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):
- appear in each row exactly once,
- appear in each column exactly once, and
- 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 are2and4. We can't put2in the last row as it's already in there. Hence, in the first column,2must be in the second last row. And then it follows, that4must be in the last row. Thus, we get:
3 4 _ _
1 2 _ _
2 _ 4 3
4 _ 2 1
- Consider the second column. The number
1can'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.
1must be in the first row as it can't be in the second row. Next, it follows that3must 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.
2must be in the first row as it can't be in the second row. Next, it follows that4must 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;
def readGame (s):
"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 rootNxrootN 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 *
>>>
>>> game = readGame("""
... 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
ith row. - All the numbers in the
jth 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 ith row is very easy. That's just game[i]. For getting the jth 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 NxN game, the box size is rootNxrootN. 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 *
>>>
>>> game = readGame("""
... 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[0];
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 xs, 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 xs 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 trioLists. On combining the values in cellwise with those from rowwise, etc., we get a combined iterable of trioLists.
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 *
>>>
>>> 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 _ _ _
... """)
>>>
>>> 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 trioLists 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[0];
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 *
>>>
>>> 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 _ _ _
... """)
>>>
>>> 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;
def readGame (s):
"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[0];
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 ():
game = readGame("""
3 4 _ _
_ 2 _ _
_ _ 4 _
_ _ 2 1
""");
assert game == [
[ 3, 4, "_", "_"],
["_", 2, "_", "_"],
["_", "_", 4, "_"],
["_", "_", 2, 1],
];
printGame(game);
solvedGame = solveGame(game);
assert checkSolved(solvedGame);
printGame(solvedGame);
badGame = readGame("""
1 1 1 _
2 2 _ 2
3 _ 3 3
_ 4 4 4
""");
try: solveGame(badGame);
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("---------------------------------------------------------");
game = readGame(gameText);
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