Hexadoku solver

The Elektor magazine has been entertaining its readers for close to 10 years with a Hexadoku puzzle. The first one was published in the edition of January 2006. Compared to the more common Sudoku puzzle, the range of possible values is extended from single digit decimals (1 – 9) to single digit hexadecimals (0x0 – 0xF). The size of the puzzle is increased from 9 x 9 cells to 16 x 16 cells and consists of 4 x 4 squares of 4 x 4 cells.

hexadoku

The basic steps to complete the puzzle are the same:

  1. A certain value is invalid when already present in the same row, column or square.
  2. A certain value is the solution when it has no other possible place in the same row, column or square.
  3. A certain value is invalid when needed as solution for one of two (or more) other cells in the same row, column or square.
  4. A certain value is the solution when all other values are not valid.

The steps above are repeated until the puzzle is solved, you get stuck and give up, or you find a mistake in the entered values and start over. For some puzzles repeating the four steps above is not enough. An assumption needs to be made for the solution of a certain cell, after which repeating the four steps could get you to a solved puzzle. Other approaches to attack the Hexadoku exist without doubt, but this would be my strategy.

So, how many readers actually take the time to complete the puzzle using a pencil and eraser? Some solvers can be found on the Internet and the Elektor probably publishes the puzzle as bitmap image exactly for that reason. However, fun really starts when programming your own solver. I have written one in Python, which follows exactly the steps described above. Several parameters can be defined to describe the difficulty of the puzzle:

  • the number of empty cells in the puzzle,
  • the number of iterations of the four steps above to solve the puzzle,
  • the need to make an assumption (guess) to solve the puzzle,
  • the number of empty cells remaining when an assumption needs to be made,
  • the rate of reducing candidate solutions per iteration,

The solutions obtained with the solver are given at the end of this post.  Statistical analysis of puzzle solving with the solver shows some interesting results. A solution is typically found in less than 1 second. 🙂

hexadoku_calctimeSince the first edition of 2011 a significant increase in difficulty of the puzzles is observed. There was that one Hexadoku in 2010, where the author added an offset of 0x1 and invented the extended hexademical 0xG. Replacing all G’s by 0’s did the trick. The puzzle in the March edition of 2011 required several solutions from previous editions to be filled in first, hence the short calculation time to solve the puzzle after getting to that point. Excluded were the odd puzzles in some of the the extra-thick editions, because they did not conform to the dimensions of the Hexadoku and would cause the solver to raise exceptions.
hexadoku_iterationsThe average number of iterations required is about 11. Still interested in solving the puzzle using a pencil and eraser?

hexadoku_iterations_distThe number of initial unknowns in the puzzles ranged from 104 to 152.

hexadoku_unknowns_distThe change in difficulty since the first edition of 2011 is obvious. It takes about three times more iterations to solve the puzzles, compared to the first 5 years of Hexadoku.

hexadoku_iterations_yearThe difficulty of the puzzles, as quantified by the number of iterations needed to solve it, gets on average just a little lower throughout the year.

hexadoku_iterations_issuehexadoku_iterations_unknownsIf assumptions need to be made to solve the puzzle, the number of iterations needed to solve the puzzle is on average higher. That makes sense.

hexadoku_iterations_guessedThe most difficult puzzle to date was published in the March edition of this year: 152 unknowns at the start of the puzzle and assumptions had to be made to solve it.

hexadoku_desirabilityNote that making assumptions to solve the puzzle only became necessary after a few years, with the change in difficulty in 2011. Did anyone had to make adjustments to his solver for this?

year month solution guessed
2006 01    EA639    N
2006 02    0928F    N
2006 03    3B479    N
2006 04    CDA48    N
2006 05    02675    N
2006 06    1A6DC    N
2006 09    0EBAD    N
2006 10    754C1    N
2006 11    1AC70    N
2006 12    87E46    N
2007 01    038FA    N
2007 02    9BC24    N
2007 03    CA9F0    N
2007 04    DF908    N
2007 05    B789E    N
2007 06    1B456    N
2007 09    FCEB7    N
2007 10    36784    N
2007 11    41EBA    N
2007 12    97C65    N
2008 01    D148B    N
2008 02    90467    N
2008 03    C2563    N
2008 04    FA63E    N
2008 05    36815    N
2008 06    0EA75    N
2008 09    7A0FE    N
2008 10    AB749    N
2008 11    FC2B6    N
2008 12    E5071    N
2009 01    4395C    N
2009 02    3097D    N
2009 03    813D2    N
2009 04    A2543    N
2009 05    857C9    N
2009 06    579BD    N
2009 09    10965    N
2009 10    DA2BF    N
2009 11    A5F32    N
2009 12    F1482    N
2010 01    26FB4    N
2010 02    95CD4    Y (This puzzle featured G's instead of 0's.)
2010 03    51E7A    N
2010 04    DFB12    N
2010 05    C81BA    N
2010 06    6B310    N
2010 09    3AE58    N
2010 10    3F8B5    N
2010 11    3F642    N
2010 12    381F0    N
2011 01    B278F    Y
2011 02    9084B    Y
2011 03    9302F    N (This puzzle required entering solutions of previous puzzles.)
2011 04    B9A65    Y
2011 05    CD604    N
2011 06    B18AD    N
2011 09    4D0F6    N
2011 10    D0837    N
2011 11    40F58    N
2011 12    35C24    N
2012 01    43ADE    Y
2012 02    BEF8D    Y
2012 03    862DF    Y
2012 04    78BE0    N
2012 05    4C03E    N
2012 06    7924A    N
2012 09    3F126    N
2012 10    75E2B    N
2012 11    BD18A    N
2012 12    621BA    N
2013 01    02518    Y
2013 03    48C57    Y
2013 04    934CB    Y
2013 05    3D1AE    Y
2013 06    F9407    N
2013 07    3B4CD    N
2013 09    569E8    N
2013 10    FCDE8    N
2013 11    E75F4    Y
2013 12    AC023    Y
2014 01    1F734    N
2014 03    0E4D6    N
2014 04    A0263    N
2014 05    18047    Y
2014 06    F6B04    Y
2014 07    CE234    Y
2014 09    E80F4    Y
2014 10    C03EF    Y
2014 11    63D95    Y
2014 12    D7085    N
2015 01    3146A    Y
2015 03    16A8E    Y
2015 04    DFBA9    Y
2015 05    8205E    Y
2015 06    458EF    N
2015 07    *****    N
2015 09    ?????    ?
2015 10    ?????    ?
2015 11    ?????    ?
2015 12    ?????    ?