Sudoku programming: Advance reasoning

The preset() function in the previous blog is not powerful enough to solve many existing sudoku games, if any at all. After going back to study how my wife solve the games, and discussed with some sudoku hobbyists, a new reasoning logic is added into the program. It is the last version in https://github.com/BenLin0/sudoku as this blog is being written.

I added the new logic into the existing program as a standalone function SetPossibleNumbers(). If I refactor the code, some part of it can be combined into the previous preset() function, or the function name should be renamed better to reflect the true functionality of it.

In this new SetPossibleNumbers(), I took advantage of the dynamic typing of Python, to give a set of possible values for each empty (undecided) cell:

    for i in range(9):
        for j in range(9):
            if board[i][j] != 0 and type(board[i][j]) is int :
                continue
            board[i][j] = set()
            for trynum in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
                if not conflict(board, i, j, trynum):
                    board[i][j].add(trynum)

With the support of knowing possible numbers of each cell, this reasoning logic is deployed:

If in one row there are 2 cells exclusively can only have 2 possible numbers, such as (3,6) in cell 1, and (3,6) in cell 2, then we know number 3 and number 6 can only be in these two cells, not in any other cells of the same row. Then I can remove these 2 numbers from the possible value of other cells.

Of course, the same column, the same block can apply the same rule too.

The number "2" in this reasoning rule can be change to any number n. For example, if in a row , cell 1 has possible values (6, 7, 8), cell 2 has possible values (6, 7), cell 3 has possible values (7, 8), then we know the number 6, 7, 8 are exclusively in these 3 cells, then they can't be in other cells.

The coding of this reasoning logic is not very pretty, so I will leave it in the github site. But with this new logic, most of the games I found can be resolved, before calling the brute-force backtracking function trysudoku(). 

I think I can add one more logic into the program shortly:

If in one block, all the possible cells for one specific number is in the same row, then the specific number must be in this 3 cells of this row: it can not be in other cells of the same row. 

It would be better to draw a sudoku to explain this logic. Let's leave it until it is implemented.

Now you just need to do it git clone:

git clone https://github.com/BenLin0/sudoku.git

then create a text file with the sudoku game you want to solve (use the samples in  test/ folder), and run the program:

python3 sudoku.py test/sudoku1.txt 

then you will see the reasoning steps (not very pretty) and the final result.

Have fun programming!