N皇后问题

题目描述

使用回溯法求解N后问题

输入

皇后的个数 ，也是棋盘的大小

输出

每一种方案及总方案数

样例输入 Copy

4

样例输出 Copy

0 1 0 0
0 0 0 2
3 0 0 0
0 0 4 0

0 0 1 0
2 0 0 0
0 0 0 3
0 4 0 0

总方案数为：2

package book;

import java.util.Scanner;

public class nqueen {
static int m[];//同一列
static int l[];//左斜线
static int r[];//右斜线
static int x;
static int array[][];
static int res=0;
public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		x=sc.nextInt();
		array=new int[x][x];
		m=new int[2*x];
		l=new int[2*x];
		r=new int[2*x];
		solve(0);
		System.out.println("总方案数为"+res);
		
		
		
		

	}
private static void solve(int i) {
	for(int j=0;j<x;j++) {
		if(array[i][j]==0&&r[i+j]==0&&m[j]==0&&l[i-j+x]==0) {
			array[i][j]=i+1;
			r[i+j]=m[j]=l[i-j+x]=1;
			if(i==x-1) {
				res++;
				print(array);
			}else {
				solve(i+1);
			}
			array[i][j]=0;
			r[i+j]=m[j]=l[i-j+x]=0;
		}
	}
	
}
private static void print(int[][] array2) {
	for(int i=0;i<x;i++) {
	     for(int j=0;j<x;j++) {
	    	 System.out.print(array[i][j]);
	     }
	     System.out.println();
	}
	System.out.println("----------------");
	
}

}