Solve Sudoku with a depth-first search. The priority of program creation is
I made it in the order of. I sacrifice speed.
It is represented by a general two-dimensional array.
def values_from_grid(grid):
"Create 2D array values from text"
values = []
digits = "123456789"
chars = [c for c in grid if c in digits or c in '0.']
assert len(chars) == 81
grid_int = map(lambda x: int(x) if x != "." else 0, chars)
count = 0
row = []
for i in grid_int:
row.append(i)
count += 1
if count % 9 == 0: #Split line by line
values.append(row)
row = []
return values
A function that reads text and converts it into a two-dimensional array. The text format is a blank represented by 0 or., And other numbers are registered in order. If it is 81 characters, it is OK. It corresponds to the following text formats.
003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300
..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..
8 5 . |. . 2 |4 . .
7 2 . |. . . |. . 9
. . 4 |. . . |. . .
------+------+------
. . . |1 . 7 |. . 2
3 . 5 |. . . |9 . .
. 4 . |. . . |. . .
------+------+------
. . . |. 8 . |. 7 .
. 1 7 |. . . |. . .
. . . |. 3 6 |. 4 .
Check recursively with a depth-first search. How to call
values = values_from_grid(Sudoku data)
solver(values)
is. Pass values to the solver function. After solving, values is an array of answers.
From the upper left cell to the lower right cell, apply the numbers 1 to 9 one by one. At this time, the number is applied only when the number to be applied is not in the "vertical / horizontal / 3x3" square. x is the horizontal axis and y is the vertical axis. When x reaches 8, that is, when it reaches the end of the horizontal axis Check the first cell in the bottom row with the vertical axis down one and the horizontal axis set to 0. When the last cell is reached, the problem is solved and True is returned.
def solver(values, x=0, y=0):
"Solve Sudoku"
if y > 8: #Complete when the pointer reaches the end
return True
elif values[y][x] != 0: #If it is not blank, skip it
if x == 8: #Move to the next row after reaching 8 columns
if solver(values, 0, y+1):
return True
else:
if solver(values, x+1, y):
return True
else:
for i in range(1, 10):#Try all the numbers from 1 to 9
if check(values, x, y, i): #To check
values[y][x] = i #If OK, enter a number
if x == 8: #Move to the next row after reaching 8 columns
if solver(values, 0, y+1):
return True
else:
if solver(values, x+1, y):
return True
values[y][x] = 0 #Return to 0 when returning
return False
The return value is True or False. If you solve it, it is True.
Check the area of horizontal axis, vertical axis, and 3 * 3. A function that calls each function.
def check(values, x, y, i):
if row(values, y, i) and column(values, x, i) and block(values, x, y, i):
return True
return False
Takes the value of the vertical axis indicating the current row as an argument to check the horizontal axis. i is the number you are trying to enter. Check the horizontal axis one by one, and if it is the same as the number you are trying to enter, False, if not Create a list of True and check it with the all function. If all are True, True is returned without duplication of numbers. If there is even one duplicate, False is returned.
def row(values, y, i):
"Check the side"
return all(True if i != values[y][_x] else False for _x in range(9))
I just changed the check on the horizontal axis to the vertical axis.
def column(values, x, i):
"Check vertical"
return all(True if i != values[_y][x] else False for _y in range(9))
The following function was created with reference to Implementing Sudoku solver in Python. Dividing the number from 0 to 8 by 3 and multiplying the value with the decimal point removed by 3 gives 0, 3, and 6, respectively. The theory is that you can see the block to which the square belongs.
def block(values, x, y, i):
"Check 3x3 blocks"
xbase = (x // 3) * 3
ybase = (y // 3) * 3
return all(True if i != values[_y][_x] else False
for _y in range(ybase, ybase + 3)
for _x in range(xbase, xbase + 3))
problem
8 5 . |. . 2 |4 . .
7 2 . |. . . |. . 9
. . 4 |. . . |. . .
------+------+------
. . . |1 . 7 |. . 2
3 . 5 |. . . |9 . .
. 4 . |. . . |. . .
------+------+------
. . . |. 8 . |. 7 .
. 1 7 |. . . |. . .
. . . |. 3 6 |. 4 .
Answer
[8, 5, 9, 6, 1, 2, 4, 3, 7]
[7, 2, 3, 8, 5, 4, 1, 6, 9]
[1, 6, 4, 3, 7, 9, 5, 2, 8]
[9, 8, 6, 1, 4, 7, 3, 5, 2]
[3, 7, 5, 2, 6, 8, 9, 1, 4]
[2, 4, 1, 5, 9, 3, 7, 8, 6]
[4, 3, 2, 9, 8, 1, 6, 7, 5]
[6, 1, 7, 4, 2, 5, 8, 9, 3]
[5, 9, 8, 7, 3, 6, 2, 4, 1]
This program took about 23 seconds in my environment to solve this puzzle. On the other hand, the program in Solve any Sudoku puzzle solves it in 0.01 seconds. This is Solve any Sudoku puzzle says, "If you fill in the squares where you can determine one possible value, the other squares are the same. This is because the strategy of "filling in" is executed, and the squares that are still not filled are searched for only the values that can be taken for each square and the solution is sought. This program checks from 1 to 8 even if only 9 squares are entered, and when checking vertical, horizontal, and 3x3 squares, overlapping squares will occur, but they are also checked individually. doing. So it's slow.
Solve all Sudoku puzzles Implemented Sudoku solver in Python
Recommended Posts