N_Queen (Back Tracking 알고리즘)

N-Queen 알고리즘

 

N-Queen 알고리즘이란 가로, 세로의 셀 수가 같은 체스판에서 Queen 말이 놓일 수 있는 자리를 찾는 알고리즘입니다. Queen말은 가로, 세로, 대각선에 하나의 Queen말만 놓일 수 있습니다. 즉, Queen말이 놓인 자리에서 가로, 세로, 대각선에는 다른 Queen말이 놓일 수 없습니다.

Queen 말이 놓이는 방법은 전수검사와 Back Tracking 알고리즘을 사용하는 방법 두 가지가 있습니다. 또 전수검사 방법은 반복문을 이용하는 방법과 재귀함수를 이용하는 방법 두 가지가 있습니다.

전수검사의 경우는 체스판에 말을 다 놓은 상태에서 말의 위치를 하나씩 이동하여 올바른 해답을 찾을 경우에만 그 자리를 출력하는 방법을 통해 구현됩니다. 하지만 고급 알고리즘은 Back Tracking 알고리즘은 재귀함수를 사용하여 가능한 수를 탐색하다가 올바르지 않는 경우가 발생하며 회귀하여 다음 조건을 검색하는 방법으로 탐색을 합니다. Back Tracking 알고리즘의 핵심은 재귀함수를 사용한 해답의 처리 속도를 증가 시키는 것입니다.

코드 작성 기준

• 체스판의 크기는 8 * 8 Size 로 함
• 체스판은 배열을 사용하여 표현합니다.
• 배열의 값은 0은 빈공간, 1은 Queen 말이 놓인 자리로 표시합니다.
• 체스판에 Queen 이 있는 모습을 보기 쉽게 구현합니다.
• Queen말이 놓일 자리를 탐색하는 함수를 구현합니다.
  

 

1. 선언부 

#include <stdio.h>
#include <stdlib.h>

#define width 8

int chess_b[width][width]={0};  // 체스판
int index[width]={0}; 

int count=0;

void show();  // 콘솔창에 결과를 출력하는 함수

int search(int x, int y);     // Queen 자리 탐색 함수

void select_q(int x, int y);  // 전수검사(반복문)를 사용하여 탐색하는 함수

int select_q(int x);  // 전수검사(재귀함수)를 사용하여 탐색하는 함수

int select_q(int x, int y); // Back Tracking 알고리즘을 사용하여 탐색하는 함수

  

2. 체스판의 모습을 보여주는 함수

/*
 * 체스판의 모습을 보여주는 함수
 */
void show(){
 int i, j;

 puts("");
 count+=1;
 printf(" %d 번째 출력 \n", count);

  for(i=0; i<width; i++) {
  for(j=0; j<width; j++) {
   if(chess_b[i][j]==1) {
    fputs("■", stdout);
   }
   else {
    fputs("□", stdout);
   }
  }
  puts("");
 }
 puts("");
 getchar();
}

 

3. 새로운 Queen을 놓을 수 있는 자리인가 탐색하는 함수 

/*
 *  퀸의 자리 탐색함수
 */
int search(int x, int y){

 int i,j;

 

 // 행 검사.
 for(i=0; i<width; i++) {
  if( chess_b[i][y]==1) { return 0; }
 }

 // 열 검사.
 for(i=0; i<width; i++) {
  if( chess_b[x][i]==1 ) { return 0; }
 }

 // "/" 대각선 검사.
 if(x+y<7) {
  for(i=0, j=x+y; j>0; j--, i++) {
   if(chess_b[i][j]==1) { return 0; }
  }
 }
 else {
  for(i=(x+y)-7, j=7; i<width; i++, j--) {
   if(chess_b[i][j]==1) { return 0; }
  }
 }

 // "역/"  대각선 검사.
 if(x>=y) {
  for(i=x-y, j=0; i<width; i++, j++) {
   if(chess_b[i][j]==1) { return 0; }
  }
 }
 else {
  for(i=0, j=(y-x); j<width; i++, j++) {
   if(chess_b[i][j]==1) { return 0; }
  }
 }

 return 1; // 퀸을 놓은 자리에 다른 퀸이 없다면 1을 리턴.
}

 

4-1. Queen을 놓는 함수(1번 반복문을 통한 전수검사) 

/*
 * 퀸말을 놓는 함수(전수 검사형태 이용).
 */
void select_q(int x, int y)
{
 int i1,i2,i3,i4,i5,i6,i7,i8;

 int j, temp=0;

 

 for(i1=0; i1<width; i1++) {
  if(search(0, i1)==1) { index[0]=1; }
  else { index[0]=0; }
  chess_b[0][i1]=1;
  
  for(i2=0; i2<width; i2++) {
   if(search(1, i2)==1) { index[1]=1; }
   else { index[1]=0;}
   chess_b[1][i2]=1;

 

   for(i3=0; i3<width; i3++) {
    if(search(2, i3)==1) { index[2]=1; }
    else {index[2]=0; }
    chess_b[2][i3]=1;

 

    for(i4=0; i4<width; i4++) {
     if(search(3, i4)==1) { index[3]=1; }
     else { index[3]=0; }
     chess_b[3][i4]=1;
     
     for(i5=0; i5<width; i5++) {
      if(search(4, i5)==1) { index[4]=1; }
      else { index[4]=0; }
      chess_b[4][i5]=1;
      
      for(i6=0; i6<width; i6++) {
       if(search(5, i6)==1) { index[5]=1; }
       else { index[5]=0; }
       chess_b[5][i6]=1;
       
       for(i7=0; i7<width; i7++) {
        if(search(6, i7)==1) { index[6]=1; }
        else { index[6]=0; }
        chess_b[6][i7]=1;
        
        for(i8=0; i8<width; i8++) {
         if(search(7, i8)==1) { index[7]=1; }
         else { index[7]=0; }
         chess_b[7][i8]=1;
         for(j=0; j<width; j++) {
          temp+=index[j];
         }
         if(temp==8) { show(); }
         temp=0;
         chess_b[7][i8]=0;
        }
        chess_b[6][i7]=0;
       }
       chess_b[5][i6]=0;
      }
      chess_b[4][i5]=0;
     }
     chess_b[3][i4]=0;
    }
    chess_b[2][i3]=0;
   }
   chess_b[1][i2]=0;
  }
  chess_b[0][i1]=0;
 }  
}

 

4-2. Queen을 놓는 함수(2번 재귀함수를 통한 전수검사)

/*
 * 전수검사 방식(재귀함수)
 */
int select_q(int x)
{
 int i, j=0;
 
 if(x<width) { // 재귀 함수가 돌 범위 설정.
  for(i=0; i<width; i++) {
   if(search(x,i)==1) { index[x]=1; }
   else { index[x]=0; }
   chess_b[x][i]=1;
   select_q(x+1);
   
   // 마지막 값까지 하나라도 거짓이 나오면 종료.
   // 마지막 값까지 참이면 화면에 출력.
   while(j<width) {
    if(index[j]==0) { break; }
    else if(j==7&&index[j]==1) { show(); }
    j++;
   }
   chess_b[x][i]=0;
  }
 }
 else { // 범위을 넘어서면 재귀 함수 종료.
  return 0;
 }
}

 

4-3. Queen을 놓는 함수(3번 BackTracking) 

/*

 * backtracking 방식사용한 함수.

 */
int select_q(int x, int y)
{
 int i,j=0;

 if(x<width&&y<width){
  for(i=0; i<width; i++) {
   if(search(x,i)==1) {
    chess_b[x][i]=1;
    index[x]=1;
    select_q(x+1, i);
    // x값이 마지막 행이 도착하면 조건 비교 화면에 출력.
    if(x==width-1) {
     while(j<width) {
      if(index[j]==0) { break; }
      else if(j==7&&index[j]==1) { show(); }
      j++;
     }
    }
    chess_b[x][i]=0;
   }
   else { continue; }
  }
 }
 else
  return 0;
}

 

 

실행 파일

8_queen.exe

 

8_queen.exe

0.15MB