Simple and Intuitive Python Solution


  • 0
    C

    So let's start with solving for 1 N Queen. This is simple and easy to understand.

    class Solution(object):
        def solveNQueens(self, n):
            """
            :type n: int
            :rtype: List[List[str]]
            """
            grid = [['.' for _ in range(n)] for _ in range(n)]
            solved = self.helper(n, 0, grid)
            if solved:
                return ["".join(item) for item in grid]
            else:
                return None
    
        def helper(self, n, row, grid):
            if n == row:
                return True
            for col in range(n):
                if self.is_safe(row, col, grid):
                    grid[row][col] = 'Q'
                    if self.helper(n, row + 1, grid):
                        return True
                    else:
                        grid[row][col] = '.'
            return False
    
        def is_safe(self, row, col, board):
            for i in range(len(board)):
                if board[row][i] == 'Q' or board[i][col] == 'Q':
                    return False
            i = 0
            while row - i >= 0 and col - i >= 0:
                if board[row - i][col - i] == 'Q':
                    return False
                i += 1
            i = 0
            while row + i < len(board) and col + i < len(board):
                if board[row + i][col - i] == 'Q':
                    return False
                i += 1
            i = 1
            while row + i < len(board) and col - i >= 0:
                if board[row + i][col - i] == 'Q':
                    return False
                i += 1
            i = 1
            while row - i >= 0 and col + i < len(board):
                if board[row - i][col + i] == 'Q':
                    return False
                i += 1
            return True
    

    Now to modify this solution to find all possible solutions is actually very easy. The idea is instead of returning True from the helper function we copy the current result in an array and continue with the search.
    The implicit base case happens when,
    row == n and col == n

    class Solution:
        def solveNQueens(self, n):
            """
            :type n: int
            :rtype: List[List[str]]
            """
            result = []
            grid = [['.' for _ in range(n)] for _ in range(n)]
            self.helper(n, 0, grid, result)
            return result
    
        def helper(self, n, row, grid, result):
            if n == row:
                g = grid[:]
                result.append(["".join(item) for item in g])
                return
            for col in range(n):
                if self.is_safe(row, col, grid):
                    grid[row][col] = 'Q'
                    self.helper(n, row + 1, grid, result)
                    grid[row][col] = '.'
    
        def is_safe(self, row, col, board):
            for i in range(len(board)):
                if board[row][i] == 'Q' or board[i][col] == 'Q':
                    return False
            i = 0
            while row - i >= 0 and col - i >= 0:
                if board[row - i][col - i] == 'Q':
                    return False
                i += 1
            i = 0
            while row + i < len(board) and col + i < len(board):
                if board[row + i][col - i] == 'Q':
                    return False
                i += 1
            i = 1
            while row + i < len(board) and col - i >= 0:
                if board[row + i][col - i] == 'Q':
                    return False
                i += 1
            i = 1
            while row - i >= 0 and col + i < len(board):
                if board[row - i][col + i] == 'Q':
                    return False
                i += 1
            return True
    

Log in to reply
 

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