Wednesday, June 24

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 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 :
            board[i][j] = set()
            for trynum in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
                if not conflict(board, i, j, 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

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

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

Have fun programming!

Sudoku programming: Adding logic into the already-logically-perfect program

As I already have a backtracking program that can perfectly solve any solvable sudoku, I am ready to add logic reasoning into it, after the board is loaded, before the backtracking trysudoku() function is called. Yes, as the last resort, the trysudoku() will be in action if the sudoku is not completely solved after the logic reasoning part is deployed.

The new function is called preset(). Apparently when I was writing this part, I only thought of it as a preprocess before running the main course trysudoku(). Anyway, in the second commit of the project, you can see this new present() function has these logic reasoning parts:

Part 1, walk though all empty cells to determine whether only one possible number suitable (not conflict with other elements). If there is only one possible number, then set this number. 

        count = 0
	for i in range(9):
        for j in range(9):
            if board[i][j] != 0:
            onlyonefit = false
            fitnum = 0
            for trynum in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
                if not conflict(board, i, j, trynum):
                    if onlyonefit == false:
                        onlyonefit = true
                        fitnum = trynum
                        onlyonefit = false
                        break   #jump out of trynum
            if onlyonefit == true:
                board[i][j] = fitnum
		count += 1

Yes this simple logic works for some sudoku games.  I should make this part as a function and call it repeatedly until there is no cell being set (count == 0). 

Part 2, for each row, loop thought number [1..9]. If the number already exists in this row, forget it; otherwise, count how many possible cells this number is possible to be set in. If there is only one cell this number can set in (in this row), then the number has to be set in this cell.

    for i in range(9):
        for trynum in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
            possiblesitenum = 0
            possiblesite = 0
            Found = False
            for j in range(9):
                if type(board[i][j]) is int:
                    if board[i][j] == trynum:
                        Found = True
                        break   #found the number.
                else:   #is a set
                    if trynum in board[i][j]:
                        possiblesitenum += 1
                        possiblesite = j
            if Found == False and possiblesitenum == 1:
      "This num {} can only be in one site {} of this column {}".format(trynum, possiblesite, i))
                board[i][possiblesite] = trynum
                count += 1

After checking each row, do the same checking to each column, and each block.

Again, this is also simple logic: Each [1...9] number must show up in a row once, and only once. If there is only one cell available for a number for one row/column/block, then the number must be in this cell.

Aha, after reading the program again, I found I did call the preset() function (including the Part 1 and Part 2) repeatedly until there is no cell being set (count == 0). 

Done with this logic, I am able to commit this code, and get back to paper sudoku to learn more logic. To be continue.

Labels: ,

Grand National Betting Locations | Mapyro
Find the 포천 출장샵 best Grand 충청남도 출장안마 National Betting locations in the United Kingdom. 김제 출장샵 Great location for betting & 논산 출장안마 gambling in our online guide. Great What is Grand National Betting?How often can I bet on 동해 출장안마 the Grand National?

Sudoku programming: Classic Backtracking Problem

It was 2018, and the source code I mentioned in this post can be accessed in

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: 
 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:

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 ]

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):
        board[x][y] = trynum
        nextx, nexty = getnext(x,y)
        if nexty == 9:
            return  1   #end!
        result = trysudoku(nextx, nexty)
        if result == 1:
            return 1
            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.

Sunday, June 7







Plastic resin codes