Solving Sudoku with Python (Incomplete)

Recently I'm addicted to solving Sudoku in smartphone games. When solving with paper and pen, find the squares that may contain numbers and apply the numbers to them. When solving with a device such as a smartphone, after substituting all the numerical values for all the squares, search for the squares that are unlikely to contain the same numerical value and delete the numerical values. It is faster to think by "subtraction".

I always solve it with that method, but I wrote a program and tried to see if the method could solve any problem algorithmically (?) Every time. From the conclusion, there were some problems that could not be solved, so if you want to build a program that can be solved without fail, we recommend that you consider a brute force method of substituting in order from one end. (See below)

How to solve (image)

First of all, if there was such a problem (1) Substitute all numbers once for all cells for which the numbers have not been determined. (2) Pay attention to each of the determined elements, and erase the numbers vertically, horizontally, and from within the 3x3 square where the numbers exist. (This figure is after operating on the "1" in the middle left. Repeat this for all determined numbers.) ③ This time, pay attention to the vertical, horizontal, and 3x3, and enter the value that can only be entered in that element as the decision value. (In the case of this figure, "1" is determined here because there is only one "1" in the upper left 3x3.) ④ Repeat these operations.

Implement this programmatically.

code

sudoku_solver.py

import numpy as np
import copy

xx = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x1 = [1]
x2 = [2]
x3 = [3]
x4 = [4]
x5 = [5]
x6 = [6]
x7 = [7]
x8 = [8]
x9 = [9]

lists = [
[copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x4), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx)],
[copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x5), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx)],
[copy.deepcopy(xx), copy.deepcopy(x3), copy.deepcopy(x6), copy.deepcopy(x8), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x7), copy.deepcopy(x2)],
[copy.deepcopy(xx), copy.deepcopy(x8), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x6), copy.deepcopy(x5), copy.deepcopy(xx), copy.deepcopy(xx)],
[copy.deepcopy(x1), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x5), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x9), copy.deepcopy(xx)],
[copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x2), copy.deepcopy(xx), copy.deepcopy(x7)],
[copy.deepcopy(xx), copy.deepcopy(x1), copy.deepcopy(xx), copy.deepcopy(x2), copy.deepcopy(xx), copy.deepcopy(x8), copy.deepcopy(x4), copy.deepcopy(x3), copy.deepcopy(x6)],
[copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x8), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x4), copy.deepcopy(x7), copy.deepcopy(xx), copy.deepcopy(x9)],
[copy.deepcopy(xx), copy.deepcopy(x6), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x1), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(xx), copy.deepcopy(x5)],
]

cells = np.array(lists)
flags = np.zeros((9, 9))
grid = [(0, 3), (3, 6), (6, 9)]

while np.any(flags==0):
    for i, ii in enumerate(cells):
        for j, jj in enumerate(ii):
            if len(jj) == 1 and flags[i, j] == False:
                num = jj[0]
                flags[i, j] = True
                #Search vertically, horizontally, and direction, and delete the same number
                for kk in cells[i]:
                    if num in kk and len(kk) != 1:
                        kk.remove(num)
                for kk in cells[:, j]:
                    if num in kk and len(kk) != 1:
                        kk.remove(num)
                #Delete the same number in 3x3
                if i < 3:
                    l = 0
                elif i >= 3 and i < 6:
                    l = 3
                elif i >= 6 and i < 9:
                    l = 6
                if j < 3:
                    d = 0
                elif j >= 3 and j < 6:
                    d = 3
                elif j >= 6 and j < 9:
                    d = 6
                for ll in cells[l:l+3, d:d+3]:
                    for mm in ll:
                        if num in mm and len(mm) != 1:
                            mm.remove(num)

    for ii in range(1, 10):
        #Search vertically, horizontally, and direction, and decide if only one number is entered
        for jj in range(0, 9):
            counter1 = 0
            counter2 = 0
            marker1 = 0
            marker2 = 0
            for kk in range(0, 9):
                if ii in cells[jj, kk]:
                    counter1 += 1
                    marker1 = kk
                if ii in cells[kk, jj]:
                    counter2 += 1
                    marker2 = kk
            if counter1 == 1:
                cells[jj, marker1].clear()
                cells[jj, marker1].append(ii)
            if counter2 == 1:
                cells[marker2, jj].clear()
                cells[marker2, jj].append(ii)

        #Search within 3x3 and decide if only one number is entered
        for jj in grid:
            for kk in grid:
                counter3 = 0
                marker3 = 0
                marker4 = 0
                for mm, ll in enumerate(cells[jj[0]:jj[1], kk[0]:kk[1]]):
                    for oo, nn in enumerate(ll):
                        if ii in nn:
                            counter3 += 1
                            marker3 = mm
                            marker4 = oo
                if counter3 == 1:
                    cells[jj[0]+marker3, kk[0]+marker4].clear()
                    cells[jj[0]+marker3, kk[0]+marker4].append(ii)

    #Creating an array for print
    num_list = []
    for ii in cells:
        _num_list = []
        for jj in ii:
            if len(jj) == 1:
                _num_list.append(jj[0])
            else:
                _num_list.append(0)
        num_list.append(_num_list)
print("---------------------------")
for ii in num_list:
    print(ii)
print("---------------------------")

One of my goals was to practice using numpy, so I'm using it for the time being. For a 3D array that has a list containing 1 to 9 in 9x9, whether the numerical value of the cell has been determined (whether the length of the 3D array is 1) and execute the operation of ② The problem is solved while managing with a 9x9 two-dimensional array that manages whether or not it has been completed with True-False.

Execution result

Here is the result of the execution.

---------------------------
[2, 7, 1, 6, 4, 3, 9, 5, 8]
[8, 9, 5, 1, 7, 2, 3, 6, 4]
[4, 3, 6, 8, 9, 5, 1, 7, 2]
[7, 8, 3, 9, 2, 6, 5, 4, 1]
[1, 4, 2, 5, 8, 7, 6, 9, 3]
[6, 5, 9, 4, 3, 1, 2, 8, 7]
[9, 1, 7, 2, 5, 8, 4, 3, 6]
[5, 2, 8, 3, 6, 4, 7, 1, 9]
[3, 6, 4, 7, 1, 9, 8, 2, 5]
---------------------------

Finally

It seems that there are problems that cannot be solved with this logic alone, and while trying to solve such problems keeps spinning. I found out by examining this time, but it seems that there are various solutions in Sudoku, and it seems that something is not enough with this solution (I do not know what it is.) This time, the purpose was not to solve all the problems in Sudoku, so I just checked it for the time being. If you want to finish the continuation, I think the following will be helpful. For the time being, I think it will be finished faster than brute force.

How to solve Sudoku / Advanced

I just want to solve any problem! As mentioned at the beginning, it is recommended to use the following brute force method.

Sudoku in Python

Also, this time I only solved it normally, but that alone is not interesting, so I tried to recognize the problem from images and photos and solve it. Next time I will write about that area.