[GO] Solve Sudoku with Python

Solve Sudoku with a depth-first search. The priority of program creation is

  1. Easy
  2. Easy to understand
  3. Early

I made it in the order of. I sacrifice speed.

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.

003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300
..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

Recommended Posts

Solve Sudoku with Python
Solve AtCoder 167 with python
Solve Sudoku with PuLP
Solve POJ 2386 with python
[Python] Solve equations with sympy
Solve AtCoder ABC166 with python
Solving Sudoku with Python (Incomplete)
Solving Sudoku with Python (Part 2)
Solve AtCoder ABC 186 with Python
solver> Link> Solve Excel Solver with python
Solve ABC163 A ~ C with Python
Solve ABC166 A ~ D with Python
Solve AtCoder Problems Recommendation with python (20200517-0523)
Solve ABC168 A ~ C with Python
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
Solve ABC158 A ~ C with Python
FizzBuzz with Python3
Scraping with Python
Scraping with Python
Python with Go
Twilio with Python
Integrate with Python
Sudoku in Python
Play with 2016-Python
AES256 with python
Tested with Python
python starts with ()
with syntax (Python)
Bingo with python
Zundokokiyoshi with python
Excel with Python
Microcomputer with Python
Cast with python
I wanted to solve ABC160 with Python
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
Solve Lake Counting (POJ NO.2386) with Python3
I wanted to solve ABC172 with Python
Serial communication with Python
Zip, unzip with python
Django 1.11 started with Python3.6
Python with eclipse + PyDev.
Socket communication with Python
Data analysis with python 2
Scraping with Python (preparation)
Try scraping with Python.
Learning Python with ChemTHEATER 03
Sequential search with Python
"Object-oriented" learning with python
Handling yaml with python
Serial communication with python
[Python] Use JSON with Python
Learning Python with ChemTHEATER 05-1
Learn Python with ChemTHEATER
Run prepDE.py with python3
Let's solve simultaneous linear equations with Python sympy!
1.1 Getting Started with Python
Collecting tweets with Python
I wanted to solve NOMURA Contest 2020 with Python
Solve ABC146-C in Python