Solved the world's smallest hint Sudoku with numpy & numba
Introduction
I feel like I've solved Sudoku with Python, but I decided to write an article because it would be a code that only exists in my memory. (Most of the reason is that it was a pain to write an article, but I will write it because spring break has been extended for a month in Corona and I have a lot of time.)
policy
Depth-first search. Temporarily enter numbers that satisfy the conditions of Sudoku in the blank cells in ascending order. Temporarily put it in and try the same for other squares. If there is a contradiction somewhere, correct the assumption made immediately before. This is repeated earnestly. Someday the contradiction will not occur and all the blanks will be filled with the assumed values. That is the correct answer.
Implementation
Verify that the assumptions meet the conditions of Sudoku
ʻIndex is counted from 0 to 81 from the upper left to the right. Taking the above figure as an example, the ʻindex of the pink numbers “5, 3, 6, 9, 8” in the upper left 3 × 3 block is “0, 1, 9, 19, 20”, respectively.
def fillable(table, index, value):
"""In the matrix being calculated, verify whether the value assumed to be the correct answer satisfies the Sudoku condition.
Parameters
-------
table : np.ndarray of int
The matrix being calculated. 2D-array。
index : int
The location of the assumed square. 1st line is 0~8,The second line is 9~17, ...
value : int
Assumed number.
Returns
-------
bool
Is it possible that the assumption is correct in the matrix being calculated?
"""
row = index // 9
col = index % 9
fillable_in_row = value not in table[row, :]
fillable_in_col = value not in table[:, col]
fillable_in_block = value not in table[
(row // 3) * 3: (row // 3 + 1) * 3,
(col // 3) * 3: (col // 3 + 1) * 3,
]
return fillable_in_row and fillable_in_col and fillable_in_block
I think it's a fairly natural implementation because it uses only the basic Python syntax.
Assuming
def fill(table_flat):
"""Solve Sudoku by depth-first search.
Parameters
-------
table_flat : np.ndarray of int
Sudoku problem. 1D-array
Returns
-------
np.ndarray of int
A matrix to which assumptions are assigned. shape= (9, 9)
"""
for tmp_i, tmp_val in enumerate(table_flat):
if tmp_val == 0:
fillable_vals = [val
for val in range(tmp_val + 1, 10)
if fillable(table_flat.reshape(9, 9), tmp_i, val)]
for new_val in fillable_vals:
table_flat[tmp_i] = new_val
if fill(table_flat).all():
break
else:
table_flat[tmp_i] = 0
break
return table_flat.reshape(9, 9)
I will explain it line by line.
Consider in order from the square with the smallest index.
for tmp_i, tmp_val in enumerate(table_flat):
I forgot to say it, but I'm assuming that you enter it as question blank cell == 0.
Therefore, this process should be considered only when the cell is blank.
if tmp_val == 0:
A slightly longer list comprehension notation.
The following assumptions should be larger than the current assumptions. However, the assumption that does not meet the conditions of Sudoku is removed. The verification uses the fillable function.
Also, I forgot to mention that ʻindex` is easier to do with numbers than tuples, so the input of the problem is assumed to be a 1x81 vector of a 9x9 matrix (flatten). However, since it is necessary to extract in 3x3 blocks according to the rules, reshape only at this time.
fillable_vals = [val
for val in range(tmp_val + 1, 10)
if fillable(table_flat.reshape(9, 9), tmp_i, val)]
Try substituting the number of possible correct answers into the squares.
for new_val in fillable_vals:
table_flat[tmp_i] = new_val
** This is the liver. ** **
First, the for / else statement will be described. Enters the ʻelse statement when the forstatement ends normally. The case where it does not end normally is when thefor statement is not finished yet but breaks. By the way, even when the for statement runs idle, it ends normally, so it enters the ʻelse statement. So, here you should pay attention to the position of break.
Recurse the assumed matrix as an argument to the fill function. numpy.ndarray.all () returns True if there are no non-zero digits. This time, the blank cell of the problem is set to == 0, so in other words, the behavior of ʻall () is eliminated in Sudoku, that is, when the Sudoku is solved, the for statement is exited.
If it is not solved, return the assumed mass value to 0 and end the examination. If you do return with the value returned to 0, it will be transmitted to ʻif fill (table_flat) .all ():` and the process to correct the assumption will be performed.
for ~~~Abbreviation~~~:
~~~Abbreviation~~~
if fill(table_flat).all():
break
else:
table_flat[tmp_i] = 0
break
return table_flat.reshape(9, 9)
Execution method
It can be executed by arranging the fill function and the fillable function in the same file, and putting the 81st-order vector with Sudoku as one line in the argument of the fill function.
Speeding up (the world's smallest hint problem)
Even at present, ordinary problems can be solved in a few milliseconds to a few seconds. However, he was defeated by a problem. It is the world's smallest hint Sudoku.
When I tried to solve this with the current code, I felt sorry for my computer. I decided to speed up with numba here.
Changes ① import
Numba at the beginning of the file ʻimport`
from numba import njit, int64, bool_
Change (2) Added a decorator
Define input and output types as @ njit (output, input).
** This was the most packed place this time. ** If you want to use numpy.ndarray.reshape (), you need to use ʻint64 [:: 1] . (It was written somewhere in the official numba documentation. [Here](http://numba.pydata.org/numba-doc/0.12.1/tutorial_firststeps.html#signature).) Actually, ʻint8 seems to be good instead of ʻint64, but it didn't work so I left it as the default. (Is it specified as dtype = int8`?)
#A function that inputs a two-dimensional array of ints and two ints and returns a bool
@njit(bool_(int64[:, :], int64, int64))
def fillable(table, index, value):
#A function that inputs a one-dimensional array of int and returns a two-dimensional array of int
@njit(int64[:, :](int64[::1]))
def fill(table_flat):
Change ③ Remove ʻin` operation
numba should support Python syntax quite a bit, but I got an error with the ʻin operation inside the fillable function. (Fillable_in_row = value not in table [row,:]etc.) So I reimplemented thefillable function without using the ʻin operation.
def fillable(table, index, value):
row = index // 9
col = index % 9
block = lambda x: ((x // 3) * 3, (x // 3 + 1) * 3)
same_in_areas = False
for area in [
table[row, :], table[:, col],
table[block(row)[0]:block(row)[1], block(col)[0]:block(col)[1]].flatten()
]:
for i in area:
same_in_areas |= (i == value)
return not same_in_areas
The for statement ʻin seems to be okay. Put the numbers entered in the vertical and horizontal blocks of the square you want to verify in ʻi and turn it. It is verified whether the ʻi matches the assumed value value`, that is, the same number exists in the vertical and horizontal blocks and does not satisfy the Sudoku condition.
In this case, the numba error did not occur.
Whole code
suudoku.py
def fillable(table, index, value):
"""In the matrix being calculated, verify whether the value assumed to be the correct answer satisfies the Sudoku condition.
Parameters
-------
table : np.ndarray of int
The matrix being calculated. 2D-array。
index : int
The location of the assumed square. 1st line is 0~8,The second line is 9~17, ...
value : int
Assumed number.
Returns
-------
bool
Is it possible that the assumption is correct in the matrix being calculated?
"""
row = index // 9
col = index % 9
fillable_in_row = value not in table[row, :]
fillable_in_col = value not in table[:, col]
fillable_in_block = value not in table[
(row // 3) * 3: (row // 3 + 1) * 3,
(col // 3) * 3: (col // 3 + 1) * 3,
]
return fillable_in_row and fillable_in_col and fillable_in_block
def fill(table_flat):
"""Solve Sudoku by depth-first search.
Parameters
-------
table_flat : np.ndarray of int
Sudoku problem. 1D-array
Returns
-------
np.ndarray of int
A matrix to which assumptions are assigned. shape= (9, 9)
"""
for tmp_i, tmp_val in enumerate(table_flat):
if tmp_val == 0:
fillable_vals = [val
for val in range(tmp_val + 1, 10)
if fillable(table_flat.reshape(9, 9), tmp_i, val)]
for new_val in fillable_vals:
table_flat[tmp_i] = new_val
if fill(table_flat).all():
break
else:
table_flat[tmp_i] = 0
break
return table_flat.reshape(9, 9)
suudoku_faster.py
from numba import njit, int64, bool_
@njit(bool_(int64[:, :], int64, int64))
def fillable(table, index, value):
row = index // 9
col = index % 9
block = lambda x: ((x // 3) * 3, (x // 3 + 1) * 3)
same_in_areas = False
for area in [
table[row, :], table[:, col],
table[block(row)[0]:block(row)[1], block(col)[0]:block(col)[1]].flatten()
]:
for i in area:
same_in_areas |= (i == value)
return not same_in_areas
@njit(int64[:, :](int64[::1]))
def fill(table_flat):
for tmp_i, tmp_val in enumerate(table_flat):
if tmp_val == 0:
fillable_vals = [val
for val in range(tmp_val + 1, 10)
if fillable(table_flat.reshape(9, 9), tmp_i, val)]
for new_val in fillable_vals:
table_flat[tmp_i] = new_val
if fill(table_flat).all():
break
else:
table_flat[tmp_i] = 0
break
return table_flat.reshape(9, 9)
suudoku_input.py
from suudoku import fill as fill_slow
from suudoku_faster import fill as fill_fast
import matplotlib.pyplot as plt
import numpy as np
from time import time
table = [0, 0, 0, 8, 0, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 4, 3, 0,
5, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 7, 0, 8, 0, 0,
0, 0, 0, 0, 0, 0, 1, 0, 0,
0, 2, 0, 0, 3, 0, 0, 0, 0,
6, 0, 0, 0, 0, 0, 0, 7, 5,
0, 0, 3, 4, 0, 0, 0, 0, 0,
0, 0, 0, 2, 0, 0, 6, 0, 0]
#The first lap of numba includes not only the calculation time but also the compile time, so let it run idle once.
fill_fast(np.array(table).copy())
start = time()
ans = fill_fast(np.array(table).copy())
finish = time()
print("answer")
print(ans)
print()
print(f"Calculation time(sec): {finish - start:5.7}")
fig, ax = plt.subplots(figsize=(6, 6))
fig.patch.set_visible(False)
ax.axis("off")
colors = np.where(table, "#F5A9BC", "#ffffff").reshape(9, 9)
picture = ax.table(cellText=ans, cellColours=colors, loc='center')
picture.set_fontsize(25)
picture.scale(1, 3)
ax.axhline(y=0.340, color="b")
ax.axhline(y=0.665, color="b")
ax.axvline(x=0.335, color="b")
ax.axvline(x=0.665, color="b")
fig.tight_layout()
plt.show()
output
If it's a normal problem, it takes about 0.01 seconds, but what kind of problem takes 100 seconds ... By the way, this world's most difficult Sudoku can be solved normally.
answer
[[2 3 4 8 9 1 5 6 7]
[1 6 9 7 2 5 4 3 8]
[5 7 8 3 4 6 9 1 2]
[3 1 6 5 7 4 8 2 9]
[4 9 7 6 8 2 1 5 3]
[8 2 5 1 3 9 7 4 6]
[6 4 2 9 1 8 3 7 5]
[9 5 3 4 6 7 2 8 1]
[7 8 1 2 5 3 6 9 4]]
Calculation time(sec): 101.6835
