Shulou(Shulou.com)06/01 Report--

This article mainly explains "how to use Python to solve Sudoku". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to use Python to solve Sudoku.

1. Introduction

The name Sudoku comes from the Japanese phrase suuji wa dokushin ni kagiru, which means "numbers must be kept single". The popularity of Sudoku games also stems from the simplicity of its rules: Sudoku games require numbers to be filled in on a grid of 9 x 9 spaces. There are 9 "square" grid block (consisting of 3 x 3 subcells cell) in rows and columns. The numbers 1-9 are required for every row, column and block, and no number must be repeated in the row, column or block.

OK, now that we know the above rules of Sudoku, let's go straight to the subject. :)

two。 Describe Sudoku's nine palace grid.

This step is mainly to initialize our ninth grid with a set of numbers. We use the setBoard () function to convert the input to a data type suitable for our subsequent operations. We use the following convention:

The empty cell cell is initialized to the default value of 0.

The data type that maintains the numerical values of the Sudoku puzzle is a 9x9-sized two-dimensional list.

Here our input is a multiline string, which we process into a two-dimensional list. The sample code is as follows:

# Initialize a 2murd list with initial values described by the problem. # Returns boarddef setBoard (): board = list () sudokuBoard =''200080300 060070084 030500209 105408 000000000 402706000 301007040 720040060004010003' 'rows = sudokuBoard.split (\ n') for row in rows: column = list () for character in row: digit = int (character) column .append (digit) board.append (column) return board

After the above code is run, if it is shown in a jigsaw puzzle, it will look like this:

3. Find the next empty subcell

The operation of the function findEmpty () function is simpler: the initialized nine-house cell is passed as an argument, and then the cell of each child cell in the nine-house cell is traversed until the first empty child cell returned is found. If an empty child cell is not found, it indicates that our problem has been solved, so it returns None.

The sample code is as follows:

# Find next empty space in Sudoku board and return dimensionsdef findEmpty (board): for row in range (9): for col in range (9): if board [row] [col] = 0: return row,col return None4. The validity of setting values in subcells

The operation of the function isValid () is to confirm whether the set number is a valid option for the ninth house cell. In order to make the set value meet the requirements of Sudoku Nine Palace Grid, the setting of this value must meet the following conditions:

Any subcell cell of the same row should not contain this number

Any subcell cell of the same column should not contain this number

The block in which the subcell cell is located should not contain this number

If the value we set satisfies all the above conditions, the function returns True, otherwise it returns False. The code is as follows:

# Check whether a specific number can be used for specific dimensionsdef isValid (board, num, pos): row Col = pos # Check if all row elements include this number for j in range (9): if board [row] [j] = = num: return False # Check if all column elements include this number for i in range (9): if board [I] [col] = = num: return False # Check if the number is already included in the block rowBlockStart = 3* (row / / 3) colBlockStart = 3* (col / / 3) rowBlockEnd = rowBlockStart + 3 colBlockEnd = colBlockStart + 3 for i in range (rowBlockStart RowBlockEnd): for j in range (colBlockStart, colBlockEnd): if board [I] [j] = = num: return False return True

The following is a dynamic example of successfully inserting a new value through the conditions described in the isValid () function:

At the same time, if we introduce a value that conflicts with a value that already exists on the ninth grid Sudoku, the value will not be inserted at this time. The illustration is as follows:

5. Implement backtracking algorithm

The next function is the core idea of our whole solution. The idea of backtracking is introduced here. The implementation steps of the algorithm are as follows:

Search for the next empty subcell cell. If it is not found, then we have solved the problem; if not, go to step 2.

Guess the correct number by iterating through the numbers 1-9, and refer to the number that has been determined to check whether it is a legal number.

If a valid number is found, the solve () function is called recursively at this time and the next empty subcell cell is guessed.

If the numbers 1-9 are invalid, the value of the subcell cell is reset to 0 and iterations continue to find the next significant number.

# Solve Sudoku using backtrackingdef solve (board): blank = findEmpty (board) if not blank: return True else: row, col = blank for i in range (1Magne 10): if isValid (board, I, blank): board [row] [col] = i if solve (board): return True board [row] [col] = 0 return False

Since recursion is not so intuitive to understand, let's try to use dynamics to visualize the whole process:

As we saw in the example above, the algorithm fills the empty subcell cell with valid numbers until there is a dead end; then it backtracks until the process is re-iterated.

6. Performance performance

Above our program needs to use the backtracking algorithm to traverse many potential values of each cell. This is certainly not the optimal solution, and it can be expected that the performance of our solution will be very slow.

We use the above code to solve the 50 Sudoku problems in question 96 of the Euler plan, and the running time is:

The execution time of above program is: 23.56185507774353 s so far, I believe you have a deeper understanding of "how to use Python to solve Sudoku". You might as well do it in practice! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.