Problem: 51. N 皇后

思路

👨‍🏫 参考地址

• 考虑每一行哪个位置放皇后
• 判断是否合法
• 递归下一行

Code

class Solution {
	int n;
	char[][] board;
	List<List<String>> res = new ArrayList<>();

	public List<List<String>> solveNQueens(int n)
	{
		this.n = n;
		board = new char[n][n];
		// "." 表示空，"Q"表示皇后，初始化棋盘
		for (char[] cc : board)
			Arrays.fill(cc, '.');
		backtrack(0);
		return res;
	}

	private void backtrack(int row)
	{
		if (row == n)
		{
			res.add(charToList());
			return;
		}
		for (int col = 0; col < n; col++)// 列
		{
			if (!isValid(row, col))
				continue;
			board[row][col] = 'Q';
			backtrack(row + 1);
			board[row][col] = '.';
		}
	}

//	判断在 board[row][col] 放皇后是否合法，合法返回 true
	private boolean isValid(int row, int col)
	{
//	   	同列冲突检测
		for (int i = 0; i < n; i++)
			if (board[i][col] == 'Q')
				return false;
//		tips：当前左下方和右下方是没有棋子的
//		右上方冲突检测
		for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
			if (board[i][j] == 'Q')
				return false;
//		左上方冲突检测
		for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
			if (board[i][j] == 'Q')
				return false;
		return true;
	}

	/**
	 * 根据 board 字符数组 生成 棋盘字符串list
	 * 
	 * @return 棋盘字符串list
	 */
	private List<String> charToList()
	{
		List<String> ans = new ArrayList<>();
		for (char[] c : board)
			ans.add(String.copyValueOf(c));
		return ans;
	}
}