Question

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.

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Solution

It is a text-book backtracking problem. In a valid solution, there are no more than 1 queens in each row, column, and diagonal. We can express them as boolean values so that we don’t have to validate each constraint for every index (i, j). If we place one queen per row, then we don’t need to keep track of the row constraint, but we will need to track n columns, 2n - 1 left and right diagonals. For a given index (i, j), the corresponding indices for its two diagonals are i + j (top-left to bottom-right) and i - j + n - 1 (bottom-left to top-right).

In order for an index (i, j) to be valid, the column and diagonal constraint must be valid. Thus, we can recursively try each valid position for every row, and construct the result when we reach the bottom of the board.

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        self.col = [True] * n
        self.diag1 = [True] * (2 * n - 1)
        self.diag2 = [True] * (2 * n - 1)
        self.queens = [-1] * n
        self.n = n

        res = list()
        self.__solve(res, 0)
        return res

    def __solve(self, res, row): # backtracking
        if row == self.n:
            board = list()
            for q in self.queens:
                board.append('.' * q + 'Q' + '.' * (self.n - q - 1))
            res.append(board)
        else:
            for col in range(self.n):
                if self.__isAvailable(row, col):
                    self.__place(row, col)
                    self.__solve(res, row + 1)
                    self.__remove(row, col)


    def __isAvailable(self, row, col):
        return self.col[col] and self.diag1[row + col] and self.diag2[row - col + self.n - 1]

    def __place(self, row, col):
        self.queens[row] = col
        self.col[col] = False
        self.diag1[row + col] = False
        self.diag2[row - col + self.n - 1] = False

    def __remove(self, row, col):
        self.queens[row] = -1
        self.col[col] = True
        self.diag1[row + col] = True
        self.diag2[row - col + self.n - 1] = True