data structure

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.

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

program

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.

Main function

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 function

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

Check the horizontal axis

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))

Check the vertical axis

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))

3x3 check

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))

Execution example

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.

Reference site

Solve all Sudoku puzzles Implemented Sudoku solver in Python

Solve Sudoku with Python