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.
The basic steps to complete the puzzle are the same:
- A certain value is invalid when already present in the same row, column or square.
- A certain value is the solution when it has no other possible place in the same row, column or square.
- A certain value is invalid when needed as solution for one of two (or more) other cells in the same row, column or square.
- 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. 🙂
Since 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.
The average number of iterations required is about 11. Still interested in solving the puzzle using a pencil and eraser?
The number of initial unknowns in the puzzles ranged from 104 to 152.
The 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.
The 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.
If 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.
The 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.
Note 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 ????? ?