[dynamic programming] python solves the N queen problem (20 lines of code)

[dynamic programming] python solves the N queen problem (20 lines of code)

If the reader doesn't know much about the idea and solution of backtracking algorithm, you can click the link to check my previous blog post< Detailed explanation of [backtracking algorithm] of algorithm >, it introduces the solution ideas and methods of backtracking algorithm in detail, which is conducive to your better learning of backtracking algorithm.

This paper mainly introduces how to use backtracking algorithm to quickly solve the classical N-queen problem.

Title Description

The n queen problem studies how to place n queens in n × N's chessboard, and the Queens can't attack each other. Given an integer n, returns the solution of all different queen n problems. Each solution contains a clear chess placement scheme for the n-queen problem, in which 'Q' and ' They represent the queen and the vacant seat respectively.

Note: the following figure is a solution to the 8 queen problem.

Queens cannot attack each other, that is, no two Queens can be in the same horizontal, vertical or diagonal line.

Example 1

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

["... Q.", / / solution 2
"Q...",
"...Q",
".Q..."]
]
Explanation: there are two different solutions to the queen problem.

Problem solving process analysis

Direct application< Detailed explanation of [backtracking algorithm] of algorithm >The basic steps of backtracking algorithm and the general framework template of backtracking algorithm.

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def backtrack(board, row):
            if row >= n:
                # # Here is to convert each line into the string form required by the title. For example, ".. Q." represents a line
                cur_res = [''.join(row) for row in board]
                res.append(cur_res)  #Save results
                return
            for i in range(n):
                if isValid(row, i, board): #isValid is used to judge whether the location is legal and can place queens
                    board[row][i] = 'Q'  #Place queen
                    backtrack(board, row+1) # row+1 goes to the next line
                    board[row][i] = '.'  #to flash back
        res = []
        board = [['.'] * n for _ in range(n)] # Initialize chessboard
        backtrack(board, 0) # row starts at 0
        return res

1. The status variable is row: row. Each time a queen position can be placed in the current row is selected, enter the next row row+1;

2. Recursion end condition: when row > = n, row starts from 0, indicating that the queens of all lines in the first n-1 have been placed, and the results are added to res.

if row >= n:
	# Here is to convert each line into the string form required by the title. For example, ".. Q." represents a line
    cur_res = [''.join(row) for row in board]
    res.append(cur_res)
    return

3. Selectable list: the positions that can be selected in each row are 0 to n-1, but whether the position can be selected needs to meet the conditions that queens cannot attack each other.

Here, we can judge whether we can attack each other, that is, judge the column where the current position (row, col) is located, and whether there is a queen in the right slash direction, that is, the left slash direction. If so, the queen can no longer be placed in the current position.

There are two ways to judge whether there is conflict:

Method 1: judge directly through circulation

def isVaild(board,row, col):
    #Judge whether the same column conflicts
    for i in range(len(board)):
        if board[i][col] == 'Q':
            return False
    # Determine whether the upper left corner conflicts
    i = row -1
    j = col -1
    while i>=0 and j>=0:
        if board[i][j] == 'Q':
            return False
        i -= 1
        j -= 1
    # Judge whether the right slash direction conflicts
    i = row - 1
    j = col + 1
    while i>=0 and j < len(board):
        if board[i][j] == 'Q':
            return False
        i -= 1
        j += 1
    return True

Method 2: left slash: each point of the same slash has a constant row col; Right slash: row+col at each point of the same slash is constant

The left slash is from top left to bottom right. Each position on the same slash satisfies that the difference between row subscript and column subscript is equal, for example, (0,0) and (3,3) are on the slash in the same direction. Therefore, using the difference between row subscript and column subscript can clearly indicate the slash in each direction.

The right slash is from top right to bottom left. Each position on the same slash satisfies that the sum of row subscript and column subscript is equal. For example, (3,0) (3,0) and (1,2) (1,2) are on the slash in the same direction. Therefore, using the sum of row subscripts and column subscripts can clearly represent the slash in each direction.

Next, we mainly use the second method to judge whether the position is legal.

for i in range(row): #All rows before the loop. If there is a conflict, return False
    for j in range(n):
        # Note: on the left diagonal, each position on the same diagonal satisfies that the difference between row subscript and column subscript is equal
        # Note: on the right diagonal, each position on the same diagonal satisfies that the sum of row subscript and column subscript is equal
        if board[i][j] == 'Q' and (j == col or i + j == row + col or i-j == row-col):
            return False

Final code

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def isValid(row, col):
            # Judge whether the position is legal
            for i in range(row):
                for j in range(n):
                    # Note: on the left diagonal, each position on the same diagonal satisfies that the difference between row subscript and column subscript is equal
                    # Note: on the right diagonal, each position on the same diagonal satisfies that the sum of row subscript and column subscript is equal
                    if board[i][j] == 'Q' and (j == col or i + j == row + col or i-j == row-col):
                        return False
            return True
        def backtrack(board, row):
            if row >= n:
                cur_res = [''.join(row) for row in board]
                res.append(cur_res)
                return
            for i in range(n):
                if isValid(row, i, board):
                    board[row][i] = 'Q'
                    backtrack(board, row+1)
                    board[row][i] = '.'
        res = []
        board = [['.'] * n for _ in range(n)]
        backtrack(board,0)
        return res

Code optimization: judge whether the current point is in the set through the positive diagonal, negative diagonal and column of elements placed before the set record. If it is, it indicates that it does not meet the requirements. This judgment method is faster.

def solveNQueens(self, n: int) -> List[List[str]]:
        def isValid(row, col):
            # If the right slash or left slash or column corresponding to the point has been placed, put it back to Fasle
            if col in col_hash or (row + col) in pie_hash or (row-col) in na_hash:
                return False
            return True
        def backtrack(board, row):
            if row >= n:
                cur_res = [''.join(row) for row in board]
                res.append(cur_res)
                return
            for col in range(n):
                if isValid(row, col, board):
                    board[row][col] = 'Q'
                    pie_hash.add(row + col)
                    na_hash.add(row - col)
                    col_hash.add(col)
                    backtrack(board, row+1)
                    board[row][col] = '.'
                    pie_hash.remove(row + col)
                    na_hash.remove(row-col)
                    col_hash.remove(col)
        res = []
        board = [['.'] * n for _ in range(n)]
        pie_hash = set() # The record places the Queen's right slash
        na_hash = set()  # The record places the Queen's left slash
        col_hash = set() # The Queen's column is placed in the record
        backtrack(board,0)
        return res

If you like the author, you are welcome to like, collect and pay attention, thank you!

Welcome to scan the following QR code to follow the official account: Ashu algorithm and machine learning, and learn and communicate with the author.

Tags: Python Algorithm

Posted by swedee on Mon, 02 May 2022 09:40:04 +0300