八皇后及n皇后问题

八皇后问题

是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。

历史

八皇后问题最早是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出。之后陆续有数学家对其进行研究，其中包括高斯和，并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹·诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年，S.冈德尔提出了一个通过行列式来求解的方法，这个方法后来又被J.W.L.格莱舍加以改进。

艾兹格·迪杰斯特拉在1972年用这个问题为例来说明他所谓结构性编程的能力。

八皇后问题出现在1990年代初期的著名电子游戏第七访客中。

八皇后問題的解

八皇后问题一共有 92 个互不相同的解。如果将旋转和对称的解归为一种的话，则一共有12个独立解，具体如下：

解的个数

下表给出了 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]为第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[i][a[i]]=1;
        printf("(%d,%d) ",i,a[i]);
    }
    printf("\n");
    for(p=0;p<N;p++)
    {
        for(q=0;q<N;q++)
        {
            if(b[p][q]==1)
                printf("●");
            else
                printf("○");
        }
        printf("\n");
    }
}
int check(int n) //满足条件返回1，否则返回0
{
    int i;
    for(i=0;i<n;i++)
    {
        if(a[i]==a[n]||fabs(n-i)==fabs(a[i]-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. .

, , Structured Programming, Academic Press, London, 1972 see pp 72-82 for Dijkstra's solution of the 8 Queens problem.