八皇后问题

基本概念 

八皇后问题：一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。

解决方案

回溯法

程序实现

C++版本

#include<iostream>
using namespace std;
static int gEightQueen[8] = { 0 }, gCount = 0;
void print()//输出每一种情况下棋盘中皇后的摆放情况
{
    for (int i = 0; i < 8; i++)
    {   
        int inner;
        for (inner = 0; inner < gEightQueen[i]; inner++)
            cout << "0";
            cout <<"#";
        for (inner = gEightQueen[i] + 1; inner < 8; inner++)
            cout << "0";
        cout << endl;
    }
    cout << "==========================\n";
}
int check_pos_valid(int loop, int value)//检查是否存在有多个皇后在同一行/列/对角线的情况
{
    int index;
    int data;
    for (index = 0; index < loop; index++)
    {
        data = gEightQueen[index];
        if (value == data)
            return 0;
        if ((index + data) == (loop + value))
            return 0;
        if ((index - data) == (loop - value))
            return 0;
    }
    return 1;
}
void eight_queen(int index)
{
    int loop;
    for (loop = 0; loop < 8; loop++)
    {
        if (check_pos_valid(index, loop))
        {
            gEightQueen[index] = loop;
            if (7 == index)
            {
                gCount++, print();
                gEightQueen[index] = 0;
                return;
            }
            eight_queen(index + 1);
            gEightQueen[index] = 0;
        }
    }
}
int main(int argc, char*argv[])
{
    eight_queen(0);
    cout << "total=" << gCount << endl;
    return 0;
}

JAVA版本

public class Solution {
    int n=8;     //八个皇后
    int total=0; //总共的解法
    int []c=new int[n];
    //八皇后问题共有92种解法(回溯法、递归实现)
    public void maxQueen(int row) {
          if(row==n){
              total++;
          }
          else{
             for(int col=0;col!=n;col++){
              c[row]=col;
              if(isOk(row))
              {
                 maxQueen(row+1); //递归调用，进行下一行的安排
              }
             }
          }       
    }
    //判断一个位置是否可以放置皇后
    public boolean isOk(int row){
      for(int j=0;j!=row;j++){
         if((c[row]==c[j])||(row-c[row]==j-c[j])||(row+c[row]==j+c[j]))
            return false;
      }
      return true;
    }

    public static void main(String[]args){
      Solution s=new Solution();
      s.maxQueen(0);
      System.out.println(s.total);
    }
}

问题扩展

N皇后问题 

参考文章

百度百科

深度优先搜索算法