Ok, First things first: Writing a Sudoku solver is not a particularly impressive feat. This post is about how to model this problem and how Python can help with that. After we write the Soduku solver, we will demonstrate some of the tricks we learned into other domains.

Lets start by talking a bit about slices.

## Slices

``````s = slice(1, 2, 3)

s.start, s.stop, s.step
# >>> (1, 2, 3)
``````

This doesn’t look very impressive. `slice` is a Python built-in, yet it doesn’t seem to accomplish anything more than a `namedtuple` would. So, why does it exist? To find out, lets try something:

``````class Slicer:
def __getitem__(self, index):
return index

slicer = Slicer()
slicer[1]
# >>> 1
slicer[1:]
# >>> slice(1, None, None)
slicer[:2]
# >>> slice(None, 2, None)
slicer[1:2]
# >>> slice(1, 2, None)
slicer[1:2:3]
# >>> slice(1, 2, 3)
slicer[1::3]
# >>> slice(1, None, 3)
slicer[:2:3]
# >>> slice(None, 2, 3)
slicer[::3]
# >>> slice(None, None, 3)
slicer[:]
# >>> slice(None, None, None)
``````

So, the square-bracket notation will invoke `__getitem__` but, before doing that, it will convert the `a:b:c` notation into a `slice(a, b, c)` constructor.

Another related trick is that indexes, ie arguments to the square bracket notation, can be pairs of things:

``````slicer[1, 2]
# >>> (1, 2)
slicer[1, 2, 3]
# >>> (1, 2, 3)
slicer[1, 2:3]
# >>> (1, slice(2, 3, None))
``````

This particular trick, however, is much less impressive since in Python it’s the comma (`,`) that makes a tuple and not the parentheses. This is why return statements with more than one values work as they do:

``````def foo():
return 1, 2
foo()
# >>> (1, 2)
``````

and why dangling commas can ruin your day:

``````a = 1,
isinstance(a, int)
# >>> False
a
# >>> (1,)
``````

Ok. Enough with slices and indexes. Back to Sudoku.

## Modeling a Sudoku puzzle

Lets get started. This is a class that represents a Sudoku puzzle:

``````class Sudoku(list):
``````

(Record scratch) Wait, a list? Shouldn’t we represent a Sudoku puzzle as a two-dimensional list?

Well, here’s the issue: Sometimes it is better to treat a Sudoku puzzle as a two-dimensional list, for example when you are verifying that no `3`s exist in the same row, and sometimes as a one-dimensional list, for example when you are iterating over every cell in the puzzle. So, which should it be?

My answer is (… drumroll …) both, almost. We store it as a one-dimensional list, which is why we simply inherit from `list`. But, when we access it, we can do it either as a one-dimensional or a two-dimensional list. Lets see how this works:

``````class Sudoku(list):
def __getitem__(self, index):
try:
x, y = index
except Exception:
return super().__getitem__(index)

rows = [self[i:i + 9] for i in range(0, 9 * 9, 9)]  # 0, 9, 18, ...
if isinstance(x, slice):
return [row[y] for row in rows[x]]
else:
return rows[x][y]
``````

So, if our index is a number or a slice, we will go to the `super().__getitem__(index)` line and we will be treating the object like a one-dimensional list:

``````s = Sudoku(range(81))
s[3]
# >>> 3
s[3:9]
# >>> [3, 4, 5, 6, 7, 8]
``````

(Notice how we don’t even have to write an `__init__` method. `list`’s initialization works just fine)

but if our index is a pair, the object will be split into rows and we will access them as a two-dimensional list:

``````# Get the 3rd cell of the 2nd row
s[1, 2]
# >>> 11
``````

The best part is that we can use slices for any of the coordinates:

``````# Get the 1st row
s[0, :]
# >>> [0, 1, 2, 3, 4, 5, 6, 7, 8]

# Get the 1st column
s[:, 0]
# >>> [0, 9, 18, 27, 36, 45, 54, 63, 72]

# Get part of the 4th row
s[3, 3:7]
# >>> [30, 31, 32, 33]

# Get the bottom-left 3x3 "box"
s[6:9, 0:3]
# >>> [[54, 55, 56],
# ...  [63, 64, 65],
# ...  [72, 73, 74]]
``````

And we can pretty-print our puzzle without any extra code:

``````s[:, :]
# >>> [[0,  1,  2,  3,  4,  5,  6,  7,  8 ],
# ...  [9,  10, 11, 12, 13, 14, 15, 16, 17],
# ...  [18, 19, 20, 21, 22, 23, 24, 25, 26],
# ...  [27, 28, 29, 30, 31, 32, 33, 34, 35],
# ...  [36, 37, 38, 39, 40, 41, 42, 43, 44],
# ...  [45, 46, 47, 48, 49, 50, 51, 52, 53],
# ...  [54, 55, 56, 57, 58, 59, 60, 61, 62],
# ...  [63, 64, 65, 66, 67, 68, 69, 70, 71],
# ...  [72, 73, 74, 75, 76, 77, 78, 79, 80]]
``````

(By the way, this way of accessing rows, columns and boxes should feel very familiar to you if you’ve worked with NumPy)

## Validation

``````class Sudoku(list):
# __getitem__

def is_valid(self):
""" Verifies that `self` follows the rules of a Sudoku puzzle. """

# Make sure size is correct
if not len(self) == 9 * 9:
return False

# Make sure all digits are between 0 and 9
if set(self) > set(range(10)):
return False

# Rows
if not all((self._check_unique(self[i, :]) for i in range(9))):
return False

# Columns
if not all((self._check_unique(self[:, i]) for i in range(9))):
return False

# 3x3 boxes
for row_start in range(0, 9, 3):  # 0, 3, 6
for column_start in range(0, 9, 3):  # 0, 3, 6
box = self[row_start:row_start + 3,
column_start:column_start + 3]
flattened_box = [number for row in box for number in row]
if not self._check_unique(flattened_box):
return False

return True

@staticmethod
def _check_unique(numbers):
""" Verifies that each number in `numbers` apart from `0` appears at
most once.
"""

numbers = [number for number in numbers if number != 0]
return len(numbers) == len(set(numbers))
``````

The “dual nature” of our Sudoku puzzle representation really shines here. We can do things like `len(self)` and `set(self)` which treat `self` as a one-dimensional list and we can resolve rows, columns and 3x3 boxes by treating `self` as a two-dimensional list.

## Recursion

Now lets actually solve the puzzle. We won’t do anything fancier that a simple brute-force solution, ie try every possible value for all cells that have `0` (ie are empty) until either the puzzle becomes invalid or full.

``````class Sudoku(list):
# __getitem__, is_valid, _check_unique

def solve(self):
""" Recursively solve the puzzle. If the current version is invalid or
we can't solve any "descendant", return `None`. If there are no
empty cells left, return `self`. If a descendant can get solved,
return the solution.

- A "descendant" is a slightly modified copy of `self` where the
first empty cell is replaced with all numbers between 1 and 9
"""

if not self.is_valid():
return None

if 0 not in self:
# We ran out of empty cells, this is a complete, valid puzzle
return self

empty_pos = self.index(0)
for candidate in range(1, 10):  # 1, 2, ... 9
descendant = Sudoku(self[:empty_pos] +
[candidate] +
self[empty_pos + 1:])
solved = descendant.solve()
if solved is not None:
return solved

# We ran out of candidates, none worked
return None
``````

This method isn’t the most sophisticated or impressive thing I’ve ever written. What I want to draw attention to here is how being able to treat the puzzle as a one-dimensional list makes things very easy and elegant while each statement makes its purpose very clear:

• `pos = self.index(0)` to find the first empty cell
• `descendant = Sudoku(self[:pos] + [candidate] + self[pos + 1:])` to make a copy where the cell in position `pos` is replaced with `candidate`

## Demo time

You can copy paste the code and run it yourselves, but here it is in action:

``````puzzle = Sudoku([0, 4, 0, 0, 0, 6, 0, 0, 0,
8, 0, 7, 0, 0, 3, 0, 4, 0,
0, 0, 0, 9, 0, 0, 1, 0, 0,
2, 0, 9, 0, 7, 0, 0, 0, 4,
6, 0, 0, 8, 0, 4, 0, 0, 2,
4, 0, 0, 0, 6, 0, 7, 0, 9,
0, 0, 1, 0, 0, 9, 0, 0, 0,
0, 6, 0, 2, 0, 0, 9, 0, 7,
0, 0, 0, 6, 0, 0, 0, 5, 0])
solved = puzzle.solve()  # 1.81 seconds
solved[:, :]
# >>> [[1, 4, 5, 7, 2, 6, 3, 9, 8],
# ...  [8, 9, 7, 5, 1, 3, 2, 4, 6],
# ...  [3, 2, 6, 9, 4, 8, 1, 7, 5],
# ...  [2, 1, 9, 3, 7, 5, 8, 6, 4],
# ...  [6, 7, 3, 8, 9, 4, 5, 1, 2],
# ...  [4, 5, 8, 1, 6, 2, 7, 3, 9],
# ...  [7, 8, 1, 4, 5, 9, 6, 2, 3],
# ...  [5, 6, 4, 2, 3, 1, 9, 8, 7],
# ...  [9, 3, 2, 6, 8, 7, 4, 5, 1]]
``````

## Other uses of `__getitem__` and slices

This section is just for inspiration. Keep in mind that there is nothing we do here that can’t be done without using `__getitem__` and slices. My argument is that the resulting code looks more natural while being very descriptive of its purpose. We are essentially accessing “virtual lists” that generate their contents the moment we ask for them.

### Fixtures for testing {json:api} responses

If you’ve worked with {json:api}, you know that the server responses look like this:

``````{"data": [{"type": "articles",
"id": "1",
"attributes": {"title": "Article 1", "created": "2020-09-01"},
"relationships": {"author": {"data": {"type": "users", "id": 1},
"self": "/articles/1/relationships/author"}}},
{"type": "articles",
"id": "2",
"attributes": {"title": "Article 2", "created": "2020-09-02"},
"relationships": {"author": {"data": {"type": "users", "id": 2},
"self": "/articles/2/relationships/author"},
"included": [{"type": "users",
"id": "1",
"attributes": {"username": "user1", "full_name": "User 1"},
{"type": "users",
"id": "2",
"attributes": {"username": "user2", "full_name": "User 2"},
``````

The advantages of an API having such detailed responses are many, but having to write these by hand for unit-tests is very frustrating (I should know, I just did it). Thankfully, writing a function that creates these is relatively easy. Lets give it a shot:

``````class JsonApiFixtures:
def __init__(self, plural_type, singular_type=None, extra=None):
if singular_type is None:
singular_type = plural_type[:-1]  # items => item
if extra is None:
extra = {}

self.plural_type = plural_type
self.singular_type = singular_type
self.extra = deepcopy(extra)

def _get(self, i):
result = {'type': self.plural_type,
'id': str(i),
'attributes': {'name': ("{} {}".
format(self.singular_type, i))}}
result.update(self.extra)
return result

def __getitem__(self, index):
if isinstance(index, slice):
start = index.start if index.start is not None else 1
stop = index.stop
step = index.step if index.step is not None else 1
return [self._get(i) for i in range(start, stop, step)]
else:
return self._get(index)
``````
``````items = JsonApiFixtures('items')
items[1]
# >>> {'type': "items", 'id': "1", 'attributes': {'name': "item 1"}}
items[1:4]
# >>> [{'type': "items", 'id': "1", 'attributes': {'name': "item 1"}},
# ...  {'type': "items", 'id': "2", 'attributes': {'name': "item 2"}},
# ...  {'type': "items", 'id': "3", 'attributes': {'name': "item 3"}}]

articles = JsonApiFixtures(
'articles',
extra={'relationships': {
'author': {'data': {'type': "users", 'id': "1"},
'related': "/users/1"}},
}}
)

articles[1:3]
# >>> [{'type': "articles",
# ...   'id': "1",
# ...   'attributes': {'name': "article 1"},
# ...   'relationships': {'author': {'data': {'type': "users", 'id': "1"},
# ...                                          'related': "/users/1"}}}},
# ...   {'type': "articles",
# ...    'id': "1",
# ...    'attributes': {'name': "article 1"},
# ...    'relationships': {'author': {'data': {'type': "users", 'id': "1"},
# ...                                           'related': "/users/1"}}}}]

assert (test_client.get('/articles?filter[odd]=True').json()['data'] ==
articles[1:11:2])
``````

### Fixtures for testing Django ORM objects

Aka “poor man’s factory-boy”. This time we will dive straight into the code:

``````class DjangoOrmFixtures:
def __init__(self, model, extra=None, **kwargs):
self.model = model
self.kwargs = kwargs

def __call__(self, **kwargs):
return self.__class__(self.model, **{**kwargs, **self.kwargs})

def _get(self, i):
result = {}
for key, value in self.kwargs.items():
try:
value = value.format(i)
except Exception:
pass
result[key] = value
return self.model.objects.create(**result)

def __getitem__(self, index):
if isinstance(index, slice):
start = index.start or 1
stop = index.stop
step = index.step or 1
return [self._get(i) for i in range(start, stop, step)]
else:
return self._get(index)
``````
``````ArticleFixtures = DjangoOrmFixtures(Article,
slug="article-{}",
title="Article {}",
content="Content of article {}")
UserFixtures = DjangoOrmFixtures(User,