Why is my backtracking algorithm not working and producing squares with duplicated entries?

Question

Hi I am trying to use backtracking to solve a Sudoku Puzzle.

board = [[0, 0, 0, 7, 0, 0, 0, 0, 0],
         [1, 0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 4, 3, 0, 2, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0, 6],
         [0, 0, 0, 5, 0, 9, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 4, 1, 8],
         [0, 0, 0, 0, 8, 1, 0, 0, 0],
         [0, 0, 2, 0, 0, 0, 0, 5, 0],
         [0, 4, 0, 0, 0, 0, 3, 0, 0]]

def findBlank(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i,j)
    return False

def feasibleMove(board, coordinate, number):
    x, y = coordinate
    #check row
    for i in range(9):
        if board[x][i] == number and y != i:
            return False
    #check column
    for i in range(9):
        if board[i][y] == number and x != i:
            return False
    #check box
    row = coordinate[0] // 3
    col = coordinate[1] // 3

    for i in range(x * 3, x * 3 + 3):
        for j in range(y * 3, y * 3 + 3):
            if board[row][col] == number and (i, j) != coordinate:
                return False

    return True

def solver(board):
    blankCell = findBlank(board)
    if not blankCell:
        return True
    else:
        row, col = blankCell

    for i in range(1, 10):
        if feasibleMove(board, (row, col), i):
            board[row][col] = i

            if solver(board):
                return True

            board[row][col] = 0

    return False

I have written one function to return a blank value if one exists, here 0 indicates a blank. Another function to test if placing a number into a specific position in a board is valid (based on Sudoku rules), and another one that implements backtracking to actually solve the puzzle.

With the board provided when I run the algorithm I get:

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

It seems to work on a column by column and row by row basis. However the 3x3 squares are not correct.

For example taking the top left square

[[2, 1, 3],
 [1, 3, 4],
 [5, 6, 9]]

This has duplicated entries for example 3 and also does not contain each number 1-9 precisely once.

Based on my feasibleMove method this should not be allowed!

Clearly I have made a mistake but I cannot see where...

Any ideas?

Answer 1

The reason is that this part of feasibleMove has errors:

row = coordinate[0] // 3
col = coordinate[1] // 3

for i in range(x * 3, x * 3 + 3):
    for j in range(y * 3, y * 3 + 3):
        if board[row][col] == number and (i, j) != coordinate:
            return False

The iteration should be based on row and col, not on x and y. And when you read out the value from board, you should use i and j as indexes. Right now, you are 9 times looking at the very same cell on your board.

row = (x // 3) * 3
col = (y // 3) * 3

for i in range(row, row + 3):
    for j in range(col, col + 3):
        if board[i][j] == number and (i, j) != coordinate:
            return False

However, your algorithm is too slow to solve the puzzle in a reasonable time. You should improve your algorithm, with the following:

• Don't look for blank cells in real time. Instead, collect them into a queue, and pop them from there (and put them back when backtracking)
• Instead of checking whether a value is valid for a cell, stay one step ahead, and keep track of which values are still valid (in a set), for each cell. Initialise this at the very start of the algorithm.
• When placing a value update the sets of impacted cells

These last two points may seem to give no gain as it just shifts the work of scanning rows, columns and boxes to another moment in the algorithm, but the benefit comes here:

• In order to keep your recursion tree narrow, give priority to cells that have the fewest possible values left, ideally only one. You can use python's heapq for this, and it should be applied to the queue that I mentioned in the first point.

I leave the implementation for you, as it was not your question. There are lots of working examples on the net anyway.