问题描述：

问题描述

　　地球人都知道，在国际象棋中，后如同太阳，光芒四射，威风八面，它能控制横、坚、斜线位置。
　　看过清宫戏的中国人都知道，后宫乃步步惊心的险恶之地。各皇后都有自己的势力范围，但也总能找到相安无事的办法。
　　所有中国人都知道，皇权神圣，伴君如伴虎，触龙颜者死......
　　现在有一个n*n的皇宫，国王占据他所在位置及周围的共9个格子，这些格子皇后不能使用（如果国王在王宫的边上，占用的格子可能不到9个）。当然，皇后也不会攻击国王。
　　现在知道了国王的位置（x,y）（国王位于第x行第y列，x,y的起始行和列为1），请问，有多少种方案放置n个皇后，使她们不能互相攻击。

输入格式

　　一行，三个整数，皇宫的规模及表示国王的位置

输出格式

　　一个整数，表示放置n个皇后的方案数

样例输入

8 2 2

样例输出

10

数据规模和约定

　　n<=12

 

问题分析：

王后传说的问题其实就是在八皇后问题之上添加了国王附近位置不能占用的条件，基本解题思路和八皇后问题一样。

首先我们来看一下八皇后问题：

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

解决八皇后的问题关键在于寻找八个皇后之间不相容的位置关系，当不满足互斥条件时可以将皇后放入棋盘中。国王王后问题只需要在最后再来判断王后的位置与国王的位置是否冲突。分成两步来做比较清晰。

下面给大家看一下我得出的国王和王后互斥关系式

 

解题步骤：

1.从第一个皇后开始摆放，从0行0开始放（0，0），判断与当前皇后之前的皇后位置是否冲突。如果不冲突则摆放下一个皇后，否则从第一行下一个位置开始放（0，1）。（递归体）

2.重复第一个步骤直到所有的皇后都摆放完，即先解决了皇后是否能在棋盘里放完，否则连皇后都解决不了就更别提国王了。

3.当所有的皇后都摆放完了之后，判断每一个皇后的位置与国王的位置是否冲突。否则该摆放方法不可取（递归出口）

详细代码：

package kingQueen;
import java.util.Scanner;

public class Main {
	static int n = 0;
	static int x_king = 0, y_king = 0;
	static int queen[] = new int [12];
	static int result = 0;
	
	public static void main(String args[]) {
		
		
		@SuppressWarnings("resource")
		Scanner input = new Scanner(System.in);
		n = input.nextInt();
		//坐标从0开始，国王坐标需要减一
		x_king = input.nextInt() - 1;
		y_king = input.nextInt() - 1;
		find(0);
		System.out.println(result);
		
		
	}
	
	public static  void find(int position) {
		
		//放置完王后后判断是否与国王位置冲突
		if(position == n) {
			boolean conflict_king = false;
			for(int i = 0;i<n;i++) 
				//位置冲突
				if(i >= x_king - 1 && i<= x_king + 1 && queen[i] >= y_king - 1 && queen[i] <= y_king + 1) {
					conflict_king = true;
					break;
				}
			if(conflict_king == false) {
				result++;
				return;
			}
				
			
		}
		//放置皇后位置，每个皇后默认在不同的行
		for(int i = 0;i<n;i++) {
			
			int j =0;
			boolean conflict_queen = false;
			for(;j<position;j++) 
				//皇后位置冲突
				if(i == queen[j] || Math.abs(i - queen[j]) == Math.abs(position - j)) {
					conflict_queen = true;
					break;
				}
					
			if(conflict_queen == false) {
				queen[position] = i;
				find(position+1);
			}
			
			
		}
		
		
	}

}