[PYTHON] Try to solve Sudoku at explosive speed using numpy
What is Sudoku?
Sudoku is one of the pencil puzzles that puts numbers from 1 to 9 in a 9x9 square frame divided into 3x3 blocks. Also called "Number Place (Sudoku)". (From Wikipedia)
It seems.
Of course, it does not fill in the numbers without thinking, and it has the following restrictions.
--The same number must not exist in one column --The same number must not exist in one line --The same number must not exist in one block
(I borrowed it from a site that summarizes interesting and useful things in mathematics)
I wanted to make this a problem for juniors who are new to programming, but I will write it because there were few articles that were unexpectedly written.
policy
Well, it simply does the same thing as humans.
Consider the following Sudoku.
For example, if you look for 1, you would ** find a place where only 1 can fit in each column, row, and block **.
We will set a flag that each number exists for each cell, and code the work of finding columns, rows, and blocks for which the total number of flags is 1.
For each square, there is a specific number
- Mass that may exist ... 1
- A cell that may not exist ... 0
In Sudoku, you can set the existence flag for "1" as follows. (Hereafter, a two-dimensional array that follows these rules is called a layer.) Below is an image. (Red and number squares ... 0, green ... 1)
Then calculate the total for each row, each column, each block. With this, when the total becomes 1, the number will be confirmed **.
In this example, you can find exactly three places to update. 
In this way, it seems that it can be solved easily just by introducing the existence flag.
Now, let's actually write the code.
Check each line
def check_row(layer):
rows = np.where(np.sum(layer, axis=1)==1)[0]
w = np.where(layer[rows] == 1)
cols = w[1][np.argsort(w[0])]
return rows, cols
In this way, basically np.sum and np.where are used to extract the cells that meet the conditions.
Check each column
The same is true for columns.
def check_col(layer):
cols = np.where(np.sum(layer, axis=0)==1)[0]
w = np.where(layer[:,cols] == 1)
rows = w[0][np.argsort(w[1])]
return rows, cols
Check each grid
def check_grid(layer):
rows, cols = list(), list()
for row in range(3):
for col in range(3):
grid = self.layer[row*3:(row+1)*3, col*3:(col+1)*3 ]
if np.sum(grid) == 1:
point = np.where(grid==1)
rows.append(point[0][0]+row*3)
cols.append(point[1][0]+col*3)
return rows, cols
Operation check
Now, let's try the functions up to this point.
layer = np.array([[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 1, 1, 0, 0, 0],
[1, 0, 0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 1, 0, 1]])
print(check_row(layer))
#(array([3], dtype=int64), array([5], dtype=int64))
print(check_col(layer))
#(array([8], dtype=int64), array([6], dtype=int64))
print(check_grid(layer))
#([4], [8])
It's working well.
Check each layer
Well, actually it works already, but since it's a big deal, I'll add another function.
Until now, we've only focused on one layer. However, Sudoku is made up of nine numbers, 1-9, so you should consider comparing the layers. In other words, ** in any cell, if the existence flag is set across each layer in only one layer, the location can be determined **.
def check_all_layer(layers):
nums = list()
sum_map = np.sum(layers, axis=0)
if np.any(sum_map==1):
rows, cols = np.where(sum_map==1)
for row, col in zip(rows, cols):
idx = np.where(layers[:,row,col])[0][0]
nums.append(idx+1)
return rows, cols, nums
layers = np.zeros((9,9,9))
layers[3,5,7] = 1
print(check_all_layer(layers))
#(array([5], dtype=int64), array([7], dtype=int64), [4])
Update when a number is assigned
When the numbers are finalized, the layers must be updated as well. Considering a 9x9x9 3D array layer, the function to update the layer can be written as:
def update(layers, idx, row, col):
layers[idx,row, : ] = 0 #Row direction
layers[idx, : ,col] = 0 #Column direction
layers[ : ,row,col] = 0 #Layer direction
row, col = row//3*3, col//3*3
layers[idx, row:row+3, col:col+3] = 0 #range
Finally
I haven't verified it at all because it's just a little code I wrote when I was excited about talking with my seniors in Sudoku () If you have any mistakes, please contact me.
Thank you for reading to the end.
Actual code
Since it was implemented in a class, it is slightly different from the above code, but with this, Sudoku can be solved in about 0.01 seconds.
I wrote it in glue, so I haven't confirmed the operation at all, but it probably works.
sudoku.py
class sudoku_solver(object):
def __init__(self, question):
self.p = np.array(problem)
self.layer = np.ones((9,9,9))
self.__init_layer()
self.update_list = list()
def solve(self):
count=0
while np.sum(self.layer)!=0 or count<100:
for i in range(9):
self.check_row(i)
self.check_col(i)
self.check_grid(i)
self.check_all_layer()
self.__update()
count+=1
#Update function
def __update(self):
for idx, row, col in self.update_points:
self.__update_point(idx, row, col)
self.update_points=list()
def __update_point(self, idx, row, col):
#Answer update
self.p[row, col] = idx+1
#Layer update
self.layer[idx,row, : ] = 0 #Row direction
self.layer[idx, : ,col] = 0 #Column direction
self.layer[ : ,row,col] = 0 #Layer direction
row, col = row//3*3, col//3*3
self.layer[idx, row:row+3, col:col+3] = 0 #range
#Layer initialization function
def __init_layer(self):
for idx in range(9):
(rows, cols) = np.where(self.p==idx+1)
for row, col in zip(rows, cols):
self.__update_point(idx, row, col)
#Row confirmation function
def check_row(self, idx):
rows = np.where(np.sum(self.layer[idx], axis=1)==1)[0]
w = np.where(self.layer[idx][rows] == 1)
cols = w[1][np.argsort(w[0])]
for row, col in zip(rows, cols):
self.update_list.append((idx, row, col))
#Column confirmation function
def check_col(self, idx):
cols = np.where(np.sum(self.layer[idx], axis=0)==1)[0]
w = np.where(self.layer[idx][:,cols] == 1)
rows = w[0][np.argsort(w[1])]
for row, col in zip(rows, cols):
self.update_list.append((idx, row, col))
#Range confirmation function
def check_grid(self, idx):
for row in range(3):
for col in range(3):
grid = self.layer[idx, row*3:(row+1)*3, col*3:(col+1)*3 ]
if np.sum(grid) == 1:
point = np.where(grid==1)
row = point[0][0]+row*3
col = point[1][0]+col*3
self.update_list.append((idx,row,col))
#Layer orientation confirmation function
def check_all_layer(self):
sum_map = np.sum(self.layer, axis=0)
if np.any(sum_map==1):
rows, cols = np.where(sum_map==1)
for row, col in zip(rows, cols):
idx = np.where(self.layer[:,row,col])[0][0]
self.update_list.append((idx,row,col))
Recommended Posts