Solving sudoku – notes from a tutorial

I have been working on a little Sudoku solver, mainly in order to familiarise myself with Atom and try to reinforce the testing-first approach.

Nothing fancy, just an implementation of a tutorial by ComputerPhile. Testing was made easier by the recursive function returns a value instead of logging the console output. The benefit of this is that it can therefore be incorporated into other code.

At the heart of the software lies a recursive algorithm, that I’m going to talk about to crystallise my thinking:

def next_value(puzzle):
    for y in range(0, 9):
        for x in range(0, 9):
            if puzzle[y][x] == 0:
                for n in range(1, 10):
                    if Sudoku.poss(puzzle, x, y, n):
                        puzzle[y][x] = n
                        if Sudoku.next_value(puzzle):
                            return puzzle
                        puzzle[y][x] = 0
                return
    return puzzle
def next_value(puzzle):
    for y in range(0, 9):
        for x in range(0, 9):
            if puzzle[y][x] == 0:
                for n in range(1, 10):
                    if Sudoku.poss(puzzle, x, y, n):
                        puzzle[y][x] = n
                        if Sudoku.next_value(puzzle):
                            return puzzle
                        puzzle[y][x] = 0
                return
    return puzzle
def next_value(puzzle):
    for y in range(0, 9):
        for x in range(0, 9):
            if puzzle[y][x] == 0:
                for n in range(1, 10):
                    if Sudoku.poss(puzzle, x, y, n):
                        puzzle[y][x] = n
                        if Sudoku.next_value(puzzle):
                            return puzzle
                        puzzle[y][x] = 0
                return
    return puzzle

Enter fullscreen mode Exit fullscreen mode

What it does: goes through each list in the array and when it hits a zero, it replaces it with the first possible number (checked using the poss function).

Then next_value() calls itself, and so the process continues until it encounters a ‘0’ with no possible solution – it then backtracks – returns through the layers of the function until it reaches a point where more than one value is possible, and proceeds as above with the next possible value.

This is where the code diverges from ComputerPhile’s tutorial:

if Sudoku.next_value(puzzle):
    return puzzle
if Sudoku.next_value(puzzle):
    return puzzle
if Sudoku.next_value(puzzle):
    return puzzle

Enter fullscreen mode Exit fullscreen mode

This passes up the answer from the last run of the recursive function to the allow the final return puzzle to provide us with a solution, rather than ‘None’.

The poss function (that checks whether a number is allowed) is simple enough – it checks a input value against the rows and columns according to the rules of Sudoku. The more complicated aspect of these checks are the 3×3 squares. This is dealt with as follows (I take no credit for it – it is taken verbatim from ComputerPhile):

x_sq = (x//3)*3
y_sq = (y//3)*3
for a in range(0, 3):
    for b in range(0, 3):
        if puzzle[y_sq+a][x_sq+b] == n:
            return False
x_sq = (x//3)*3
y_sq = (y//3)*3
for a in range(0, 3):
    for b in range(0, 3):
        if puzzle[y_sq+a][x_sq+b] == n:
            return False
x_sq = (x//3)*3
y_sq = (y//3)*3
for a in range(0, 3):
    for b in range(0, 3):
        if puzzle[y_sq+a][x_sq+b] == n:
            return False

Enter fullscreen mode Exit fullscreen mode

The // operator is Floor Division. It returns full values, so 3//3 == 1, but 2//3 == 0. This allows squares to be defined – the first three checks will all floor divide to 0, so script can check through all and only the values in the 3×3 square.

At some point it would be good to incorporate an easy way to input puzzles. There are also some tutorials for building a GUI to show the puzzle being solved (albeit much slower that the runtime of the function) – I hope to look into those.

The code is available here.

原文链接：Solving sudoku – notes from a tutorial