#
Building a Sudoku Solver (Idea)

Basically to solve any game via code, you just take the rules a human would play and implement code that performs them one after another …

For Sudoku this is stuff like: if a field can have only one possible value (e.g. in the row are already 1,2,3,4; and in the col 6,7,8,9 -> so this field is clearly a 5) or when there is only like one place in a row where the digit could be. (these cases are called nacked singles & hidden singles apparently in sudoku).

So the usual approach to safe computation is to make a candidate list, like what field could have which candidates (like manually writing notes for a hard sudoku).

For this I’m gonna use a 3-dimensional boolean array, with the first 2 dimensions representing the board and then each field in the board can have 9 possible candidates, so each one is represtend with a boolean. Resulting in a 9x9x9 array. For this I’m gonna use numpy, the reason is mostly I just wanna learn using numpy more and its pretty fast (taking advantage of vector operations and written in c).

#
Implementation

#
Basic Structure

Lets first write the basic structure of our solver, it should have a function solve that takes our puzzle as input, the puzzle is in the format:

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

Here 0 means its unknown and a number means its already filled. our function then should solve it and return the solved board. If its not solvable raise an Exception (InvalidBoard), same if there are multiple solutions (MultipleSolutions). You can obviously modify it to just return all solutions if you want instead of raising an exception. The convention to raise an exception, is because I started doing this sudoku solver because of a kata I found on codewars. And they demanded to have an exception in the case ^^'

Python sudoku_solver.py 
import numpy as np

# custom exceptions
class InvalidBoard(Exception): pass
class MultipleSolutions(Exception): pass

def solve(board: list) -> list:
    board = np.array(board)
    hints = np.ones((9, 9, 9), dtype=bool)
    # TODO: solve the puzzle ;)
    pass

#
Creating Hints, Updating board

So the idea here is to create first hints based on what is actually present already, like if a cell has a 9 already, remove 9 as candidate from the row, col and box. Also since that field has a value, it can obviously no longer assume other values, so the candidates for that cell should also be only the current option

def update_hints(board, hints):
    for r in range(9):
        for c, e in enumerate(board[r]):
            if e == 0: continue
            # so we have here a field in the board that has already a value
            # so we can set:
            
            # first of: the row & col in which this cell is, cant contain this value anymore 
            hints[:, c, (e-1)] = False
            hints[r, :, (e-1)] = False

            # same with the box 
            box_row = (r // 3) * 3
            box_col = (c // 3) * 3
            hints[box_row:box_row+3, box_col:box_col+3, (e-1)] = False

            # next the field can't obviously have any other values anymore, so we remove the candidates
            hints[r, c, :] = False

            # and lastly we readd the own value as a candidate for this field, earlier we just removed it as well
            # since that way we can make use of numpy's vectorization stuff & it's way shorter
            hints[r, c, (e-1)] = True

The second thing we need is sth to update the board based on the hints, this carry out our two rules:

  • nacked singles: if this field only has one possible candidate
  • hidden singles: if this field is the only one in the row / col / box that has this candidate

(Don’t blame me for these weird names, apparently they are officially called this …)

def update_board(board, hints):
    # this modified value is added since later on its kinda handy, alternativly one could also just use numpy and compute like the sum of the board or sth similiar
    # and check if it changed, but ig this would take more computing power? 
    modified = False

    # nacked singles (only one value left for this field)
    for r in range(9):
        for c in range(9):
            if board[r][c] != 0: continue
            possible_entries_sum = np.sum(hints[r, c, :])
            if possible_entries_sum == 0: raise InvalidBoard()
            elif possible_entries_sum == 1:
                modified = True
                board[r][c] = np.argmax(hints[r, c]) + 1

    # hidden singles (only possible place in row / col / box for this value)
    for di in range(9):
        # rows
        for r in range(9):
            count = np.sum(hints[r, :, di])
            if count == 0: raise InvalidBoard()
            if count == 1:
               # means there is only one field in this row that has this value as a candidate -> it must be here
               c = np.argmax(hints[r, :, di])
               if board[r][c] != 0: continue

               modified = True
               board[r][c] = di + 1

        # cols
        for c in range(9):
            count = np.sum(hints[:, c, di])
            if count == 0: raise InvalidBoard()
            if count == 1:
                r = np.argmax(hints[:, c, di])
                if board[r][c] != 0: continue

                modified = True
                board[r][c] = di + 1

        # boxes
        for r in range(0, 9, 3):
            for c in range(0, 9, 3):
                count = np.sum(hints[r:r+3, c:c+3, di])
                if count == 0: raise InvalidBoard()
                if count == 1:
                    rr, cc = np.argwhere(hints[r:r+3, c:c+3, di])[0]
                    if board[r + rr][c + cc] != 0: continue

                    modified = True
                    board[r + rr][c + cc] = di + 1

    return modified

So while we can update the board, we need to update the hints, then try filling more of the board and so on …, so we loop as long as stuff gets modified. Thats why I added here a modified return value, so it’s easy to check if the board was actually updated and iterate only as long as stuff changes.

Putting it together

Python sudoku_solver.py 
import numpy as np

class InvalidBoard(Exception): pass
class MultipleSolutions(Exception): pass

def update_hints(board, hints):
    for r in range(9):
        for c, e in enumerate(board[r]):
            if e == 0: continue

            # col
            hints[:, c, (e-1)] = False

            # row
            hints[r, :, (e-1)] = False

            # box
            box_row = (r // 3) * 3
            box_col = (c // 3) * 3
            hints[box_row:box_row+3, box_col:box_col+3, (e-1)] = False

            # the field can't assume other values anymore ...
            hints[r, c, :] = False

            hints[r, c, (e-1)] = True

def update_board(board, hints):
    modified = False

    # nacked singles (only one value left for this field)
    for r in range(9):
        for c in range(9):
            if board[r][c] != 0: continue
            possible_entries_sum = np.sum(hints[r, c, :])
            if possible_entries_sum == 0: raise InvalidBoard()
            elif possible_entries_sum == 1:
                modified = True
                board[r][c] = np.argmax(hints[r, c]) + 1

    # hidden singles (only possible place in row / col / box for this value)
    for di in range(9):
        # rows
        for r in range(9):
            count = np.sum(hints[r, :, di])
            if count == 0: raise InvalidBoard()
            if count == 1:
               # means there is only one field in this row that has this value as a candidate -> it must be here
               c = np.argmax(hints[r, :, di])
               if board[r][c] != 0: continue

               modified = True
               board[r][c] = di + 1

        # cols
        for c in range(9):
            count = np.sum(hints[:, c, di])
            if count == 0: raise InvalidBoard()
            if count == 1:
                r = np.argmax(hints[:, c, di])
                if board[r][c] != 0: continue

                modified = True
                board[r][c] = di + 1

        # boxes
        for r in range(0, 9, 3):
            for c in range(0, 9, 3):
                count = np.sum(hints[r:r+3, c:c+3, di])
                if count == 0: raise InvalidBoard()
                if count == 1:
                    rr, cc = np.argwhere(hints[r:r+3, c:c+3, di])[0]
                    if board[r + rr][c + cc] != 0: continue

                    modified = True
                    board[r + rr][c + cc] = di + 1

    return modified

def solve(board):
    board = np.array(board)
    hints = np.ones((9, 9, 9), dtype=bool)

    update_hints(board, hints)

    while update_board(board, hints):
        update_hints(board, hints)

    return board.tolist()

This is still not able to solve every sudoku that exists, only some easier ones get solved with just this

#
Backtracking

The next & last step for having a fully working sudoku solver is adding backtracking. Sometimes based on the pure deterministic logic we added a cell can still have two or more candidates and we are stuck, so the classical approach is backtracking. This means we just assume that it’s value a first try it out, see if it works, if not then try out value b etc.

Python sudoku_solver.py 
import numpy as np

class InvalidBoard(Exception): pass
class MultipleSolutions(Exception): pass

def update_hints(board, hints):
    for r in range(9):
        for c, e in enumerate(board[r]):
            if e == 0: continue

            # col
            hints[:, c, (e-1)] = False

            # row
            hints[r, :, (e-1)] = False

            # box
            box_row = (r // 3) * 3
            box_col = (c // 3) * 3
            hints[box_row:box_row+3, box_col:box_col+3, (e-1)] = False

            # the field can't assume other values anymore ...
            hints[r, c, :] = False

            hints[r, c, (e-1)] = True

def update_board(board, hints):
    modified = False

    # nacked singles (only one value left for this field)
    for r in range(9):
        for c in range(9):
            if board[r][c] != 0: continue
            possible_entries_sum = np.sum(hints[r, c, :])
            if possible_entries_sum == 0: raise InvalidBoard()
            elif possible_entries_sum == 1:
                modified = True
                board[r][c] = np.argmax(hints[r, c]) + 1

    # hidden singles (only possible place in row / col / box for this value)
    for di in range(9):
        # rows
        for r in range(9):
            count = np.sum(hints[r, :, di])
            if count == 0: raise InvalidBoard()
            if count == 1:
               # means there is only one field in this row that has this value as a candidate -> it must be here
               c = np.argmax(hints[r, :, di])
               if board[r][c] != 0: continue

               modified = True
               board[r][c] = di + 1

        # cols
        for c in range(9):
            count = np.sum(hints[:, c, di])
            if count == 0: raise InvalidBoard()
            if count == 1:
                r = np.argmax(hints[:, c, di])
                if board[r][c] != 0: continue

                modified = True
                board[r][c] = di + 1

        # boxes
        for r in range(0, 9, 3):
            for c in range(0, 9, 3):
                count = np.sum(hints[r:r+3, c:c+3, di])
                if count == 0: raise InvalidBoard()
                if count == 1:
                    rr, cc = np.argwhere(hints[r:r+3, c:c+3, di])[0]
                    if board[r + rr][c + cc] != 0: continue

                    modified = True
                    board[r + rr][c + cc] = di + 1

    return modified

def propagate(board, hints):
    iterations_required = 0
    update_hints(board, hints)

    while update_board(board, hints):
        iterations_required += 1
        update_hints(board, hints)

    print(f"required: {iterations_required} iterations")

def solve(board):
    board = np.array(board)
    hints = np.ones((9, 9, 9), dtype=bool)

    propagate(board, hints)

    # now the board & hints are as small as the deterministic part of the implementation will lead
    # potential improvements: hidden / nacked pairs, triples etc. -> could make it way faster later on

    if np.count_nonzero(board) == 81:
        return board.tolist()

    # since its not solved now, backtracking is required
    # find the cell with the least possibilities
    candidates_per_cell = np.sum(hints, axis=2)
    # already filled fields should be ignored (set to 10, so they are certainly not the field thats gonna get tried)
    candidates_per_cell[board != 0] = 10
    r, c = np.unravel_index(np.argmin(candidates_per_cell), candidates_per_cell.shape)

    solutions = []

    for di in np.where(hints[r, c])[0]:
        board_try = board.copy()

        board_try[r][c] = di + 1
        try:
            solutions.append(solve(board_try))
        except InvalidBoard:
            continue

    if solutions == []:
        raise InvalidBoard
    elif len(solutions) == 1:
        return solutions[0]

    raise MultipleSolutions(solutions)

solving a hard sudoku

#
Further Improvement Ideas

Here one can also check (like written in the comments), for hidden / nacked pairs, triplets etc. this can make the solving way faster, by increasing the deterministic part of the solver. But for now this is enough

Btw, I added the required iteration prints as it’s kinda nice to have like some information of the run and is also a good indicator if it makes sense for your sudoku difficulty to add backtracking, like if there are only little iterations etc. then it might not be really worth it … but if you get like a ton of iterations, then its worth considering

Also A nice improvement would be pretty printing the result etc. (like you see here, the result doesnt look soo “pretty”, its just a bunch of lists, just putting them in newlines etc would be a huge improvement)