LeetCode | N-Queens

题目

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+CkVhY2ggc29sdXRpb24gY29udGFpbnMgYSBkaXN0aW5jdCBib2FyZCBjb25maWd1cmF0aW9uIG9mIHRoZSBuLXF1ZWVucw==" placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

用DFS递归得到所有结果，需要注意的是剪枝的时候有两种方式：

一种是遍历先前的皇后出现位置，判断当前行的可行位置，这种是节省空间，但时间复杂度较高（解法1）；

另一种是用空间换时间，从列、主对角线、反对角线三个方向上纪录已经被占用的位置，从而直接判断出当前行的可用位置（解法2）。

解法1

import java.util.ArrayList;

public class NQueens {
	private ArrayList
  
    results;
	private int n;

	public ArrayList
   
     solveNQueens(int n) { this.n = n; results = new ArrayList
    
     (); // index: row, value: column int[] queue = new int[n]; dfs(0, queue); return results; } private void dfs(int row, int[] queue) { if (row == n) { results.add(constructResult(queue)); return; } for (int j = 0; j < n; ++j) { boolean valid = true; for (int i = 0; i < row; ++i) { if (queue[i] == j || Math.abs(j - queue[i]) == row - i) { valid = false; break; } } if (valid) { queue[row] = j; dfs(row + 1, queue); } } } private String[] constructResult(int[] queue) { String[] array = new String[n]; StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; ++i) { sb.append('.'); } for (int i = 0; i < n; ++i) { sb.setCharAt(queue[i], 'Q'); array[i] = sb.toString(); sb.setCharAt(queue[i], '.'); } return array; } }
    
   
  

解法2

import java.util.ArrayList;

public class NQueens {
	private ArrayList
  
    results;
	private int n;
	private int[] column;
	private int[] mainDiag;
	private int[] antiDiag;
	private int[] queen;

	public ArrayList
   
     solveNQueens(int n) { this.n = n; results = new ArrayList
    
     (); column = new int[n]; mainDiag = new int[2 * n]; antiDiag = new int[2 * n]; queen = new int[n]; dfs(0); return results; } private void dfs(int row) { if (row == n) { results.add(constructResult(queen)); return; } for (int j = 0; j < n; ++j) { if (column[j] == 0 && mainDiag[row + j] == 0 && antiDiag[row + n - j] == 0) { column[j] = mainDiag[row + j] = antiDiag[row + n - j] = 1; queen[row] = j; dfs(row + 1); column[j] = mainDiag[row + j] = antiDiag[row + n - j] = 0; } } } private String[] constructResult(int[] queen) { String[] array = new String[n]; StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; ++i) { sb.append('.'); } for (int i = 0; i < n; ++i) { sb.setCharAt(queen[i], 'Q'); array[i] = sb.toString(); sb.setCharAt(queen[i], '.'); } return array; } }