n-Queen 모델에도 적용 가능합니다~
초기 구상 ¶
8bit == 1byte 라는 생각을 하고 비트연산만으로 할 수 있을것 같다는 생각을 하였다. 하지만 이 경우는 n-Queen 으로까지 확장하기까지 힘들고 간단한 index 로 값을 참조할수 있는 배열에 비해 비능률적인 방법이다. 단지 속도가 조금 빠를 것으로 믿었는데.. 빨라봤자 얼마나 빠르겠어.--;
나중에는.. ¶
recursive-call 을 이용하겠다는 생각이 퍼뜩 들었다. 역시 가장 문제가 되는 부분은 backtrack 하는 부분이었다.
구린점 ¶
처음에 시작 call 을 좀 이상하게 한다. loop 을 돌면서 첫번째 라인의 원소에 대한 get_Queen()함수를 호출한다. 생각에는 get_Queen(0,0); 처럼 호출하는게 가장 이상적이라고 생각하는데..--;
source code ¶
~cpp #include <iostream.h> #define QUEEN 8 int Queen[QUEEN][QUEEN]={0}; int total=0; void print_result(); void reset(int fromline=0); void get_Queen(int x, int y); int check(int i, int j); int main() { for(int i=0; i<QUEEN; i++) { reset(); get_Queen(i,0); } return 0; } void get_Queen(int x, int y) { reset(y+1); Queen[x][y]=1; if(y==QUEEN-1) print_result(); for(int i=0; i<QUEEN; i++) if(check(i,y+1)) get_Queen(i,y+1); Queen[x][y]=0; } void print_result() { int i,j; for(i=0; i<QUEEN; i++) { for(j=0; j<QUEEN; j++) cout << Queen[j][i] << " "; cout << endl; } cin.get(); } void reset(int fromline) { int i,j; for(i=0; i<QUEEN; i++) for(j=fromline; j<QUEEN; j++) Queen[i][j]=0; } int check(int i, int j) { if(i<0 || j<0 || i>=QUEEN || j>=QUEEN) return 0; int x, y, sum=0; for(y=j-1; y>=0 && sum==0; y--) /* 위로 */ sum+=Queen[i][y]; for(x=i-1; x>=0 && sum==0; x--) /* 왼쪽으로 */ sum+=Queen[x][j]; for(x=i-1, y=j-1; x>=0 && y>=0 && sum==0; x--, y--) /* 대각선 */ sum+=Queen[x][y]; for(x=i+1, y=j-1; x<QUEEN && y>=0 && sum==0; x++, y--) /* 대각선 */ sum+=Queen[x][y]; return (int)(sum==0); }