Sudoku programming: Classic Backtracking Problem

It was 2018, and the source code I mentioned in this post can be accessed in https://github.com/BenLin0/sudoku

That day my wife had problem with the sudoku game she was working on. So I said:" Let me make a program for you."

The first program was pretty simple, and you can get it from the commit history of the mentioned github: https://github.com/BenLin0/sudoku/blob/44acde0d2a5c06c5b69dbbf74c680214e7e9533b/sudoku.py 

 The first step is to design the input format of the sudoku file, such as:

 ,8,5,1,3, , , , 
 , , , ,4,7, , ,6
 , ,9, , , , , ,7
 , , , , ,8,3,7,5
 , ,8, , , , ,6, 
2, , , , , , , , 
 , ,7,8, ,3, ,9, 
5, , , ,7, , , , 
 , , ,2,5, , , , 

(Original Sudoku game)

In theory, if you are building a modern phone app for sudoku, you would be using the camera to snap the picture of a paper-printed sudoku and get the input feed into the program, in the same way I just designed.

With this design, I can easily read the sudoku in to a 2D array, or a list of list, as saying in Python:

board=[]
def loadsudoku(filelocation):
    with open(filelocation, encoding="utf-8") as sudokufile:
            for line in sudokufile:
                if line.startswith("#"):
                    continue    #comment line
                if line.strip():
                    col = line.split(",")
                    column = [int(x.strip()) if x.strip() else 0 for x in col ]
                    board.append(column)

Now the board to the sudoku is ready, the next step is to try each number in each empty cell, using brute-force recursive function. 

def trysudoku(x, y):
    while board[x][y] != 0:
        x, y = getnext(x, y)
        if y == 9:
            return  1   # get to the 10th line, so this is the end!
    for trynum in [1, 2, 3, 4, 5, 6, 7, 8, 9]:   
        if conflict(board, x, y, trynum):
            continue
        board[x][y] = trynum
        nextx, nexty = getnext(x,y)
        if nexty == 9:
            return  1   #end!
        result = trysudoku(nextx, nexty)
        if result == 1:
            return 1
        else:
            board[x][y] = 0  # clean it, for the next trynum.
    return -1   #failed after trying all [1..9] number in this [x,y] position.

There are 2 support functions here: getnext() and conflict(). The getnext() is to get the next cell. We try to get the next cell in the same row; if we get to the end of the row, we will get the first cell of next row. The conflict() function is to test whether the new number is able to by apply to the current cell, whether it conflict with the known cells of the current row, current column, and column block.

So, this program is completed, when a new sudoku board is given, every number is tried in the cells from top left corner to bottom right corner brute-forcely. If a conflict is found for the current cell, we try a bigger number; if all [1..9] numbers are tried, we backtrack to previous cell to try another number. There are 2 possible results:

1, We successfully fill all the cells, now getnext() get to the 10th row ( y == 9 in the program). return 1.

2, We already backtrack to the first level, tried all the possible numbers [1...9] but failed. return -1.

Pretty classic backtracking algorithm. Mission complete. 

As I presented this program to my wife, and showed her how it worked, she disliked it. She said:"Any robot can do that. What I need is some logic thinking to support me when I am stuck in some steps." 

So I have to update my program to add some logic into the already-logically-perfect program. To be continue.