Sudoku solver implemented in Python 3

The other day, while surfing the internet, I found the following article: "The most difficult Sudoku in the world" created by a math expert over 3 months .. Whether it's true or not, I tried to solve this with Python3. The backtrack method is used for implementation. In short, it means that you are solving by force (´ ・ ω ・ `)


import itertools

class Sudoku(object):
    def __init__(self):
        self.matrix = [[0 for _ in range(9)] for _ in range(9)] #0 if blank
    
    #Solve a given Sudoku puzzle
    #Fills blank cells one after another, and returns True if all blank cells are filled.(False if not filled)
    def solve(self):
        #Elimination method:Fill in the squares that are unique
        while True:
            ls = []
            for i, j in itertools.product(range(9), repeat=2):
                if self.matrix[i][j] != 0: continue

                numbers = self.__find_numbers(i, j)
                if len(numbers) == 1: ls.append((i, j, numbers[0]))

            if len(ls) == 0: break
            for i, j, number in ls: self.matrix[i][j] = number


        blanks = [(i, j) for i, j in itertools.product(range(9), repeat=2) if self.matrix[i][j] == 0]
        if len(blanks) == 0: return True #If all the squares are already filled

        first_i, first_j = blanks[0]
        stack = [(0, first_number) for first_number in self.__find_numbers(first_i, first_j)]

        #Backtrack method:
        #     1.Put a number in a blank cell
        #     2.Find out if there is a number in the next blank cell
        #     3. 2.In, if it does not enter, back track
        while stack:
            idx, number = stack.pop()
            i, j = blanks[idx]
            self.matrix[i][j] = number

            if idx == len(blanks) - 1: return True

            next_i, next_j = blanks[idx + 1]
            next_numbers = self.__find_numbers(next_i, next_j)

            #Back truck
            if len(next_numbers) == 0:
                stack_top_idx = stack[-1][0]
                for temp_idx in range(stack_top_idx, idx + 1):
                    temp_i, temp_j = blanks[temp_idx]
                    self.matrix[temp_i][temp_j] = 0

            stack.extend((idx + 1, next_number) for next_number in next_numbers)

        return False

    #Store the numbers that can be put in a certain cell in set
    def __find_numbers(self, i, j):
        used_numbers = set()
        #Examine the same row and the same column
        for x in range(9): used_numbers |= {self.matrix[x][j], self.matrix[i][x]}

        #Examine the same block
        box_i_min, box_j_min = (i // 3) * 3, (j // 3) * 3
        for box_i, box_j in itertools.product(range(box_i_min, box_i_min + 3), \
                                              range(box_j_min, box_j_min + 3)):
            used_numbers.add(self.matrix[box_i][box_j])

        return set(range(1, 10)) - used_numbers

    def __str__(self):
        return "\n".join("".join(map(str, row)) for row in self.matrix)

if __name__ == "__main__":
    matrix = '''
        ..53.....
        8......2.
        .7..1.5..
        4....53..
        .1..7...6
        ..32....8.
        .6.5....9
        ..4....3.
        .....97..
    '''.split()

    sudoku = Sudoku()
    for i, j in itertools.product(range(9), repeat=2):
        if matrix[i][j] == ".": continue
        sudoku.matrix[i][j] = int(matrix[i][j])
    
    print(sudoku)
    sudoku.solve()
    print("========")
    print(sudoku)


# 005300000
# 800000020
# 070010500
# 400005300
# 010070006
# 003200080
# 060500009
# 004000030
# 000009700
# =========
# 145327698
# 839654127
# 672918543
# 496185372
# 218473956
# 753296481
# 367542819
# 984761235
# 521839764

The answer is the same as GIGAZINE, so it should be okay (`・ ω ・ ´) Shakin

Recommended Posts

Sudoku solver implemented in Python 3
Sudoku in Python
Implemented SimRank in Python
Implemented Shiritori in Python
6 Ball puzzle implemented in python
Implemented image segmentation in python (Union-Find)
Widrow-Hoff learning rules implemented in Python
Implemented label propagation method in Python
Implemented Perceptron learning rules in Python
Implemented in 1 minute! LINE Notify in Python
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
A simple HTTP client implemented in Python
Meta-analysis in Python
Unittest in python
Implemented in Python PRML Chapter 7 Nonlinear SVM
Epoch in Python
Discord in Python
DCI in Python
quicksort in python
N-Gram in Python
Programming in python
I implemented Cousera's logistic regression in Python
Plink in Python
Constant in python
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
N-gram in python
Implemented in Python PRML Chapter 5 Neural Networks
LINE-Bot [0] in Python
Csv in python
Disassemble in Python
Reflection in Python
Implemented Stooge sort in Python3 (Bubble sort & Quicksort)
Constant in python
nCr in Python.
format in python
Scons in Python3
Puyo Puyo in python
python in virtualenv
PPAP in Python
Implemented in Python PRML Chapter 1 Bayesian Inference
Quad-tree in Python
Reflection in Python
Chemistry in Python
Hashable in python
DirectLiNGAM in Python
LiNGAM in Python
Flatten in python
flatten in python
Implemented in Python PRML Chapter 3 Bayesian Linear Regression
I implemented Robinson's Bayesian Spam Filter in python
Implemented memoization recursion and exploration in Python and Go
Implemented in Python PRML Chapter 1 Polynomial Curve Fitting