递归回溯法-八皇后问题

一、问题描述

八皇后问题是回溯算法的典型案例。该问题由国际西洋棋手马克斯 • 贝瑟尔于1848年提出：

在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后不能处于同一行、同一列或同一斜线上，问有多少种摆法。通过计算可以得出共有92种摆法。

二、思路分析

由于规定两个皇后不能处于同一行，因此一种放置结果可以由对应的一个一维数组来表示（记所有索引都从0开始）。

如下图所示的可行解，对应数组即 [0，4，7，5，2，6，1，3]，很直观，即第0行的皇后，放置在第0列；第1行的皇后放置在第4列...

在求解时，按照逐行逐列放置的思路。

由第0行的皇后开始放置，放置位置为 0~7 列；同样，第 i 行的皇后放置位置也为 0~7 列；

在放置第 i 行的皇后是否能放置在第 j 列时，需要依次判断是否与前 i-1 行的各个皇后相互攻击，如果都不攻击，即满足条件，则继续放置 i+1 行的皇后；否则，继续判断第 j+1 列的位置是都可行；

三、Java实现

// 八皇后问题，在一个8×8的国际象棋棋盘上摆放8个皇后，
// 摆放需遵守皇后不能处于同一行、同一列、同一斜线上，问有多少种摆法

// 由于不能处于同一行、说明每行只能放1个皇后
// 用一维数组 arr 表示一组皇后放置结果（索引从0开始）
// Eg，[0，4，7，5，2，6，1，3]表示第0行的皇后，放置在第0列；第1行的皇后放置在第4列...
// 问题等效于，找到一组符合条件的permute排列，通过回溯法求解。

public class EightQueen
{
    int count = 0;  //记录一共多少种解法
    int[] arr = new int[8];

    public static void main(String[] args)
    {
        EightQueen q = new EightQueen(); //创建一个类的对象 q
        q.putQueen(0); //棋盘为空，从第0行的皇后开始放
        System.out.println("count:"+q.count);
    }



    //判断第i个皇后是否能放在第j个位置
    public boolean verifyPos(int[] arr,int i,int pos)
    {
        for (int putAread = 0; putAread <i; putAread++)
            //在判断第i行的皇后是否能放置在第j列的位置时，
            //需要依次判断是否与前i-1行的皇后在同行||同列||对角线
        {
            if (arr[putAread] == pos || arr[putAread] + i - putAread ==pos
                    || arr[putAread] + putAread -i ==pos )
                return false;
        }
        return true;
    }


    //放置第id行的皇后
    public void putQueen(int id)
    {
        for (int pos = 0; pos <8; pos++) //依次判断每一列，即第pos个位置是否放置
        {
            if (verifyPos(arr, id, pos))
            {
                arr[id] = pos; //可以放，则放置在该位置
                if (id == 7)
                    //是否全部放完，是，计数并打印输出该方案；否，继续放置下一行的皇后
                {
                    count += 1;
                    System.out.println("Solotion "+ count +" like this:");
                    printSolution(arr);
                }
                else
                {
                    putQueen(id+1);
                }
            }

        }

    }

    public void printSolution(int[] arr)
        // 打印输出可行方案
    {

        for (int id = 0; id < 8; id++)
        {
            for (int pos = 0; pos < 8; pos++)
            {
                System.out.print(arr[id]==pos?'Q':'*');
            }
            System.out.println();
        }
    }

}