N 皇后

题目展开目录

N 皇后问题是一个以国际象棋为背景的问题：如何能够在 N×N 的国际象棋棋盘上放置 N 个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

题解展开目录

N 个皇后中任意两个不能处在同一行，所以每个皇后必须占据一行，及一列。我们采用回溯法的思想去解。首先摆放好第 0 行皇后的位置，然后在不冲突的情况下摆放第 1 行皇后的位置。到第 j 行时，如果没有一个位置可以无冲突的摆放皇后，则回溯到第 j-1 行，寻找第 j-1 行皇后的下一个可以摆放的位置。

总结一下，用回溯法解决 N 皇后问题的步骤：

1. 从第 0 列开始，为皇后找到安全位置，然后跳到下一列.
2. 如果在第 n 列出现死胡同，如果该列为第 0 列，棋局失败，否则后退到上一列，再进行回溯.
3. 如果在第 8 列上找到了安全位置，则棋局成功.

代码展开目录

C展开目录

#include <bits/stdc++.h>
using namespace std;
int N,sum = 0;
int queen[100];//queen[i]的值表示第i行放第queen[i]列 
void nqueen(int k)
{
    int j;
    if(k == N)//如果所有的皇后都放好了就输出 
    {
        for(int i = 0;i < N;i++)
            cout<<queen[i] + 1<<" ";//我是从第0行开始放，所以输出就要+1 
        cout<<endl;
        sum++;//每放置一种，就加一种方法 
        return;
    }
    for(int i = 0;i < N;i++)//枚举N列 
    {
        for(j = 0;j < k;j++)//前k行的皇后 
        {//第j行的皇后的列是queen[j]，不能和我当前的列相同 
            if(queen[j] == i || abs(j - k) == abs(queen[j] - i))
            //也不能是对角线 
                break;
        }
        if(k == j)
        {//如果情况都满足，j就会等于k，这时就保存列号，并且进入下一行枚举
            queen[j] = i;
            nqueen(k+1);
        }//如果下一行的皇后没有正确的位置放，就会回溯，继续循环上一行的皇后位置 
    } 
} 
int main()
{
    cin>>N;
    nqueen(0);//从第0行开始放皇后 
    cout<<sum;//输出一共有多少种放法 
    return 0;
}

Java展开目录

public class Nqueen {
    static int[] queen = new int[100];
    static int N, sum = 0;

    public static void nqueen(int k) {
        int j;
        if (k == N) {
            for (int i = 0; i < N; i++)
                System.out.print(queen[i] + 1 + " ");
            System.out.println();
            sum++;
            return;
        }
        for (int i = 0; i < N; i++) {
            for (j = 0; j < k; j++) {
                if (queen[j] == i || abs(queen[j], i) == abs(k, j))
                    break;
            }
            if (j == k) {
                queen[j] = i;
                nqueen(k + 1);
            }
        }
    }

    public static int abs(int i, int j) {
        if (i > j)
            return i - j;
        else
            return j - i;
    }

    public static void main(String[] args) {
        N = Integer.parseInt(args[0]);
        nqueen(0);
        System.out.println(sum);
    }
}