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

This article mainly introduces "how to use Python to solve Sudoku". In daily operation, I believe many people have doubts about how to use Python to solve Sudoku problems. I have consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts about "how to use Python to solve Sudoku problems". Next, please follow the editor to study!

1. Introduction

On the basis of the previous solution, this paper mainly considers how to improve the performance of the Sudoku problem solving algorithm.

Cut the gossip and let's get started. :)

two。 Review the previous article

First of all, let's review the previous backtracking algorithm, which is shown below:

In the previous article, we introduce a backtracking algorithm to solve the Sudoku problem, and solve the problem violently by iterating over all possible values of each subcell cell until there is no conflict between the new values in the Sudoku grid and the determined values in the subcells belonging to the same row, column or block block. Although this solution can effectively solve the problem, it is by no means the best solution because it does not make rational use of the additional prior information provided in the Sudoku grid. Next, let's optimize the previous algorithm step by step.

3. Reduce the number of non-essential iterations

The first idea to optimize the above algorithm comes from the observation that our algorithm iterates over all the numbers 1 through 9 sequentially until it finds a value that does not conflict with another cell in the same row, column, or block block that already contains the same value. However, some certain values in Sudoku have already provided us with some information about which numbers cannot be added to a subcell cell.

# 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

Our optimization idea is to scan our Sudoku grid first, keep all possible legitimate candidates for each subcell in memory, and then iterate over them one by one, instead of iterating over all the numbers. Referring to the figure below, the set of candidate values of two subcells of Sudoku's nine grid is demonstrated. As our rules of the game imply, every row, column, and block block cannot contain the same number, so in the same row that belongs to a given child cell, all numbers that have been determined in the column and the cell of the block block are excluded.

Now that we have an optimization idea, we can then use code to achieve the above idea.

3.1 generate candidate value dictionary

Then we need a data structure (here we choose a dictionary) to hold the list of candidate values for each subcell. This function returns the list of candidate values for each subcell by traversing the empty subcells throughout the nine-house cell and calling our allowedValues () function.

The sample code is as follows:

# Store in a dictionary the legitimate # values for each individual celldef cacheValidValues (board): cache = dict () for i in range (9): for j in range (9): if board [I] [j] = 0: cache [(board,i,j j)] = allowedValues (board,i,j) return cache3.2 generate a list of candidate values

The allowValues () function in the previous section has similar logic to the isValid () function we saw in the previous article, but in this case, it returns a list of legal numbers extracted by each subcell.

The sample code is as follows:

Def allowedValues (board,row Col): numbersList = list () for number in range (1mem10): found = False # Check if all row elements include this number for j in range (9): if board [row] [j] = = number: found = True break # Check if all column elements include this number if found = = True: continue else: For i in range (9): if board [I] [col] = = number: found = True break # Check if the number is already included in the block if found = = True: continue else: 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] = = number: found = True break if found = = False: numbersList.append (number) return numbersList3.3 function call

With our cell candidate cache dictionary we are going to test whether this scheme will significantly improve our program performance.

To do this, we also need to replace the solve () function with a new function, solveWithCache (), which iterates over only the list of legal values for each subcell cell, not all the digits 1mer 9.

The code is as follows:

Def solveWithCache (board, cache): blank = findEmpty (board) if not blank: return True else: row,col = blank for value in cache [(row,col)]: if isValid (board, value, blank): board [row] [col] = value if solveWithCache (board, cache): return True board [row] [col] = 0 return False

Testing our code after implementing all the changes provides us with the results we need, and running the same 50 sets of test cases takes significantly less time than our first version:

The execution time of above program is: 15.41820478439331 s so far, the study on "how to use Python to solve Sudoku" is over. I hope I can solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.