n皇后问题回溯法java_Java解决N皇后问题

全栈程序员站长

发布于 2022-11-19 12:34:58

7170

发布于 2022-11-19 12:34:58

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

问题描述：

要求在一个n×n的棋盘上放置n个皇后，使得它们彼此不受攻击。

按照国际象棋的规则，一个皇后可以攻击与之同一行或同一列或同一斜线上的任何棋子。

因此，n皇后问题等价于：要求在一个n×n的棋盘上放置n个皇后，使得任意两个皇后不在同一行或同一列或同一斜线上。

一个皇后的攻击范围：

n皇后的解空间—完全n叉树：

要找出“四皇后”问题的解，最可靠的方法就是把各种情况都分析一遍，将符合条件的解找出来。但这样做十分地费时间。

采用回溯算法进行求解，在搜索的过程中，将不满足条件要求的分支树剪去，可以有效地降低算法的时间复杂度。

首先定义一个Location类，用来表示棋盘上（实际上就是一个二维数组）点的位置：

static class Location{
		int x;//对应棋盘的行
		int y;//对应棋盘的列
		
		Location(int x,int y){
			this.x = x;
			this.y = y;
		}
		
                //重写toString函数用来输出点的信息
		public String toString() {
			return "(" + x + "," + y + ")";
		}
	}

然后就是判断两个皇后放置的位置是否冲突，需要判断是否在同一行、同一列和同一斜线上，这里所有的符合要求的皇后都放置在一个Location链表中，如果要新加入一个皇后，就必须要与当前链表中所有的皇后都进行冲突比较，如果冲突就放弃这个方案；如果不冲突，继续下一步，直到N个皇后都存在于链表中，才算得到了一个解:

/**
     * 判断位置为loc的皇后是否合法
     */
    private static boolean isLegalLoc(LinkedList<Location> list, Location loc) {
        for(Location each : list){
            if(loc.x == each.x || loc.y == each.y)  //判断是否在同一行或同一列
                return false;
            else if (Math.abs(loc.x - each.x) == Math.abs(loc.y - each.y))  //判断是否在同斜线上
                return false;
        }
        return true;
    }

核心算法：

	/**
     * 主要函数，用回溯法。
     */
    private static void NQueen(LinkedList<Location> list, int x, int y) {   

        if(list.size() == SIZE){  //当list元素个数为SIZE时，表示SIZE个皇后都摆放完毕，打印后即可退出函数。
            printLocation(list);  //打印皇后摆放方式
            return ;
        }

        for(int i = x ; i < SIZE ; i++){
            Location loc = new Location(i, y);
            if(isLegalLoc(list, loc)){
                list.offer(loc);  //将第y行的皇后摆放好
                NQueen(list, 0, y+1);  //开始摆放y+1行的皇后，同样从第0列开始摆放
                list.pollLast();  //每次摆放完一个皇后后，都要将其撤回，再试探其它的摆法。
            }                   
        }           
    }

由于皇后的攻击范围的特性，在这个算法执行时，只用考虑一行或者一列的情况就行，即要么使x=0固定，让y从0到n-1进行；要么反过来让y=0固定，让x从0到n-1进行。这样可以省去很多不必要的比较。

全部代码（其中还包括将N皇后问题的解显示输出的函数）：

package quene;
import java.util.LinkedList;
import java.util.Scanner;
public class Com_quene {
private static int SIZE = 0;//皇后的个数
private static int count = 0;//记录摆放的方式数
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
System.out.println("请输入你要解决几个皇后的问题");
SIZE = input.nextInt();
input.close();
LinkedList<Location> list = new LinkedList<Location>();
NQueen(list, 0, 0);  //从棋盘的第0行第0列开始
System.out.println(SIZE + "皇后共有 " + count + "种摆放方式");
}
static class Location{
int x;//对应棋盘的行
int y;//对应棋盘的列
Location(int x,int y){
this.x = x;
this.y = y;
}
public String toString() {
return "(" + x + "," + y + ")";
}
}
/**
* 主要函数，用回溯法。
*/
private static void NQueen(LinkedList<Location> list, int x, int y) {   
if(list.size() == SIZE){  //当list元素个数为SIZE时，表示SIZE个皇后都摆放完毕，打印后即可退出函数。
printLocation(list);  //打印皇后摆放方式
return ;
}
for(int i = x ; i < SIZE ; i++){
Location loc = new Location(i, y);
if(isLegalLoc(list, loc)){
list.offer(loc);  //将第y行的皇后摆放好
NQueen(list, 0, y+1);  //开始摆放y+1行的皇后，同样从第0列开始摆放
list.pollLast();  //每次摆放完一个皇后后，都要将其撤回，再试探其它的摆法。
}                   
}           
}
/**
* 判断位置为loc的皇后是否合法
*/
private static boolean isLegalLoc(LinkedList<Location> list, Location loc) {
for(Location each : list){
if(loc.x == each.x || loc.y == each.y)  //判断是否在同一行或同一列
return false;
else if (Math.abs(loc.x - each.x) == Math.abs(loc.y - each.y))  //判断是否在同斜线上
return false;
}
return true;
}
/**
* 打印皇后摆放方式
* @param list
*/
private static void printLocation(LinkedList<Location> list) {
String[][] show = new String[SIZE][SIZE];
for(int i = 0;i<SIZE;i++) {
for(int j = 0;j<SIZE;j++) {
show[i][j] = "0";
}
}
for(Location each : list){
System.out.print(each.toString() + "\t");
show[each.x][each.y] = "1";
}
System.out.println();
for(int i =0;i<SIZE;i++) {
for(int j=0;j<SIZE;j++) {
System.out.print(show[i][j] + " ");
}
System.out.println();
}
System.out.println();
count ++;
}
}

四皇后问题解的示例：