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.

image.png Source of figure

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. image.png

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

image.png

Recommended Posts

Solved the world's smallest hint Sudoku with numpy & numba
Find the smallest index that meets the cumulative sum threshold with numpy
2016 The University of Tokyo Mathematics Solved with Python
Find a position above the threshold with NumPy