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.

N-Queens - 图1

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:

  1. [
  2.  [".Q..",  // Solution 1
  3.   "...Q",
  4.   "Q...",
  5.   "..Q."],
  7.  ["..Q.",  // Solution 2
  8.   "Q...",
  9.   "...Q",
  10.   ".Q.."]
  11. ]

Solution:

  1. public class Solution {
  2.   public List<String[]> solveNQueens(int n) {
  3.     List<String[]> res = new ArrayList<String[]>();
  4.     helper(n, 0, new int[n], res);
  5.     return res;
  6.   }
  8.   private void helper(int n, int row, int[] columnForRow, List<String[]> res) {
  9.     if (row == n) {
  10.       String[] sol = new String[n];
  11.       for (int r = 0; r < n; r++) {
  12.         sol[r] = "";
  13.         for (int c = 0; c < n; c++) {
  14.           sol[r] += (columnForRow[r] == c) ? "Q" : ".";
  15.         }
  16.       }
  17.       res.add(sol);
  18.       return;
  19.     }
  21.     for (int col = 0; col < n; col++) {
  22.       columnForRow[row] = col;
  24.       if (check(row, col, columnForRow)) {
  25.         helper(n, row + 1, columnForRow, res);
  26.       }
  27.     }
  28.   }
  30.   private boolean check(int row, int col, int[] columnForRow) {
  31.     for (int r = 0; r < row; r++) {
  32.       if (columnForRow[r] == col || row - r == Math.abs(columnForRow[r] - col)) {
  33.         return false;
  34.       }
  35.     }
  36.     return true;
  37.   }
  38. }