- 注册时间
- 2005-10-7
- 最后登录
- 1970-1-1
|
众所周知的八皇后问题就是在一个8*8的棋盘上放8个皇后,让她们不能互相攻击,求出所有满足条件的情况。
- input: n
- output: all answers
- 以下是源码:
- #define MAXN 16
- int n;
- int nsol,nprinted;
- char row[MAXN];
- char col[MAXN];
- char updiag[2*MAXN];
- char downdiag[2*MAXN];
- void solution()
- {
- int i;
- for(i=0; i<n; i++)
- {
- if(i!= 0) printf(" ");
- printf("%d",row[i]+1);
- }
- printf("\n");
- }
- void nway(i,lim)
- {
- int j;
- if(i==n)
- {
- nsol++;
- if (n>6&&row[0]<n/2) nsol++;
- if (nprinted++<3) solution();
- return;
- }
- for(j=0; j<lim; j++)
- {
- if(!col[j]&&!updiag[i+j] && !downdiag[i-j+MAXN])
- {
- row[i] = j;
- col[j]++;
- updiag[i+j]++;
- downdiag[i-j+MAXN]++;
- nway(i+1,n);
- col[j]--;
- updiag[i+j]--;
- downdiag[i-j+MAXN]--;
- }
- }
- }
- int main()
- {
- scanf("%d",&n);
- nway(0,n>6?(n+1)/2:n);
- printf("%d\n",nsol);
- return(0);
- }
复制代码 在游戏开发中,也许有时会用到这种算法(如:迷宫问题),希望对大家有帮助。 |
|