MENU

N皇后

March 24, 2018 • Read: 111 • 算法

题目

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);
    }
}
Archives Tip
QR Code for this page
Tipping QR Code