回溯 n皇后问题

1.问题描述

在一个n×n 的棋盘，有n个皇后棋子被放置在棋盘上。不能让皇后之间互相攻击。
即同时要满足每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

（PS：我们知道国际象棋中，“皇后”是整个棋局最强的棋子，在棋盘中，可以横、竖、斜走，且格数不限。）

输入：（int）n表示棋子个数n、棋盘大小n*n。

输出：前三行：前三个解；第四行：只有一个数字，表示解的总数。

示例

输入 #1

6

输出 #1

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

问题分析

我们知道每一行，都只能有一个棋子，于是我们从第一行一直放到第i行。在第一行，放入棋盘后，我们要如何判断下一行，放入的位置是不是符合规则的呢。

我们只需要判断，这个位置的所在的行、列、左对角线（左上到右下）、右对角线（左下到右上）是否已经存在一个棋子了。

在代码的实现中，我们使用4个数组，来标记行、列、左右对角线是否存在棋子。

package mypackage;
import java.util.Scanner;
public class Checker_Challenge {
	static int a[]=new int [30];
	static boolean b[]=new boolean[30];
	static boolean c[]=new boolean[30];
	static boolean d[]=new boolean[30];
	static int sum=0;
	static int n;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in=new Scanner(System.in);
		n=in.nextInt();
		dfs(1);
		System.out.print(sum);
		in.close();
	}
	public static void myprint() {
		if (sum<=2) {
			for(int k=1;k<=n;k++)
				System.out.print(a[k]+" ");
			System.out.println();
		}
		sum++;
	}
	public static void dfs(int i) {
		if(i>n) {
			myprint();
			return;
		}else {
			for(int j=1;j<=n;j++) {
				if((!b[j])&&(!c[i+j])&&(!d[i-j+n])) {
					a[i]=j;
					b[j]=true;
					c[i+j]=true;
					d[i-j+n]=true;
					dfs(i+1);
					b[j]=false;
					c[i+j]=false;
					d[i-j+n]=false;
				}
			}
		}
	}
}
int search(int t)
{
    if(满足输出条件)
    {
        输出解;
    }
    else
    {
        for(int i=1;i<=尝试方法数;i++)
            if(满足进一步搜索条件)
            {
                为进一步搜索所需要的状态打上标记;
                search(t+1);
                恢复到打标记前的状态;//也就是说的{回溯一步}
            }
    }
} 

回溯 n皇后问题

原文：https://www.cnblogs.com/runaway-code/p/14635420.html