Standard backtracking with detailed explanation and more


  • 0
    W

    The solution below is not very elegant, but it follows a generic pattern common in lots of backtracking problems.

    Most backtracking problems can be solved with Depth First Search. Once we are given such a problem, we should be thinking about solving it step by step. As in this N-Queen problem, a common way is to put a queen one column at a time. By doing so, we know we have finished once we are handling the nth column.

    For every column, we want to put a queen without violating the rules. Once our move is invalid, we undo the move and try another move in the same column. Every time we have a complete set of moves that maintain the rules, we add the board config to the solution set.

    Some important parameters are index, cur, and ret. index indicates where we are in solving the problems. Since we only have n columns, reaching index n means we have checked the previous n moves and is ready to add to solution set. cur refers to the current solution we are building. In this case, the unfinished n-queen board. ret is the solution set to keep a record of all valid board configurations.

    One caveat is that when we are adding to the solution set, we do not add cur directly, because it is a reference to a board configuration that is used throughout the solving processes. It is subject to change while what we needed was the value at a specific point.

    '''

    def solveNQueens(self, n):
        ret = []
        self.dfs(n, 0, ['.'*n for i in range(n)], ret)
        return ret
    
    def dfs(self, n, index, cur, ret):
        if index >= n:
            ret.append(cur[::])
            return
        for i in range(n):
            cur[i] = cur[i][:index]+'Q'+cur[i][index+1:]
            if self.isValid(cur, i, index):
                self.dfs(n, index+1, cur, ret)
            cur[i] = cur[i][:index]+'.'+cur[i][index+1:]
        
    def isValid(self, board, i, j):
        for a in range(j):
            if board[i][a] == 'Q':
                return False
        for b in range(1, min(i,j)+1):
            if board[i-b][j-b] == 'Q':
                return False
        for c in range(1, min(j,len(board)-i-1)+1):
            if board[i+c][j-c] == 'Q':
                return False
        return True
    

    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.