I’ve never been particularly interested in puzzle games. Figuring out software has filled that niche for me (plenty puzzling enough). So, I’ve never done a Sudoku puzzle. Recently I read a post about Tredoku, which is a kind of three-dimensional Sudoku.

In that post was an unsolved Tredoku puzzle. I wasn’t tempted to try to solve it myself, but I did think it might be fun to see if I could write some Python to do it.

Figure 1. Tredoku puzzle.

It took three tries to get a good algorithm. I needed a fourth pass because I didn’t know the Sudoku rule that the 3×3 blocks also must contain all nine digits. My version 3.0 code found a solution that works for rows and columns, but not within the 3×3 blocks.

Version 1.0 worked… I think. It was a brute force algorithm, and solving Sudoku is not amenable to brute force because of all the possible combinations. I ran that version for hours and it only scratched the surface.

Version 2.0 was an attempt to rethink the whole approach. I thought I’d start with the cells where a row and column intersect, check the clues in the intersecting paths, and see what digits remain that would be possible to fill the blank. I hoped to find at least one blank with only one possible digit. I thought filling that in might give me another, and so on.

That code found only one cell with only one possible digit. It’s the bottom row, in the center between the 3 and 2. That cell can only be a 1. But filling it in didn’t give me another cell with only one possibility. The best was several with two.

Version 2.0 was such a kludge I started over with a fresh approach. This version identifies all blank cells and what digits were possible for them (in some cases, quite a few). Here’s a listing sorted from least number of possibilities to most:

1,7: [0,9,14   ] {6       } [12345789]
3,1: [2,12     ] {1       } [23456789]
3,5: [2,7,13   ] {8       } [12345679]
7,1: [3,15     ] {7       } [12345689]
9,5: [5,10,16  ] {1       } [23456789]
2,2: [1,12     ] {19      } [2345678]
2,7: [1,9,14   ] {16      } [2345789]
3,4: [2,6,13   ] {58      } [1234679]
3,7: [2,9,14   ] {12      } [3456789]
4,4: [6,9,18   ] {69      } [1234578]
7,5: [3,10,16  ] {16      } [2345789]
8,4: [4,9,16   ] {67      } [1234589]
9,1: [5,15     ] {79      } [1234568]
1,9: [0,11,14  ] {368     } [124579]
2,4: [1,6,13   ] {356     } [124789]
5,4: [6,10,18  ] {368     } [124579]
8,5: [4,10,16  ] {456     } [123789]
8,6: [4,11,16  ] {456     } [123789]
8,7: [4,6,17   ] {689     } [123457]
8,9: [4,8,17   ] {678     } [123459]
9,8: [5,7,17   ] {179     } [234568]
1,5: [0,7,13   ] {3678    } [12459]
1,6: [0,8,13   ] {3678    } [12459]
2,8: [1,10,14  ] {1356    } [24789]
2,9: [1,11,14  ] {1356    } [24789]
3,9: [2,11,14  ] {1458    } [23679]
5,6: [8,10,18  ] {1368    } [24579]
6,5: [7,11,18  ] {1368    } [24579]
6,6: [8,11,18  ] {1368    } [24579]
7,8: [3,7,17   ] {1367    } [24589]
7,9: [3,8,17   ] {1367    } [24589]
8,8: [4,7,17   ] {6789    } [12345]
5,5: [7,10,18  ] {12368   } [4579]

From left-to-right: The pair of numbers is the cell row and column. The first square brackets contain the indexes of path definitions that cross the cell. The numbers in the curly braces are the possible digits. The second square brackets contain the digits found in the paths that cross the cell.

Note that five cells have only one possibility. Those five cells must have those digits.

As it turns out, plugging those values in reveals new cells that have only one possible digit. This continues all the way to a solution, at least for the Tredoku puzzle I have. It’s possible it’s an easy puzzle to solve.

There’s a lot to explain, starting with how we represent a three-dimensional Tredoku puzzle. We obviously can’t treat it as a square grid indexed by row and column. We need some way to represent the puzzle shape and the relevant paths.

Figure 2. Row and column labels. Blue numbers are row and columns. Red numbers are path definition indexes.

We’ll label the cells with rows and columns according to a reasonable scheme and use a dictionary to hold them. The dictionary keys are the (row, column) tuples that label the Tredoku cells. The dictionary items are the cell contents, a digit from one to nine. Blank cells are set to zero.

Figure 2 shows the labeling scheme. Compare it with Figure 1 above. The diamond cells in the middle are the visually horizontal 3×3 grid. The lines leading through them indicate the (vertical) paths.

Note that there are six readily apparent horizontal paths, three above, three below, each with nine cells. Each row needs to have one of each digit.

Less obvious are the six vertical paths on the right that run from the top row of the puzzle to the bottom row. Note how the left three cross the horizontal grid in a different direction from the three on the right. As with the row paths, each vertical path must have one of each digit.

These 12 paths comprise the straight nine-cell paths through the puzzle. We also treat as paths each 3×3 grid of the puzzle because these grids must also have one of each digit.

We’re going to solve the puzzle by making a list of all the blank cells (the ones set to zero). For each zero we find, we check the row and column that cross it for what digits have already been used. We also check the applicable 3×3 grid for digits already in play. When we do this for the first time, we get the listing shown above. Which, as mentioned, already shows five cells that — with the clues as given — can only have one value.

The general process is to analyze the puzzle as just described and plug in a possible value. Ideally a required value, but if only choices with multiple options exist, pick one with the smallest number of options and iterate over trying each in turn. Then recurse and repeat until — hopefully — the puzzle is filled in. If we get stuck, back up to a point that had multiple options and try one of the others.

Here’s how we’ll define the puzzle structure:

The BlankPuzzle dictionary represents the shape of the puzzle as described above. It’s keyed with (row,col) tuples identifying the cell. All values are set to zero (no clues in a blank puzzle).

The  PuzzlePaths list contains the row, column, and square grid paths also described above. Each path is a list of (row,col) tuples identifying the cells of the path.

We also need some general data and helper functions:

Symbols (line #3) is a set containing the nine digits. Its use becomes apparent later. RowSum (line #4) is the sum of the nine digits (1+ … +9=45). GetRow (line #6) is a lambda function that, given a puzzle (pz) and path definition (pd) returns the puzzle values from that path.

The join_puzzle function (lines #8 to #20) merges the clues of a puzzle specification with a blank puzzle to create the populated puzzle for solving. It defaults to using BlankPuzzle.

The test_puzzle function (lines #22 to #39) scans all the puzzle paths to see if they sum to RowSum.

The print_puzzle function (lines #41 to #65) lists the puzzle to an output stream. By default, stdout, but a file stream can be provided.

We’ll define a class for the zero-cell analysis data:

Object instances have five properties. The key property holds the cell’s (row,col) label. The pos property (possibles) is a set of possible digits for this cell. The pds property (path defs) is a list of indexes to the path definitions that apply to this cell. The gots property is a list of digits found in the paths for the cell. The size property (lines #8 to #11) returns the number of possible digits.

Each cell has at least two applicable path definitions, a row or column that crosses it and the 3×3 grid the cell is in. Most cells have a row and column crossing them, so have three applicable path definitions.

The dunder len method returns the number of path definitions, the dunder iter method returns an iterator over the path definitions, and dunder getitem allows read access to a specified one.

Here’s the function that scans for blank cells and determines what digits are possibilities:

The first loop (lines #10 to #26) iterates over the path definitions. It starts by getting the row values and making a set out of them (lines #12 and #13). If that set contains a zero, it’s discarded to make got the set of already-used digits.

Then we iterate over the keys of the path definition (lines #17 to #26). For each key, we get the puzzle value, and if it’s zero, we create a cellinfo object for zcells. We append the path def index and set of gots to pds and gots, respectively.

The second loop (lines #28 to #35) iterates over the zcells values. It turns the gots list into a set, then subtracts that from Symbols to get a set of possible digits for the cell.

Then we print the zcells (lines #37 to #41) and return them.

And now, here’s the puzzle solver:

It starts by calling analyze_puzzle to get the zero cells dictionary, zcells (line #9). If there are no zero cells, the puzzle is filled in, so test to see if it’s correctly solved and return (lines #12 to #14). Note that, if we got this far, the puzzle should be solved.

Otherwise, we iterate over zcells sorted by fewest possible options (#lines 19 to #37). For each, we iterate through the possible digits, plugging it in and recursing, hopefully all the way down with required fill-ins.

Ideally, at each level, there is at least one cell with only one option. If we can follow a path of single-option fill-ins throughout, then we solve the puzzle with pure logic (rather than any brute force or retries).

All we need now is the actual puzzle and a driver routine:

The Clues1 dictionary (lines #3 to #12) defines where the clue digits go. It has the same (row,col) tuple keys used throughout to identify puzzle cells. The dictionary values are the clue digits.

The do_puzzle_solve function (lines #14 to #40) first calls the join_puzzle function to create the puzzle by combining the clues with the blank puzzle. We want to write output to a disk file, so we open one (lines #20 and #21).

Inside the try block protecting the file, we call solve_puzzle to do the heavy lifting.

Finally, on line #42, we call the driver, which calls the solver, which calls itself (and the analyzer), many times during recursion.

When run, this prints:

Path  1: [5, 2, 4, 1, 0, 0, 0, 9, 0] = 21 x
Path  2: [7, 0, 8, 0, 4, 2, 0, 0, 0] = 21 x
Path  3: [0, 6, 3, 0, 0, 9, 0, 7, 0] = 25 x
Path  4: [0, 5, 4, 8, 0, 9, 2, 0, 0] = 28 x
Path  5: [3, 2, 1, 0, 0, 0, 0, 0, 0] =  6 x
Path  6: [0, 8, 6, 3, 0, 2, 4, 0, 5] = 28 x
Path  7: [1, 0, 0, 0, 0, 7, 2, 0, 4] = 14 x
Path  8: [0, 4, 0, 5, 0, 0, 0, 0, 0] =  9 x
Path  9: [0, 2, 9, 4, 0, 0, 0, 0, 5] = 20 x
Path 10: [0, 0, 0, 4, 5, 0, 8, 0, 3] = 20 x
Path 11: [9, 0, 7, 0, 0, 0, 0, 0, 0] = 16 x
Path 12: [0, 0, 0, 0, 0, 7, 9, 0, 2] = 18 x
Path 13: [5, 2, 4, 7, 0, 8, 0, 6, 3] = 35 x
Path 14: [1, 0, 0, 0, 4, 2, 0, 0, 9] = 16 x
Path 15: [0, 9, 0, 0, 0, 0, 0, 7, 0] = 16 x
Path 16: [0, 5, 4, 3, 2, 1, 0, 8, 6] = 29 x
Path 17: [8, 0, 9, 0, 0, 0, 3, 0, 2] = 22 x
Path 18: [2, 0, 0, 0, 0, 0, 4, 0, 5] = 11 x
Path 19: [0, 5, 4, 0, 0, 0, 7, 0, 0] = 16 x

Puzzle solved!

Path  1: [5, 2, 4, 1, 3, 7, 6, 9, 8] = 45 Okay!
Path  2: [7, 9, 8, 6, 4, 2, 1, 5, 3] = 45 Okay!
Path  3: [1, 6, 3, 5, 8, 9, 2, 7, 4] = 45 Okay!
Path  4: [7, 5, 4, 8, 6, 9, 2, 1, 3] = 45 Okay!
Path  5: [3, 2, 1, 7, 4, 5, 8, 9, 6] = 45 Okay!
Path  6: [9, 8, 6, 3, 1, 2, 4, 7, 5] = 45 Okay!
Path  7: [1, 6, 5, 9, 3, 7, 2, 8, 4] = 45 Okay!
Path  8: [3, 4, 8, 5, 2, 6, 1, 9, 7] = 45 Okay!
Path  9: [7, 2, 9, 4, 8, 1, 3, 6, 5] = 45 Okay!
Path 10: [6, 1, 2, 4, 5, 9, 8, 7, 3] = 45 Okay!
Path 11: [9, 5, 7, 8, 2, 3, 6, 4, 1] = 45 Okay!
Path 12: [8, 3, 4, 1, 6, 7, 9, 5, 2] = 45 Okay!
Path 13: [5, 2, 4, 7, 9, 8, 1, 6, 3] = 45 Okay!
Path 14: [1, 3, 7, 6, 4, 2, 5, 8, 9] = 45 Okay!
Path 15: [6, 9, 8, 1, 5, 3, 2, 7, 4] = 45 Okay!
Path 16: [7, 5, 4, 3, 2, 1, 9, 8, 6] = 45 Okay!
Path 17: [8, 6, 9, 7, 4, 5, 3, 1, 2] = 45 Okay!
Path 18: [2, 1, 3, 8, 9, 6, 4, 7, 5] = 45 Okay!
Path 19: [9, 5, 4, 3, 2, 8, 7, 6, 1] = 45 Okay!

wrote: tredoku.list

Which shows the unsolved puzzle paths first and the solved puzzle paths second. The output, the tredoku.list file, has over 3,000 lines, so I won’t reproduce it here. It’s included in the ZIP file available below.

The algorithm can be repurposed for other puzzles using this shape as well as puzzles with new Tredoku shapes. It even works with Sudoku puzzles.

For a new shape, redefine BlankPuzzle and PuzzlePaths. The former is basically a list of (row,col) cell specifications, the initializing zero can be assumed. The latter is a list of lists, each inner list consisting of the (row,col) cell spec of the cells on the path. The outer list includes actual horizontal and vertical paths as well as “paths” for the 3×3 squares. In the abstract, a “path” is any collection of nine cells that must contain among them all digits 1-9.

The clues for a specific puzzle are a set of cell specifications and the digit for that cell.

For more flexibility, use a JSON file to contain a variety of puzzle shape definitions and clue sets for different puzzles. A fully working script is included in the ZIP file linked below.

Link: Zip file containing all code fragments used in this post.

∅