Sudoku in Python

July 21, 2021 7-minute read

What is sudoku?

Sudoku is a 81 square game, whereing all you need to do is just enter a single digit number(1-9)(and not 0 Computer Nerds know why I said this :) ) in a box.

    2 - 7 |9 - 5 |- 8 1
    8 - 3 |7 - 6 |- 4 9
    4 - 1 |8 - 3 |- 7 6
    ------+------+------
    - - - |4 - 8 |1 9 2
    3 8 4 |1 9 2 |- - -
    - - - |- - - |4 3 8
    ------+------+------
    - - - |- 7 - |8 - 5
    9 - 5 |- 8 - |7 - 4
    7 - 8 |- 6 - |9 - 3

Sounds easy right? Not Really. There are some rules to this, particularly w.r.t How to add a number, a number can only be added in a box

if and only if it is unique in a ROW, COLUMN, or a 3x3 BOX as shown below:-

  Box       Block   Column
   |          |        |
    \       - - -      |
    [2] - 7|9 - 5 |- 8 1
     8 - 3 |7 - 6 |- 4 9
     4 - 1 |8 - 3 |- 7 6
            - - -
     ------+------+------
     - - - |4 - 8 |1 9 2 --- Row
     3 8 4 |1 9 2 |- - -
     - - - |- - - |4 3 8
     ------+------+------
     - - - |- 7 - |8 - 5
     9 - 5 |- 8 - |7 - 4
     7 - 8 |- 6 - |9 - 3

So how about lets make it more intresting and solve it not with pen/pencil, but with python code(Why python, easy for demonstration purpose, can use any other programming language).

There are many ways in which this problem can be solved, BackTracking being one of them. The method which I will show is a bit different not because its unique in terms of algorithm, but in terms of thinking with a different angle.

What did you mean by the last sentence?

Imagine you have a Multiple Choice Question(MCQ) with 4 options. Now the probability of one option being correct is 25%(1/4). Now lets suppose magically/logically you know that one option is not correct, the odds of one option being correct has increased to 33%(1/3). This can go as high as 50%(1/2). The lesson that can be taken is sometimes in order to reach the right answer, one way the can be used is to eliminate the wrong ones. And that’s what we are gonna do here.

How exactly?

The Box in which numbers will be filled

for this, we will not really use 9x9 2D Array, instead have shown how exactly would the data structure look like

 # Intead on naming row by their index, will use conventions such as A1, A2....H9
 rows = 'ABCDEFGHI'
 cols = '123456789'

 # Cross product of elements in A and elements in B.
 def cross(A, B):
     return [s + t for s in A for t in B]

 # Something like [A1, .., B2,....]
 boxes = cross(rows, cols)

 # Define row units of a sudoku
 # Something like [[A1,...], [B1,....]]
 row_units = [cross(r, cols) for r in rows]

 # Define column units of a sudoku
 # Something like [[A1,...], [A2,....]]
 row_units = [cross(r, cols) for r in rows]

 # Define square units of a sudoku
 # Something like [[A1,A2,...,B1,..], [A4,....]]
 square_units = [cross(rs, cs) for rs in ('ABC', 'DEF', 'GHI') for cs in ('123', '456', '789')]

 # Define diagonal units of a sudoku
 # Something like [[A1,B2,..], [...]]
 diagonal_units = [[x + y for x, y in zip(rows, cols)], [x + y for x, y in zip(rows, cols[::-1])]]

 # Create a list of all units of a sudoku
 unitlist = row_units + column_units + square_units + diagonal_units

 # Create a dictionary of peers of each box
 # Something like {'I6': set(['I9', 'I8...])}
 units = dict((s, [u for u in unitlist if s in u]) for s in boxes)
 peers = dict((s, set(sum(units[s], [])) - {s}) for s in boxes)

Since everthing’s in place, lets start the process. Just a Disclaimer, the input will be
taken in string format, sort of like this(2………….6) where . is empty boxes. After fetching the
input, replace the . with values that can be added(whole set for now) in a box.
Something like - {‘I6’: ‘123456789’…}
```
 chars = []
 digits = '123456789'
 for c in grid:
     if c in digits:
         chars.append(c)
     if c == '.':
         chars.append(digits)
 assert len(chars) == 81
 return dict(zip(boxes, chars))
```

Having added elements that can be added, it time for elimination part, this is further divided into sub parts

3.1) First we shall perform elimination such that if a box has a value, it does not make sense to keep them in the box’s peer.

# Here values is the dict. mentioned above
solved_values = [box for box in values.keys() if len(values[box]) == 1] # Fetch those boxes that have only 1 value
for box in solved_values:
    digit = values[box] # Fetch the single digit
    for peer in peers[box]:
        values[peer] = values[peer].replace(digit, '') # Sort of remove the digit from larger number pool
return values

3.2) This is followed by Naked Twins Strategy(don’t know who gave this name). Now I wanted to explain it in words but this link has just made it easier to understand it.

NOTE:- Please watch the tutorial before moving ahead

naked_twin_dic = {}
for unit in unitlist:
    # Build a dictionary to identify a naked twin pair
    vdic = {}
    for box in unit:
        # Identify box containing only 2 possibilities as a candidate for a naked twin
        if len(values[box]) == 2:
            if not values[box] in vdic:
                vdic[values[box]] = [box]
            else:
                vdic[values[box]].append(box)
    # Examine the dictionary to validate the candidates present as
    # naked twin pairs
    for key in vdic:
        # Condition for the candidate to be a naked twin pair
        if len(vdic[key]) == 2:
            if not key in naked_twin_dic:
                naked_twin_dic[key] = [unit]
            else:
                naked_twin_dic[key].append(unit)

# now naked twin dict will have key as 2 possibilites and value as array of bozes that have them
# eg:- {'57': [['A1', 'B2', 'C3', 'D4', 'E5', 'F6', 'G7', 'H8', 'I9']]}
# Eliminate the naked twins as possibilities for their peers
for key in naked_twin_dic:
    for unit in naked_twin_dic[key]:
        for box in unit:
            if values[box] != key:
                assign_value(values, box, values[box].replace(key[0], ''))
                assign_value(values, box, values[box].replace(key[1], ''))

3.3) At the end, a bit counter-intuitive move is done wherein the box in which only value is possible in one box, will set that value in the box.

for unit in unitlist:
for digit in '123456789':
    dplaces = [box for box in unit if digit in values[box]]
    # This line checks if only one value is possible in one box
    if len(dplaces) == 1:
        values[dplaces[0]] = digit
return values

One these reductions are done, will check if there comes a points wherein it cannot be reduced further. Will also add a check if there arises a box which was left empty, thereby proving that sudoku cannot be solved ;), will simply return false

while not stalled:
    solved_values_before = len([box for box in values.keys() if len(values[box]) == 1])
    values = eliminate(values)
    values = naked_twins(values)
    values = only_choice(values)
    solved_values_after = len([box for box in values.keys() if len(values[box]) == 1])
    # Check if it can be solved further(happy flow)
    stalled = solved_values_before == solved_values_after
    # Check if it can be solved further(sad flow)
    if len([box for box in values.keys() if len(values[box]) == 0]):
        return False

Now the next problem is how do we iterate(i.e. to go to each square and do the necessary computations), for this DFS(Depth First Search) is considered. Reason is that backtracking is needed for restarting from a different path. The traversal starts from box of fewest possibilities(think why?)

values = reduce_puzzle(values) # do the reduction part
if values is False:
    return False  ## Failed
if all(len(values[s]) == 1 for s in boxes):
    return values  ## Solved!
# Choose one of the unfilled boxes with the fewest possibilities
n, s = min((len(values[s]), s) for s in boxes if len(values[s]) > 1)
# Now use recurrence to solve each one of the resulting sudokus
for value in values[s]:
    new_sudoku = values.copy()
    new_sudoku[s] = value
    attempt = search(new_sudoku)
    if attempt:
        return attempt

And TADA: Your very own sudoku is solved

2 6 7 |9 4 5 |3 8 1
8 5 3 |7 1 6 |2 4 9
4 9 1 |8 2 3 |5 7 6
------+------+------
5 7 6 |4 3 8 |1 9 2
3 8 4 |1 9 2 |6 5 7
1 2 9 |6 5 7 |4 3 8
------+------+------
6 4 2 |3 7 9 |8 1 5
9 3 5 |2 8 1 |7 6 4
7 1 8 |5 6 4 |9 2 3

Woah! This was quite a mental exercise. Hope you had fun learning along with me. See you around