[LeetCode] N-Queens

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.

Each solution contains a distinct board configuration of the n-queens' 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.."]
]

Solution: DFS.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

public class Solution { private int n; private int[] idx; private ArrayList<String[]> result; private String s; void storeResult() { String[] config = new String[n]; for (int i = 0; i < n; i++) { StringBuffer sb = new StringBuffer(); sb.append(s.substring(0, idx[i])); sb.append('Q'); sb.append(s.substring(idx[i] + 1)); config[i] = sb.toString(); } result.add(config); } boolean isValid(int row) { for (int r = 0; r < row; r++) { if ( idx[r] == idx[row] || Math.abs(idx[r] - idx[row]) == row - r ) { return false; } } return true; } void DFS(int row) { if (row == n) { storeResult(); return; } for (int i = 0; i < n; i++) { idx[row] = i; if (isValid(row)) { DFS(row + 1); } } } public List<String[]> solveNQueens(int n) { this.n = n; idx = new int[n]; result = new ArrayList<String[]>(); char[] chars = new char[n]; Arrays.fill(chars, '.'); s = new String(chars); DFS(0); return result; } }