LeetCode-52. N-Queens II (JAVA)（N皇後解集個數）

52. N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

N皇後問題是一個經典的問題，在一個N*N的棋盤上放置N個皇後，每行一個并使其不能互相攻擊（同一行、同一列、同一斜線上的皇後都會自動攻擊）。

 LeetCode-51. N-Queens (JAVA)（列印N皇後解集）

一：

int count = 0;

	public int totalNQueens(int n) {
		char[][] board = new char[n][n];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				board[i][j] = '.';
		dfs(board, 0);
		return count;
	}

	// 類似求全排列，組合
	// 按列進行放置，若到了第colIndex列，那麼第0~colIndex-1列已經是放置好的
	private void dfs(char[][] board, int colIndex) {
		if (colIndex == board.length) {
			count++;
			return;
		}
		// 類似求全排列，組合
		// 按列進行放置，若到了第colIndex列，那麼第0~colIndex-1列已經是放置好的
		for (int i = 0; i < board.length; i++) {
			// 找一個在colIndex列适合放置Q的位置
			if (validate(board, i, colIndex)) {
				board[i][colIndex] = 'Q';
				dfs(board, colIndex + 1);
				board[i][colIndex] = '.';
			}
		}
	}

	// x == i 同一行
	// x + j == y + i (y -x == j - i,斜率1,在同一條直線上) 同一主斜行
	// x + y == i + j(x-i=-(y-j),斜率-1,在同一條直線上) 同一副斜行
	private boolean validate(char[][] board, int x, int y) {
		for (int i = 0; i < board.length; i++) {
			// 判斷放置第j列的時候，是否與前面的沖突，
			// 不需要判斷y == j（循環j<y），隻是與前面的進行比較
			for (int j = 0; j < y; j++) {
				// same as if(board[i][j] == 'Q' && (Math.abs(x - i) ==
				// Math.abs(y - j) || x == i))
				if (board[i][j] == 'Q' 
						&& (x - y == i - j 
						|| x + y == i + j 
						|| x == i))
					return false;
			}
		}
		return true;
	}
           

二：

一個N長的數組就可以解決 int[n]，例如int[0]=1表示在Q放在第1行的第2列，int[2]=3表示在Q放在第3行的第4列。

int count;

	public int totalNQueens(int n) {
		// 第i個位置存放的數表示row行時，Q的列
		int[] queenList = new int[n];
		// 從第0行開始放
		placeQueen(queenList, 0, n);
		return count;
	}

	private void placeQueen(int[] queenList, int row, int n) {
		// 如果已經填滿，就生成結果
		if (row == n) {
			count++;
			return;
		}
		// 按照行進行放置
		for (int col = 0; col < n; col++) {// 循環每一列
			if (isValid(queenList, row, col)) { // 如果在該列放入Q不沖突的話
				// 沒有回溯，因為沒有修改原結果集
				// 隻是臨時記錄結果
				queenList[row] = col;
				placeQueen(queenList, row + 1, n);
			}
		}
	}

	private boolean isValid(int[] queenList, int row, int col) {
		for (int i = 0; i < row; i++) {
			// pos為列
			int pos = queenList[i];
			if (pos == col) { // 和新加入的Q處于同一列
				return false;
			}
			if (pos + row - i == col) { // 在新加入的Q的右對角線上
				return false;
			}
			if (pos - row + i == col) { // 在新加入的Q的左對角線上
				return false;
			}
		}
		return true;
	}