Wednesday, June 24

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:
                continue
            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
                    else:
                        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:
                logging.info("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: ,

1 Comments:

At March 03, 2022 5:46 PM, Blogger idunquigg said...

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?

 

<< Home