BASIC-27 / Tsinsen 1085 2n皇後問題（java）

問題描述 　　給定一個n*n的棋盤，棋盤中有一些位置不能放皇後。現在要向棋盤中放入n個黑皇後和n個白皇後，使任意的兩個黑皇後都不在同一行、同一列或同一條對角線上，任意的兩個白皇後都不在同一行、同一列或同一條對角線上。問總共有多少種放法？n小于等于8。 輸入格式 　　輸入的第一行為一個整數n，表示棋盤的大小。

　　接下來n行，每行n個0或1的整數，如果一個整數為1，表示對應的位置可以放皇後，如果一個整數為0，表示對應的位置不可以放皇後。 輸出格式 　　輸出一個整數，表示總共有多少種放法。 樣例輸入 4

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1 樣例輸出 2 樣例輸入 4

1 0 1 1

1 1 1 1

1 1 1 1

1 1 1 1 樣例輸出 0

題目分析：八皇後問題擴充，搜尋，遞歸，回溯

算法分析：

 1、基本解題思路是遞歸回溯。一個白皇後和一個黑皇後看成是一組，給一個白皇後找到位置後，立刻給對應的黑皇後找位置，一組皇後中任何一個找不到位置就回溯。

    2、有了基本的解題思路，接下來要考慮的問題就是判斷矩陣中 (i,j) 位置能否放皇後：我們利用兩個一維數組 white 和 black 來記錄第 i 個白皇後所在的位置 ( i , white[i] ) 和第 i 個黑皇後所在的位置 ( i , black[i] ) ，這樣自然而然的就消除了行沖突；列沖突可以通過 white[i] ( black[i] ) 和列标j比較判定。

    此外，關于對角線的判定，有這麼一個規律，假設兩個位置 (a,b) (c,d)，如果它們在某一對角線上，它們将會滿足abs(a-c) = abs(b-d)，利用這點也可以輕而易舉的解決對角線沖突。

算法設計：

import java.util.*;

public class Main {
	public static int n;// 皇後的組數(一白一黑為一組)
	public static int[] white;// white[i]: 表示第i個白皇後在第i行第white[i]列
	public static int[] black;// black[i]: 表示第i個黑皇後在第i行第black[i]列
	public static int[][] arr;
	public static int result = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		white = new int[n];
		black = new int[n];
		arr = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		sc.close();
		
		dfs(0);
		System.out.println(result);
		//result = 0;
	}

	private static void dfs(int i) {
		if (i > n - 1) {
			result++;
			return;
		}

		int x;// 處理第i個白皇後
		for (x = 0; x < n; x++) {
			if (checkWhite(i, x)) {
				white[i] = x;
				arr[i][x] = 0;

				int y;// 處理第i個黑皇後(第i個白皇後有位置放時，才考慮第i個黑皇後)
				for (y = 0; y < n; y++) {
					if (checkBlack(i, y)) {
						black[i] = y;
						arr[i][y] = 0;

						dfs(i + 1);// 遞歸
                        //一組皇後中任何一個找不到位置就回溯
						arr[i][y] = 1;// 回溯
					}
				}
				arr[i][x] = 1;// 回溯
			}
		}
	}

	private static boolean checkWhite(int i, int x) {
		if (arr[i][x] == 0) {
			return false;
		}

		for (int k = 0; k < i; k++) {
			if (x == white[k] || Math.abs(i - k) == Math.abs(x - white[k])) {
				return false;
                //假設兩個位置 (a,b) (c,d)，如果它們在某一對角線上，它們将會滿足abs(a-c) = abs(b-d)
			}
		}
		return true;
	}

	private static boolean checkBlack(int i, int y) {
		if (arr[i][y] == 0) {
			return false;
		}
		for (int k = 0; k < i; k++) {
			if (y == black[k] || Math.abs(i - k) == Math.abs(y - black[k])) {
				return false;
                //假設兩個位置 (a,b) (c,d)，如果它們在某一對角線上，它們将會滿足abs(a-c) = abs(b-d)
			}
		}
		return true;
	}
}