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.

Example

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

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

Solution

看到求多种不同的解决方案自然可以想到用标准的DFS， 这道题是个表格，所以DFS搜索的时候，每次一行一行的扫描，这样首先定义DFS的参数就有一个row 参数，第一次在第一行的第一列开始，然后第二行第一列，第三行第一列，以此类推。一般的DFS题目很容根据题目的结果反推出来解题过程，但是这道题有点难度，首先如果定义了result ,然后定义一curr, curr 是不同的解决方案，但是因为curr里面是字符串的组合，非常不好判断，两个点是否在对角线，或者同一列，同一行的情况不存在，因为我们是向下不停的搜索。这个时候可以考虑是否可以用一个辅助的usedcolumns数组，这个数组用来保存第i行的Q的位置。这样就可以非常轻松的得到给定，row, column, 放下Queen是否合理，同时也可以在DFS退出的时候，通过print(usedcolumns)来得到真正的curr.

class Solution:
    """
    Get all distinct N-Queen solutions
    @param n: The number of queens
    @return: All distinct solutions
    """
    def solveNQueens(self, n):
        # write your code here
        result = []
        usedColumns = [0] * n
        if n <= 0:
            return result
        self.search(usedColumns, result, 0)
        return result

    def search(self, usedColumns, result, row):
        n = len(usedColumns)
        if n == row:
            result.append(self.printChessBoard(usedColumns))
            return
        for i in range(n):
            if self.isValid(usedColumns, row, i):
                usedColumns[row] = i
                self.search(usedColumns, result, row + 1)
    def isValid(self, usedColumns, row, col):
        for i in range(row):
            # check the columns is valid
            if usedColumns[i] == col:
                return False
            # left-top to right-bottom, right-top to left - bottom.
            if row - i == abs(col - usedColumns[i]) :
                return False
        return True
    def printChessBoard(self, usedColumns):
        chessboard = []
        n = len(usedColumns)
        for r in range(n):
            line = ""
            for c in range(n):
                if usedColumns[r] == c:
                    line += "Q"
                else:
                    line += "."
            chessboard.append(line)
        return chessboard