Solve Sudoku puzzles with Google or tools

Sudoku is a common intelligence game , The rule is : In a 9×9 Fill in the grid of 81 individual 1 to 9 The number of , It is required that the number of each line cannot be repeated , The numbers in each column cannot appear again , At the same time 9×9 The large grid is divided into 9 individual 3×3 The small grid of requires that the numbers in each small grid cannot be repeated . At the beginning of the game, several numbers have been filled in the big grid , Ask the participants of the game to fill in the remaining numbers, as shown in the figure below ：

Today we use google or-tools Modeling language of cp_model To crack mobile phone app Sudoku on enjoy sudoku The one with the highest difficulty level maelstorm Level Sudoku puzzle ：

Before modeling , We must first clarify the rules of Sudoku , We just need to tell the rules of the game cp_model, As for how to crack it, we don't need to worry ,cp_model I'll help you with everything . Reconfirm the rules of the game ：  

1. stay 9×9 In the big grid ： Each row 、 Each column of elements cannot be repeated .  
2. stay 3×3 In the small grid of ： All elements cannot be repeated .

 

Initialize variable

After clarifying the rules of the game , We first need to define the size of large grid and small grid in the code , And a Sudoku grid to be cracked , For elements without numbers, we will use 0 Instead of ：

from ortools.sat.python import cp_model
model = cp_model.CpModel()

# Small grid size 
cell_size = 3
# Large grid per row , Size of each column 
line_size = cell_size**2

line = list(range(0, line_size))
cell = list(range(0, cell_size))

# Sudoku grid to be cracked 
initial_grid = [[2, 8, 1, 0, 0, 0, 0, 0, 0],
                [7, 9, 6, 1, 0, 4, 0, 3, 5],
                [5, 3, 4, 6, 0, 0, 0, 0, 0], 
                [3, 4, 0, 8, 0, 0, 6, 9, 7],
                [8, 1, 0, 7, 0, 6, 0, 5, 0], 
                [6, 7, 0, 0, 0, 0, 0, 8, 1],
                [0, 0, 7, 0, 0, 8, 0, 2, 0], 
                [1, 2, 8, 3, 0, 7, 5, 4, 0],
                [0, 0, 3, 2, 0, 0, 7, 0, 8]]

Define grid variables

Next we will define a 9×9 Large grid variables , It is used to store all the numbers in the grid after cracking , Then assign the initial value to the grid variable ：

# Define the grid variables that store the cracking results 
grid = {}
for i in line:
    for j in line:
        grid[(i, j)] = model.NewIntVar(1, line_size, 'grid %i %i' % (i, j))  
        
# Initialize grid variables 
for i in line:
    for j in line:
        if initial_grid[i][j]:
            model.Add(grid[(i, j)] == initial_grid[i][j])  

Add game rules

Next we will tell the rules of the game cp_model, And add the constraints of the game rules to the grid variables ：

1. Row constraint ： The elements of each line are different .
2. Column constraints : The elements of each column are different .
3.cell( Little grid ) constraint : Every cell The elements inside are different .

# Row constraint ：  The elements of each line are different 
for i in line:
    model.AddAllDifferent([grid[(i, j)] for j in line])  
    
# Column constraints :  The elements of each column are different 
for j in line:
    model.AddAllDifferent([grid[(i, j)] for i in line])  
    

#cell constraint :  Every cell The elements inside are different 
for i in cell:
    for j in cell:
        one_cell = []
        for di in cell:
            for dj in cell:
                one_cell.append(grid[(i * cell_size + di,
                                      j * cell_size + dj)])

        model.AddAllDifferent(one_cell) 

solve

After setting the rules of the game , We can make or-tools To complete the rest of the solution process for us , It's that simple ！ Finally, our program only takes time 3 The Sudoku game was cracked in milliseconds .

%%time
#  solve 
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
    for i in line:
        print([int(solver.Value(grid[(i, j)])) for j in line])

Reference material ：

The above code comes from ：https://github.com/google/or-tools/blob/master/examples/python/sudoku_sat.py