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

数独の解答.jpg (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. 20090929101557.jpg

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

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)

asdfvar.jpg

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. fdvrvravger.jpg

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

Try to solve Sudoku at explosive speed using numpy
Try multivariable correlation analysis using Graphical lasso at explosive speed
Create machine learning projects at explosive speed using templates
Try to solve Sudoku in various ways (SAT, CSP)
Implement APIs at explosive speed using Django REST Framework
I want to solve Sudoku (Sudoku)
Build a web API server at explosive speed using hug
Try using pynag to configure Nagios
Try to get statistics using e-Stat
Try to solve the function minimization problem using particle swarm optimization
Stack problem: Try to solve "20. Valid Parentheses"
Try to detect fusion movement using AnyMotion
Try to operate Excel using Python (Xlwings)
I tried to let optuna solve Sudoku
Try to download Youtube videos using Pytube
Try to solve the fizzbuzz problem with Keras
How to create large files at high speed
Try using django-import-export to add csv data to django
Python template for log analysis at explosive speed
Try to solve the Python class inheritance problem
Try to separate Controllers using Blueprint in Flask
How to speed up scikit-learn like conda Numpy
Try to solve the man-machine chart with Python
I tried using PyCaret at the fastest speed
Try to create an HTTP server using Node.js
Every time I try to read a csv file using pandas, I get a numpy error.