## Sumukh Barve

Polydojo Founder's blog on Software, Business and more.

2020-12-14

# Solving NxN Sudoku Via Deductions & BFS in Python

A number of articles on the Internet employ backtracking for solving Sudoku puzzles. And while backtracking works for 9x9 puzzles, it takes hours and hours to solve 16x16 puzzles.

When humans solve Sudoku by hand, we don't use backtracking. We instead use on the rules of Sudoku to deduce a solution. In this blog post, we'll do exactly that. We'll develop a simple algorithm for solving Sudoku puzzles by employing the rules of the game. Along the way, we'll use a little bit of help from our trusty friend, BFS. ### Rules Of Sudoku

If you've played Sudoku before, you can skip this section. If not, don't worry. It's a simple logical reasoning game. The Sudoku puzzles in most newspapers have a 9x9 grid like follows: The object of the game is the fill the entire puzzle with a single number per cell, such that the numbers 1 to 9 (both inclusive):

1. appear in each row exactly once,
2. appear in each column exactly once, and
3. appear in each (thick-bordered) 3x3 box, exactly once.

Nomenclature: Cell vs Box
Cell: A single empty spot in the puzzle that takes a single number.
Box: A grouping of 9 (or generally N) cells, just like the 3x3 boxes marked with thick borders.

In the above puzzle, consider the last 3x3 box. Now, notice that the last column and the second-last row both include `1`. Hence, the only remaining cell in the 3x3 box must be `1`.

We can keep applying the rules of Sudoku until we solve the entire puzzle. The full solution to the puzzle is given below: ### Generalizing To NxN And Solving By Hand

Instead of a 9x9 puzzle, more generally, we can have an NxN puzzle, where N is a perfect square. And while we'll be solving 16x16 puzzles, let's work with a 4x4 puzzle first. Consider the following 4x4 puzzle, represented in plain text:

``````3 4  _ _
_ 2  _ _

_ _  4 _
_ _  2 1
``````

In the above text representation, empty cells are marked with underscores, and distinct 2x2 boxes are spaced slightly apart for visual clarity. (For a general NxN puzzles, there are exactly N non-overlapping inner boxes of size √N x √N.)

With 4x4, instead of numbers `1` to `9`, we only have `1` to `4`. But the rules remain the same. Each number must appear exactly once in each row, in each column and in each 2x2 box.

4x4 puzzles are obviously simpler than 9x9 ones. Let's quickly deduce some cells:

• In the first 2x2 box, the only remaining cell must be `1`.
• In the last 2x2 grid, the only remaining cell must be `3`.

Thus, we quickly get:

``````3 4  _ _
1 2  _ _

_ _  4 3
_ _  2 1
``````
• Consider the first column (`3`, `1`, `_`, `_`). The only remaining numbers are `2` and `4`. We can't put `2` in the last row as it's already in there. Hence, in the first column, `2` must be in the second last row. And then it follows, that `4` must be in the last row. Thus, we get:
``````3 4  _ _
1 2  _ _

2 _  4 3
4 _  2 1
``````
• Consider the second column. The number `1` can't be in the last row, so it must be in the second last row. Which means the last row must have the only remaining number, `3`.
``````3 4  _ _
1 2  _ _

2 1  4 3
4 3  2 1
``````
• Now, consider the third column. `1` must be in the first row as it can't be in the second row. Next, it follows that `3` must be in the second row. We get:
``````3 4  1 _
1 2  3 _

2 1  4 3
4 3  2 1
``````
• Finally, consider the last column. `2` must be in the first row as it can't be in the second row. Next, it follows that `4` must be in the second row. Thus, we get the final solution:
``````3 4   1 2
1 2   3 4

2 1   4 3
4 3   2 1
``````

### Column-wise, vs row-wise vs box-wise:

While we mostly used a column-wise approach in the above example, we could've gone row-wise instead. The solution, of course, would've been exactly the same.

### Game Representation & Helpers:

The text-based representation above is simple for humans, but while writing code, it may be easier to manipulate lists of numbers. So, let's use a list of numbers for representing a row, and a list of such rows for representing the entire puzzle.

In `sudoku.py`:

``````import math;

"Reads a string-represented game as a list of rows.";
rows = [];
for line in s.splitlines():
if line.strip():
rows.append([]);
for word in line.split():
if word.isdigit():
rows[-1].append(int(word));
elif word == "_" * len(word):
rows[-1].append("_");
else:
raise ValueError(f"Unexpected word: {word}");
n = len(rows);
rootN = int(math.sqrt(n));
if rootN ** 2 != n:
raise ValueError("The number of rows isn't a perfect square.");
for i in range(n):
if len(rows[i]) != n:
raise ValueError("Game-grid isn't a perfect square.");
return rows;
``````

In `readGame()`, we accept a string `s` and iterate line-by-line, adding a new row for each non-blank line. And of course, underscores are to be interpreted as empty cells.

Next, let's write a utility for printing back into the human-friendly text format:

``````def printGame (game):
"Pretty-prints `game`.";
n = len(game);
rootN = int(math.sqrt(n));
maxDigits = len(str(n));    # 16 -> len('16') -> 2
output = "";
leftPad = lambda s: s if len(s) == maxDigits else leftPad(" " + s);
for (i, row) in enumerate(game):
if i % rootN == 0:
output += "\n";
for (j, cell) in enumerate(row):
if j % rootN == 0:
output += " " * 2;
output += leftPad(str(cell)) + " ";
output += "\n";
print(output);
``````

In `printGame()`, we accept a `game` as produced by `readGame()`, and build `output` row by row; ultimately printing it. And yes, we add a little extra space around `rootN`x`rootN` boxes, for visual clarity. (The `leftPad` helper is for left-padding spaces, which'll be useful when we solve 16x16 puzzles.)

Alright, let's try our functions in an interactive Python shell:

``````>>> from sudoku import *
>>>
...   3 4   _ _
...   _ 2   _ _
...
...   _ _   4 _
...   _ _   2 1
... """)
>>> print(game)
[[3, 4, '_', '_'], ['_', 2, '_', '_'], ['_', '_', 4, '_'], ['_', '_', 2, 1]]
>>>
>>> printGame(game)

3 4   _ _
_ 2   _ _

_ _   4 _
_ _   2 1

>>>
``````

As you can see, we're now able to read the game as a list of lists, and we can print the game back into our human-friendly text representation.

### Getting Rows, Columns And Boxes

The rules of Sudoku revolve around rows, columns and boxes. Thus, for any given any cell, we must be able quickly get the row, column and box it belongs to.

Let's say we're at the cell with row index `i` and column index `j`. Then, we need to be able to quickly get:

• All the numbers in the `i`th row.
• All the numbers in the `j`th column.
• All the numbers in the box that includes the `(i, j)`th cell.

Let's write helpers for each:

``````def getRow (i, game):
"Returns the i^th row in `game`.";
return game[i];

def getCol (j, game):
"Returns the j^th column in `game`.";
return list(map(lambda row: row[j], game));

def getBoxStartPos (i, j, rootN):
"Returns the box-starting positions w.r.t `(i,j)`";
iBox = math.floor(i / rootN) * rootN;
jBox = math.floor(j / rootN) * rootN;
return (iBox, jBox)

def getFlatBox (i, j, game):
"Returns inner-box w.r.t (i,j), as a _flat_ list.";
rootN = int(math.sqrt(len(game)));
iBox, jBox = getBoxStartPos(i, j, rootN);
flatBox = [];
for ii in range(iBox, iBox + rootN):
for jj in range (jBox, jBox + rootN):
flatBox.append(game[ii][jj]);
return flatBox;
``````

Getting the `i`th row is very easy. That's just `game[i]`. For getting the `j`th column, we iterate over each `row` in `game` and collect `row[j]`. (If you're unfamiliar with `map()`, check out this guide to functional programming in Python.)

Getting the box in which `(i, j)` occurs is a wee-bit more involved. We note that for an `N`x`N` game, the box size is `rootN`x`rootN`. And for the row (or column) indexed `k`, the cell at the beginning of the box has row (or column) index equal to `math.floor(k/rootN) * rootN`. Once we have the index ranges for the box, we iterate over the box and collect the cell values into a list, returning the same.

### Let's Deduce!

Alright, now that we can read & print games, and quickly access rows, columns & boxes, let's write a deduction function.

``````def deduceSimple (game):
"Deduces cells in `game` based on Sudoku rules.";
n = len(game);
fullSet = set(range(1, n+1));   # Set of numbers 1, 2, ... N
putCount = 0;
isSolved = True;                # Initial assumption
for i in range(n):
for j in range(n):
if game[i][j] == "_":
isSolved = False;   # Assumption correction
remSet = (
fullSet
- set(getRow(i, game))
- set(getCol(j, game))
- set(getFlatBox(i, j, game))
);
if len(remSet) == 1:
game[i][j] = remSet.pop();
putCount += 1;
if putCount:
return deduceSimple(game);
# otherwise ...
return isSolved;
``````

Here's how `deduceSimple(.)` works:

1) We accept a `game`, as parsed by `readGame(.)`.

2) `fullSet` is the set of all numbers that must be in each row, column or box. (For 4x4, that'll be `{1,2,3,4}`, for 9x9 that'll be `{1,2,3,4,5,6,7,8,9}`, etc.)

3) `putCount` is the number of times we've placed a number in a cell.

4) Initially, we assume that the game `isSolved`. If we encounter an empty cell, we'll set `isSolved = False`. (This bit arguably isn't rigorous enough. But for now, if we assume that invalid games won't be supplied, everything should be OK.)

5) We iterate through each cell, row-wise. For each empty cell:

5.1) We compute `remSet`, which is the set of remaining numbers that may be placed in the cell. We do this by subtracting from the `fullSet`, the set of numbers already in the row, column and box.

5.2) If the `remSet` has a single number, then that number must be placed in the cell. That is, if only one number can be placed in a cell, then it must be placed there. Thus, we place the number in the cell and increment `putCount`.

6) If `putCount` is truthy (i.e. `>= 1`), then it must mean that we've placed at least one number. Now, on account of such placement, we may be able to place additional numbers. Thus, we `deduceSimple(game)` again.

7) Instead, if `putCount` is falsy (i.e. zero), it means that we were unable to place even a single number. Thus, we just return `isSolved`.

### Deductions In Action:

Instead of jumping to writing tests, let's see `deduce()` in action:

``````>>> from sudoku import *
>>>
... 3 4  _ _
... _ 2  _ _
...
... _ _  4 _
... _ _  2 1
... """);
>>> deduceSimple(game)
True
>>> printGame(game)

3 4   1 2
1 2   3 4

2 1   4 3
4 3   2 1

>>>
``````

Hmm, it seems to work. Let's try it on the 9x9 puzzle above. Continuing in the same Python shell:

``````>>> game = readGame("""
... 5 3 _  _ 7 _  _ _ _
... 6 _ _  1 9 5  _ _ _
... _ 9 8  _ _ _  _ 6 _
...
... 8 _ _  _ 6 _  _ _ 3
... 4 _ _  8 _ 3  _ _ 1
... 7 _ _  _ 2 _  _ _ 6
...
... _ 6 _  _ _ _  2 8 _
... _ _ _  4 1 9  _ _ 5
... _ _ _  _ 8 _  _ 7 9
... """)
>>> deduceSimple(game)
True
>>> printGame(game)

5 3 4   6 7 8   9 1 2
6 7 2   1 9 5   3 4 8
1 9 8   3 4 2   5 6 7

8 5 9   7 6 1   4 2 3
4 2 6   8 5 3   7 9 1
7 1 3   9 2 4   8 5 6

9 6 1   5 3 7   2 8 4
2 8 7   4 1 9   6 3 5
3 4 5   2 8 6   1 7 9

>>>
``````

Alright, it still seems to work. But the puzzles we've been using so far have been simple. Let's try a hard puzzle:

``````>>> game = readGame("""
... _ 1 3   _ _ _   _ 5 _
... _ _ 5   _ _ 8   _ 4 3
... _ 6 _   _ _ _   _ _ 7
...
... _ _ _   4 _ _   _ _ _
... _ _ 1   _ _ 2   _ _ _
... _ _ _   _ _ 5   _ 6 8
...
... _ 5 4   2 _ _   _ _ 9
... 2 _ _   3 _ _   _ 8 _
... _ _ 7   5 _ 1   _ _ _
... """)
>>> deduceSimple(game)
False
>>> printGame(game)

_ 1 3   _ _ _   _ 5 _
_ _ 5   _ _ 8   _ 4 3
_ 6 _   _ _ _   _ _ 7

_ _ _   4 _ _   _ _ _
_ _ 1   _ _ 2   _ _ _
_ _ _   _ _ 5   _ 6 8

_ 5 4   2 _ _   _ _ 9
2 9 6   3 _ _   _ 8 _
_ _ 7   5 _ 1   _ _ _

>>>
``````

Ouch! It no longer works. What's happening?

### Why `deduceSimple()` failed:

First of all, while `deduceSimple()` couldn't solve the puzzle, it did manage to place a couple of numbers. Specifically, it placed two numbers in the bottom-left (3x3) box.

Continue considering the bottom-left box. Notice that we can't put `1` in the last row, as it's already in there. And since there's only one other empty cell in the box, that must be `1`. Gosh! We've just deduced a number that the `deduceSimple()` couldn't. How?

Essentially, `deduceSimple()` uses the following logic: For a given cell, if only a single number can be placed in the cell, then it must be placed there.

To determine the placement of `1` in the bottom-left box, we used the following logic: For a given box, if a number can only be placed in a single cell, then it must be placed there.

That is, `deduceSimple()` employs a cell-based technique. But instead, we used a box-based technique for placing `1`. And similarly, we can use row-based and column-based techniques too.

### Cells, Rows, Etc.

Cells

So far, we've been considering a single (empty) cell at a time. We checked if only a single number can be placed in it, and if so, we placed it there.

Here's another way of putting it: For an empty cell positioned at `(i, j)`, for each number `x` in the set of possible numbers, we check if `x` could be placed at `(i, j)`. If only one such `x` exists, then we must place `x` at `(i, j)`.

Rows

Alright, let's now turn to rows. If a number `x` is not already in the row (indexed) `i`, we must check if the row `i` has just one empty cell that can accept `x`. If such a cell is found, then we must place `x` there. And of course, for each row, we'll need to consider every possible value of `x`.

Here's another way to put it: For the row `i` and a number `x`, we check each empty-cell's column-index `j`, such that `x` can be placed at `(i, j)`. If there's exactly one such `j`, then `x` must be placed at `(i, j)`.

For a given cell, `i` & `j` are fixed, but we try each possible number `x`. And for a given row+number combination, `i` and `x` are fixed, but we try each possible (non-empty) column-index `j`.

Columns & Boxes

Row-based logic can easily be extended to columns and boxes too.

The Trio: `(i, j, x)`

The trio, `(i, j, x)`, can be thought of as a three-dimensional index. And for deducing numbers/cells, we fix two indices and try if the third index can take only one possible value. If so, then it must take that value.

### Smarter Deductions:

Alright, in addition to cell-based deductions, let's code row, column and box-based deductions:

``````from collections import defaultdict;
import itertools;

def collectPossibleTrioLists (game):
"Collects possibly deducible trios, (i, j, x), in `game`.";
n, rootN = len(game), int(math.sqrt(len(game)));
isFilled = True;                # Initial assumption
cellwise = defaultdict(list);
rowwise = defaultdict(list);
colwise = defaultdict(list);
boxwise = defaultdict(list);
#
for i in range(n):
for j in range(n):
if game[i][j] == "_":
isFilled = False;
rowSet = set(getRow(i, game));
colSet = set(getCol(j, game));
(iBox, jBox) = getBoxStartPos(i, j, rootN);
boxSet = set(getFlatBox(iBox, jBox, game));
for x in range(1, n+1):
if x not in (rowSet | colSet | boxSet):
trio = (i, j, x);
cellwise[(i, j)].append(trio);
rowwise[(i, x)].append(trio);
colwise[(j, x)].append(trio);
boxwise[((iBox, jBox), x)].append(trio);
possibleTrioLists = itertools.chain(
cellwise.values(), rowwise.values(),
colwise.values(), boxwise.values(),
);
return (possibleTrioLists, isFilled);

def deduceBetter (game):
putCount = 0;
(iterTrioLists, isFilled) = collectPossibleTrioLists(game);
for trioList in iterTrioLists:
if len(trioList) == 1:
(i, j, x) = trioList;
if game[i][j] == "_":
game[i][j] = x;
putCount += 1;
# Finally ...
if putCount:
return deduceBetter(game);
# otherwise ...
return isFilled;
``````

Collecting Lists Of Possible Trios:

We'd touched upon `(i, j, x)` trios in the preceding discussion. The function, `collectPossibleTrioLists(.)`, is all about trios.

The `cellwise` dictionary is keyed using fixed `(i, j)` combinations. The value against a given `(i, j)` combination is the list of all possible `(i, j, x)` trios. Basically, we find all possible values of `x` for given `(i, j)`, but instead of collecting just the possible `x`s, we collect the possible `(i, j, x)` trios.

The `rowwise` dictionary is keyed using `(i, x)` combinations. The values are the corresponding `(i, j, x)` trios. The `columnwise` dictionary is exactly like `rowwise`, but keyed using `(j, x)` combinations instead.

The `boxwise` dictionary is a wee-bit different. To identify a box, we need an `(iBox, jBox)` pair. (This is similar to needing `i` for identifying a row.) Thus, the `boxwise` dictionary is keyed using `( (iBox, jBox), x )`. The dictionary's values, as always, are `(i, j, x)` trios.

Now, with regard to `cellwise`, you may ask: Why not use a list of `x`s as the value, instead of `(i, j, x)` trios? The answer is simple. By using a list of trios across `cellwise`, `rowwise`, `columnwise` and `boxwise`, we can combine the `.values()` of these dictionaries without special regard to keys.

Deducing:

Note that each value in the `cellwise` dictionary is a list of trios, AKA `trioList`. Thus, `cellwise.values()` is an iterable of `trioList`s. On combining the values in `cellwise` with those from `rowwise`, etc., we get a combined iterable of `trioList`s.

We iterate over each `trioList`. If a `trioList` contains a single trio `(i, j, x)`, it means that on fixing two of the (pseudo-)indices, only a single value for the third index was possible. Thus, we can go ahead and place `x` at `(i, j)`.

### Better Deductions In Action

Let's try `deduceBetter()` on the previous hard puzzle:

``````>>> from sudoku import *
>>>
... _ 1 3   _ _ _   _ 5 _
... _ _ 5   _ _ 8   _ 4 3
... _ 6 _   _ _ _   _ _ 7
...
... _ _ _   4 _ _   _ _ _
... _ _ 1   _ _ 2   _ _ _
... _ _ _   _ _ 5   _ 6 8
...
... _ 5 4   2 _ _   _ _ 9
... 2 _ _   3 _ _   _ 8 _
... _ _ 7   5 _ 1   _ _ _
... """)
>>>
>>> deduceBetter(game)
False
>>> printGame(game)

_ 1 3   _ _ _   _ 5 _
_ _ 5   _ _ 8   _ 4 3
4 6 _   _ 5 3   _ _ 7

_ _ _   4 _ _   _ _ _
_ _ 1   8 _ 2   _ _ _
_ _ _   _ _ 5   _ 6 8

1 5 4   2 8 6   _ _ 9
2 9 6   3 _ _   _ 8 _
_ _ 7   5 9 1   _ _ _

>>>
``````

Hmm, `deduceBetter(.)` did better than `deduceSimple(.)`. Particularly, `deduceBetter(.)` was able to place eight additional cells. But it still didn't solve the puzzle. What's happening?

### Too Many Techniques

For deductions, we're using simple cell-based, row-based, column-based and box-based techniques. But there are LOTS of Sudoku techniques that we aren't yet using. Advanced techniques like X-Wing, Swordfish, XY-Wing etc. often require you to track multiple rows/boxes at once.

We could try to code-up all the advanced techniques, but first let's take a step back and reflect on our progress so far.

### Reflection, Simplicity & BFS

Alright. We wanted to use deduction for solving Sudoku puzzles. For easy puzzles, it appears that our solution works. But implementing a purely-deductive function that can solve every puzzle seems complicated.

Could we combine our deductive function with something simple, like Breadth First Search? Hmm, the idea here is that instead of searching the entire space of possible NxN grid arrangements, we'll use deductions in combination with BFS so that we can make educated guesses.

Smart Guessing:

Right now, we're looking for `trioList`s that contain exactly one trio. But if we find no such `trioList`, we could consider the smallest (minimum length) `trioList`, and try each of its trios as a guess. Sounds like a start. Let's try it.

### Deductive Guessing & BFS Code

Retaining `collectPossibleTrioLists(.)` from before, consider:

``````def deduce (game):
"Tries to logically fill game using the rules of Sudoku.";
putCount = 0;
minTrioList = None;
(iterTrioLists, isFilled) = collectPossibleTrioLists(game);
for trioList in iterTrioLists:
if len(trioList) == 1:
(i, j, x) = trioList;
if game[i][j] == "_":
game[i][j] = x;
putCount += 1;
elif len(trioList) == 0:
pass;
elif (not minTrioList) or len(trioList) < len(minTrioList):
minTrioList = trioList;
# Finally ...
if putCount:
return deduce(game);
# otherwise ...
#printGame(game);
return (isFilled, minTrioList);
``````

The only difference from the previous implementation is `minTrioList`, which is simply the `trioList` with minimum length. Using `minTrioList`, we'll be able to make smart guesses. That is, instead of guessing randomly, our guesses will spring from `(i, j, x)` trio-based deductions.

Now consider:

``````import copy;

def solveGame (inputGame):
"Solves `inputGame` using deductions and BFS.";
solutionList = [inputGame];         # Search-list (AKA Open-list)
while solutionList:
game = solutionList.pop(0);     # 0 => BFS
(isFilled, minTrioList) = deduce(game);
if isFilled and checkSolved(game):
return game;
elif minTrioList:
for (i, j, x) in minTrioList:
newGame = copy.deepcopy(game);
newGame[i][j] = x;
solutionList.append(newGame);
# otherwise ...
raise ValueError("Can't solve game.");
``````

The function `solveGame(.)`, uses `minTrioList` to perform BFS if (and only if) `deduce()` alone can't provide a solution. First, we use `deduce(.)` to deduce cells. If the game isn't solved, we create a separate copy of the game for each guess/trio from `minTrioList`. We keep trying to solve each copy, until we find the right solution.

The only other detail is the definition of `checkSolved(.)`, which is quite simple:

``````def checkSolved (game):
n = len(game);
rootN = int(math.sqrt(n));
fullSet = set(range(1, n+1));
for k in range(0, n):
rowAndColOk = (
set(getRow(k, game)) == fullSet and
set(getCol(k, game)) == fullSet #and
);
if not rowAndColOk:
return False;
for i in range(0, n, rootN):
for j in range(0, n, rootN):
if set(getFlatBox(i, j, game)) != fullSet:
return False;
return True;
``````

### Let's Solve!

Let's try our new function on the hard puzzle that previously stumped us:

``````>>> from sudoku import *
>>>
... _ 1 3   _ _ _   _ 5 _
... _ _ 5   _ _ 8   _ 4 3
... _ 6 _   _ _ _   _ _ 7
...
... _ _ _   4 _ _   _ _ _
... _ _ 1   _ _ 2   _ _ _
... _ _ _   _ _ 5   _ 6 8
...
... _ 5 4   2 _ _   _ _ 9
... 2 _ _   3 _ _   _ 8 _
... _ _ 7   5 _ 1   _ _ _
... """)
>>>
>>> solvedGame = solveGame(game)
>>> printGame(solvedGame)

8 1 3   7 2 4   9 5 6
9 7 5   6 1 8   2 4 3
4 6 2   9 5 3   8 1 7

5 3 8   4 6 9   1 7 2
6 4 1   8 7 2   3 9 5
7 2 9   1 3 5   4 6 8

1 5 4   2 8 6   7 3 9
2 9 6   3 4 7   5 8 1
3 8 7   5 9 1   6 2 4

>>>
``````

Hmm, it seems to work. But could this solve a 16x16 puzzle?

### Easy 16x16 Puzzles:

With backtracking, solving (even simple) 16x16 puzzles will take hours if not days. Let's see how `solveGame(.)` fairs:

``````>>> game = readGame("""
... __  4 __ __      8 __ 16 __     11 __  1 __     __  6 __ 14
...  3 __ __  9     __ 15 __  4     10  7 __ 13     __ __ 12 __
... __  6 __ __      2 11 __ __      8 __ __ __      3 __ __ __
... 15 __ __ __     __ __ __ 13     __ __ 14 __     __  2 __  4
...
...
... __ __ __  8     __  3 __ __      7 __ __ __      5 __ __ __
... __ __ __ __     __ __ 14 __     __ __ __ 10     __ 16 __ 13
... __ __  9  2      5 __ __ __     __  8 __ __     11 __ __ __
... 12 __  1 __     __ __ __ 16     __ __ 13 __     __ __  3 __
...
... __ __ __ 12     15 __ __ __     __  6 __ __     13 __  4  7
... 16  1 13 __     10 __ __  3     __ __  7 __     __  9 __ __
...  6 __ __ __     __ __ 11 __      4 __ __  9     __ __  2 10
... __  3 __ __     __ 16 __ __     __ 14  8 __     __ 11 __ __
...
...
...  5 11  3 10     __ __ __  8     __ __ 12  4     __ __ __  1
... __ 14 __ __     11  9 __ __     __ 13 15 __      4 __  5 __
... 13 __  4 __      6 __ __ __     __ __ __  2     __ 12 __  9
... __ 12 __ 16     __ 13 __ __     __  1 __ __      6 __ 15 __
... """)
>>>
>>> solvedGame = solveGame(game)
>>> printGame(solvedGame)

10  4  5 13    8 12 16  9   11  2  1  3   15  6  7 14
3  2 11  9   14 15  6  4   10  7 16 13    1  5 12  8
1  6 12 14    2 11  7 10    8 15  4  5    3 13  9 16
15  8 16  7    3  5  1 13    9 12 14  6   10  2 11  4

14 13  6  8   12  3  4 15    7 16  9 11    5  1 10  2
7  5 15  3    1  6 14 11   12  4  2 10    9 16  8 13
4 16  9  2    5 10 13  7    3  8  6  1   11 15 14 12
12 10  1 11    9  8  2 16   15  5 13 14    7  4  3  6

11  9  8 12   15  2  5 14    1  6 10 16   13  3  4  7
16  1 13  5   10  4  8  3    2 11  7 12   14  9  6 15
6  7 14 15   13  1 11 12    4  3  5  9   16  8  2 10
2  3 10  4    7 16  9  6   13 14  8 15   12 11  1  5

5 11  3 10   16 14 15  8    6  9 12  4    2  7 13  1
8 14  2  6   11  9 12  1   16 13 15  7    4 10  5  3
13 15  4  1    6  7  3  5   14 10 11  2    8 12 16  9
9 12  7 16    4 13 10  2    5  1  3  8    6 14 15 11

>>>
``````

For this easy 16x16 puzzle, `solveGame(.)` took about 2 seconds. At least in comparison with hours, that's pretty neat. And the maximum number of games simultaneously on the `solutionList` was just `26`. But then again, this was an easy 16x16 puzzle. Let's try a hard one.

### Hard 16x16 Puzzle

``````>>> game = readGame("""
...  8 __  9 __     10 __ __ 12     16 __ 15 __     __ __ __  4
... __ __ 15 __     __ __  5 __     __  7 __ 10     __ __ 13 __
...  2 __ __ __     __ __ __  4     __ __ __ __     __ 16 __ 14
... __  6 __  3     __ __ 14 __     __ __ 11 __      9 __ __ __
...
...
... __ __ __ __     __  9 __ __      1 __ __  2     __ __ __  7
... 11 __ __ __     14 __ __  6     __ __ __ __     __ 13 __ __
... __  7 __ 16     __  2 __ __     12 __ __ __     __ __  1 __
... __ __ __  5      8 __ __ 13     __  3 __ __     __ __ __  9
...
... 12 __  4 __     __ __  7 __     13 __  8 __     11 __ __ __
... __  5 __  8     __ 13 __ 10     __ 16 __  4     __ __ __ __
... __ __ 14 __     __ __  9 __      6 __ __ 11     __  1 __  3
...  1 __ __ __      3 __ __  5     __ __ __ __      6 __ 16 __
...
...
... 14 __  7 __     __ __ 10 __     __ 12 __  9     __  8  2 __
... __ 16 __ 12     __ 14 __  3     __ __ __ __     13 __ __ 11
...  5 10 __ __      6 __ 11 __     __ __ 14 __     __  7 __ __
... 15 __  1 __     __ __ __  2     __ __ __  5     __ __ __ 12
... """)
>>>
>>> solvedGame = solveGame(game)
>>> printGame(solvedGame)

8  1  9  7   10  3  2 12   16 14 15 13    5 11  6  4
4 11 15 14    9 16  5  8    2  7  6 10   12  3 13  1
2 12  5 10   11  6 13  4    8  1  9  3   15 16  7 14
13  6 16  3    1 15 14  7    5  4 11 12    9  2 10  8

3  8 13 15    5  9 12 16    1 11 10  2    4  6 14  7
11  4 12  1   14 10 15  6    9  8  7 16    2 13  3  5
9  7  6 16    4  2  3 11   12  5 13 14    8 15  1 10
10 14  2  5    8  7  1 13   15  3  4  6   16 12 11  9

12  3  4  6   16  1  7 14   13  9  8 15   11 10  5  2
7  5 11  8    2 13  6 10    3 16  1  4   14  9 12 15
16  2 14 13   12  4  9 15    6 10  5 11    7  1  8  3
1 15 10  9    3 11  8  5   14  2 12  7    6  4 16 13

14 13  7  4   15  5 10  1   11 12 16  9    3  8  2  6
6 16  8 12    7 14  4  3   10 15  2  1   13  5  9 11
5 10  3  2    6 12 11  9    4 13 14  8    1  7 15 16
15  9  1 11   13  8 16  2    7  6  3  5   10 14  4 12

>>>
``````

For this hard 16x16 puzzle, `solveGame(.)` took about 50 seconds. Not bad. And the maximum number of games simultaneously on the `solutionList` was 1186. Keep in mind that the total number of possible grid-arrangements for a 16x16 grid is 16256, which is about 10300. Obviously, 1,186 is much much smaller.

With backtracking on a 16x16 grid, you're likely to explore around `16!` (sixteen factorial) possibilities, which is about 20 trillion. Again, 1186 is much smaller.

### Tests, Tweaks & The Whole Thing

Finally, it's now time to write tests.

I made some tweaks to `sudoku.py` and introduced test cases in `test_sudoku.py`. The tweaks are mostly around slight performance improvements and some additional parameterization.

`sudoku.py`:

``````import math;
from collections import defaultdict;
import itertools;
import functools;
import copy;

@functools.lru_cache()
def intSqrt (n):
"Computes integer square-root of perfect squares.";
rootN = int(math.sqrt(n));
if rootN ** 2 != n:
raise ValueError(f"Expected a perfect square, not: {n}");
return rootN;

"Reads a string-represented game as a list of rows.";
rows = [];
for line in s.splitlines():
if line.strip():
rows.append([]);
for word in line.split():
if word.isdigit():
rows[-1].append(int(word));
elif word == "_" * len(word):
rows[-1].append("_");
else:
raise ValueError(f"Unexpected word: {word}");
n = len(rows);
rootN = intSqrt(n);
assert rootN ** 2 == n;
for i in range(n):
if len(rows[i]) != n:
raise ValueError("Game-grid isn't a perfect square.");
return rows;

def printGame (game):
"Pretty-prints `game`.";
n = len(game);
rootN = intSqrt(n);
maxDigits = len(str(n));    # 16 -> len('16') -> 2
output = "";
leftPad = lambda s: s if len(s) == maxDigits else leftPad(" " + s);
for (i, row) in enumerate(game):
if i % rootN == 0:
output += "\n";
for (j, cell) in enumerate(row):
if j % rootN == 0:
output += " " * 2;
output += leftPad(str(cell)) + " ";
output += "\n";
print(output);

def getRow (i, game):
"Returns the i^th row in `game`.";
return game[i];

def getCol (j, game):
"Returns the j^th column in `game`.";
return list(map(lambda row: row[j], game));

def getBoxStartPos (i, j, rootN):
"Returns starting position of box containing (i, j).";
iBox = math.floor(i / rootN) * rootN;
jBox = math.floor(j / rootN) * rootN;
return (iBox, jBox)

def getFlatBox (i, j, game):
"Returns inner-box w.r.t (i, j), as a _flat_ list.";
rootN = intSqrt(len(game));
iBox, jBox = getBoxStartPos(i, j, rootN);
flatBox = [];
for ii in range(iBox, iBox + rootN):
for jj in range (jBox, jBox + rootN):
flatBox.append(game[ii][jj]);
return flatBox;

def collectPossibleTrioLists (game):
"Collects possibly deducible trios, (i, j, x), in `game`.";
n, rootN = len(game), intSqrt(len(game));
isFilled = True;                # Initial assumption
cellwise = defaultdict(list);
rowwise = defaultdict(list);
colwise = defaultdict(list);
boxwise = defaultdict(list);
#
@functools.lru_cache()
def getRowSet (i): return set(getRow(i, game));
#
@functools.lru_cache()
def getColSet (j): return set(getCol(j, game));
#
@functools.lru_cache()
def getBoxSet (iBox, jBox):
return set(getFlatBox(iBox, jBox, game));
#
iBox, jBox = (0, 0);
for i in range(n):
if i % rootN == 0:
iBox = i;
for j in range(n):
if j % rootN == 0:
jBox = j;
if game[i][j] == "_":
isFilled = False;
rowSet = getRowSet(i);
colSet = getColSet(j);
boxSet = getBoxSet(iBox, jBox);
for x in range(1, n+1):
if x not in (rowSet | colSet | boxSet):
trio = (i, j, x);
cellwise[(i, j)].append(trio);
rowwise[(i, x)].append(trio);
colwise[(j, x)].append(trio);
boxwise[((iBox, jBox), x)].append(trio);
possibleTrioLists = itertools.chain(
cellwise.values(), rowwise.values(),
colwise.values(), boxwise.values(),
);
return (possibleTrioLists, isFilled);

def deduce (game):
"Tries to logically fill game using the rules of Sudoku.";
putCount = 0;
minTrioList = None;
(iterTrioLists, isFilled) = collectPossibleTrioLists(game);
for trioList in iterTrioLists:
if len(trioList) == 1:
(i, j, x) = trioList;
if game[i][j] == "_":
game[i][j] = x;
putCount += 1;
elif len(trioList) == 0:
pass;
elif (not minTrioList) or len(trioList) < len(minTrioList):
minTrioList = trioList;
# Finally ...
if putCount:
return deduce(game);
# otherwise ...
#printGame(game);
return (isFilled, minTrioList);

def solveGame (inputGame, verbose=False, search="bfs"):
"Solves `inputGame` using deductions and BFS/DFS.";
search = search.lower();
if search not in ["bfs", "dfs"]:
raise ValueError(f"Unexpected param `search`: {search}");
assert search in ["bfs", "dfs"];
solutionList = [inputGame];         # Search-list (AKA Open-list)
maxSolListLen = 1;
while solutionList:
game = solutionList.pop(0 if search == "bfs" else -1);
(isFilled, minTrioList) = deduce(game);
if isFilled and checkSolved(game):
if verbose:
print(f"Search list's maximum length: {maxSolListLen}");
return game;
elif minTrioList:
for (i, j, x) in minTrioList:
newGame = copy.deepcopy(game);
newGame[i][j] = x;
solutionList.append(newGame);
if len(solutionList) > maxSolListLen:
maxSolListLen = len(solutionList);
# otherwise ...
raise ValueError("Can't solve game.");

def checkSolved (game):
n = len(game);
rootN = intSqrt(n);
fullSet = set(range(1, n+1));
for k in range(0, n):
rowAndColOk = (
set(getRow(k, game)) == fullSet and
set(getCol(k, game)) == fullSet #and
);
if not rowAndColOk:
return False;
for i in range(0, n, rootN):
for j in range(0, n, rootN):
if set(getFlatBox(i, j, game)) != fullSet:
return False;
return True;

# End xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
``````

`test_sudoku.py`:

``````import time;
import functools;

from sudoku import *;

def test_2x2 ():
3 4 _ _
_ 2 _ _
_ _ 4 _
_ _ 2 1
""");
assert game == [
[ 3,    4,  "_", "_"],
["_",   2,  "_", "_"],
["_",  "_",  4,  "_"],
["_", "_",   2,   1],
];
printGame(game);
solvedGame = solveGame(game);
assert checkSolved(solvedGame);
printGame(solvedGame);

1 1 1 _
2 2 _ 2
3 _ 3 3
_ 4 4 4
""");
except ValueError: pass;
else: assert False;

def test_3x3_and_4x4 ():
gameTexts = [
# Easy:
"""
5 3 _   _ 7 _   _ _ _
6 _ _   1 9 5   _ _ _
_ 9 8   _ _ _   _ 6 _

8 _ _   _ 6 _   _ _ 3
4 _ _   8 _ 3   _ _ 1
7 _ _   _ 2 _   _ _ 6

_ 6 _   _ _ _   2 8 _
_ _ _   4 1 9   _ _ 5
_ _ _   _ 8 _   _ 7 9
""",

# Hard:
"""
_ 1 3   _ _ _   _ 5 _
_ _ 5   _ _ 8   _ 4 3
_ 6 _   _ _ _   _ _ 7

_ _ _   4 _ _   _ _ _
_ _ 1   _ _ 2   _ _ _
_ _ _   _ _ 5   _ 6 8

_ 5 4   2 _ _   _ _ 9
2 _ _   3 _ _   _ 8 _
_ _ 7   5 _ 1   _ _ _
""",

# Hard:
"""
9 _ _   _ _ 7   1 2 _
6 _ 7   9 _ _   _ _ _
2 _ _   _ _ _   _ 8 _

_ _ _   3 _ _   _ _ _
_ _ 8   _ _ _   _ 4 3
_ _ _   _ _ 5   9 _ _

_ 4 _   1 _ _   _ _ _
_ _ _   _ _ _   6 5 _
_ 3 5   _ _ 8   _ _ _
""",

# Hard:
"""
_ _ 7   8 _ _   _ _ _
_ _ 3   7 4 _   _ _ 6
2 8 _   _ 5 _   4 _ _

1 9 _   _ _ _   _ _ _
7 _ _   4 8 9   _ _ 1
_ _ _   _ _ _   _ 4 3

_ _ 9   _ 3 _   _ 6 2
8 _ _   _ 6 5   3 _ _
_ _ _   _ _ 4   1 _ _
""",

# Hard:
"""
_ _ _   _ _ _   _ _ 2
_ 2 3   _ _ _   _ _ 1
_ _ _   _ 6 8   _ _ _

_ 9 4   5 _ _   _ _ 3
_ 7 _   _ 1 _   _ 5 _
_ _ _   _ _ _   _ 8 _

_ 5 _   7 4 _   _ _ _
6 _ _   _ _ _   7 2 _
_ _ 9   _ _ _   _ 1 _
""",

#Hard:
"""
_ _ _   _ _ _   3 _ _
_ _ 1   _ _ 9   _ 8 _
2 _ _   _ 3 _   _ _ 7

6 _ _   _ 2 _   1 _ _
_ _ _   5 _ 3   _ _ _
_ 8 _   _ _ _   _ _ 9

7 _ _   4 6 _   _ _ 3
_ 2 _   _ _ _   _ _ _
_ _ 9   _ 7 _   _ 5 _
""",

# Easy 16x16:
"""
__  4 __ __      8 __ 16 __     11 __  1 __     __  6 __ 14
3 __ __  9     __ 15 __  4     10  7 __ 13     __ __ 12 __
__  6 __ __      2 11 __ __      8 __ __ __      3 __ __ __
15 __ __ __     __ __ __ 13     __ __ 14 __     __  2 __  4

__ __ __  8     __  3 __ __      7 __ __ __      5 __ __ __
__ __ __ __     __ __ 14 __     __ __ __ 10     __ 16 __ 13
__ __  9  2      5 __ __ __     __  8 __ __     11 __ __ __
12 __  1 __     __ __ __ 16     __ __ 13 __     __ __  3 __

__ __ __ 12     15 __ __ __     __  6 __ __     13 __  4  7
16  1 13 __     10 __ __  3     __ __  7 __     __  9 __ __
6 __ __ __     __ __ 11 __      4 __ __  9     __ __  2 10
__  3 __ __     __ 16 __ __     __ 14  8 __     __ 11 __ __

5 11  3 10     __ __ __  8     __ __ 12  4     __ __ __  1
__ 14 __ __     11  9 __ __     __ 13 15 __      4 __  5 __
13 __  4 __      6 __ __ __     __ __ __  2     __ 12 __  9
__ 12 __ 16     __ 13 __ __     __  1 __ __      6 __ 15 __
""",

# Hard 16x16:
"""
8 __  9 __     10 __ __ 12     16 __ 15 __     __ __ __  4
__ __ 15 __     __ __  5 __     __  7 __ 10     __ __ 13 __
2 __ __ __     __ __ __  4     __ __ __ __     __ 16 __ 14
__  6 __  3     __ __ 14 __     __ __ 11 __      9 __ __ __

__ __ __ __     __  9 __ __      1 __ __  2     __ __ __  7
11 __ __ __     14 __ __  6     __ __ __ __     __ 13 __ __
__  7 __ 16     __  2 __ __     12 __ __ __     __ __  1 __
__ __ __  5      8 __ __ 13     __  3 __ __     __ __ __  9

12 __  4 __     __ __  7 __     13 __  8 __     11 __ __ __
__  5 __  8     __ 13 __ 10     __ 16 __  4     __ __ __ __
__ __ 14 __     __ __  9 __      6 __ __ 11     __  1 __  3
1 __ __ __      3 __ __  5     __ __ __ __      6 __ 16 __

14 __  7 __     __ __ 10 __     __ 12 __  9     __  8  2 __
__ 16 __ 12     __ 14 __  3     __ __ __ __     13 __ __ 11
5 10 __ __      6 __ 11 __     __ __ 14 __     __  7 __ __
15 __  1 __     __ __ __  2     __ __ __  5     __ __ __ 12
""",
]
for gameText in  gameTexts[0:]:
print("---------------------------------------------------------");
printGame(game);
solvedGame = solveGame(game, verbose=True, search="bfs");
assert checkSolved(solvedGame);
printGame(solvedGame);
print("---------------------------------------------------------");

def timer (fn):
@functools.wraps(fn)
def wrapper (*a, **ka):
t0 = time.time();
result = fn(*a, **ka);
tDiff = time.time() - t0;
print(f"Time taken by {fn.__name__}(.): {tDiff}");
return result;
return wrapper;

if __name__ == "__main__":
solveGame = timer(solveGame);
test_2x2();
test_3x3_and_4x4();

# End xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
``````

Run `\$ python test_sudoku.py` to run the tests. You could instead run `\$ pytest` if you prefer. But with the former command, you'll see time-related output and pretty-printed game solutions.

Image credit: Solved Sudoku image via Wikimedia Commons, under CC BY-SA 3.0