八皇后问题
是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。
历史
八皇后问题最早是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出。之后陆续有数学家对其进行研究，其中包括高斯和解的个数
下表给出了 n 皇后问题的解的个数包括独立解U（中的数列）以及互不相同的解D（中的数列）的个数：
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | .. | 24 | 25 | 26 |
U: | 1 | 0 | 0 | 1 | 2 | 1 | 6 | 12 | 46 | 92 | 341 | 1,787 | 9,233 | 45,752 | .. | 28,439,272,956,934 | 275,986,683,743,434 | 2,789,712,466,510,289 |
D: | 1 | 0 | 0 | 2 | 10 | 4 | 40 | 92 | 352 | 724 | 2,680 | 14,200 | 73,712 | 365,596 | .. | 227,514,171,973,736 | 2,207,893,435,808,352 | 22,317,699,616,364,044 |
可以注意到六皇后问题的解的个数比五皇后问题的解的个数要少。现在还没有已知公式可以对 n 计算 n 皇后问题的解的个数。
程序
- /*
- * Copyright (c) leo
- * All rights reserved.
- * filename: nQueens
- * summary :
- * version : 1.0
- * author : leo
- * date : 8.12.2011
- *问题：
- * 在n*n (n=1 or n>=4 )的棋盘上放置n个皇后，如果在同一行，同一列，同一对角线上都不存在两个皇后，
- * 那么这个棋盘格局就是n皇后的一个解。
- *要求：
- * 找出n皇后的一组解即可，打印出放置满足n皇后条件的棋子位置
- */
- #include<stdio.h>
- #include<math.h>
- #include<stdlib.h>
- #include<conio.h>
- #define N 8 //皇后数=棋盘行列数
- int a[N]; //a为第i行皇后所在列
- void show() //图形化输出
- {
- int i;
- int p,q ;
- int b[N][N]={0};
- static t=1;
- printf("第%d个解为: ",t++);
- for(i=0;i<N;i++)
- {
- b[a]=1;
- printf("(%d,%d) ",i,a);
- }
- printf("\n");
- for(p=0;p<N;p++)
- {
- for(q=0;q<N;q++)
- {
- if(b
[q]==1)
- printf("●");
- else
- printf("○");
- }
- printf("\n");
- }
- }
- int check(int n) //满足条件返回1，否则返回0
- {
- int i;
- for(i=0;i<n;i++)
- {
- if(a==a[n]||fabs(n-i)==fabs(a-a[n])) //at the same column or diagonal (对角线)
- return 0;
- }
- return 1;
- }
- void put(int n) //在第n行放置第n个皇后
- {
- int i;
- if(n==N)
- return ;
- for(i=0;i<N;i++)
- {
- a[n]=i;
- if(check(n)) //位置合法
- {
- if(n==N-1) //皇后全部放置完毕
- show();
- else
- put(n+1);
- }
- }
- }
- int main ()
- {
- put(0);
- return 0;
- }
參考資料
Watkins, John J. (2004). Across the Board: The Mathematics of Chess Problems. Princeton: Princeton University Press. ISBN 0-691-11503-6.
O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare Structured Programming, Academic Press, London, 1972 ISBN 0-12-200550-3 see pp 72-82 for Dijkstra's solution of the 8 Queens problem.
- 上一篇： 螺旋队列算法分析
- 下一篇： WideCharToMultiByte 将CString转为char
-
精密半导体参数测试解决方案 直播时间： 01月08日 10:00
/3 
文章评论（0条评论）
登录后参与讨论