Conquering the Behemoth - The Ultra-Difficult Board of Size 16

While I was still developing this game, I recognized that at the highest game size and difficulty lays a monstrosity. I call the game of Hexakai on a board of size 16 at ultra-difficulty level the behemoth. I've known of its existence for months, but it wasn't until last week that I set out to battle it.

While I was writing the book, I played numerous Hexakai boards of varying sizes and difficulties to build up an intuitive feeling of how the perceived difficulty increases as both board size and rated-difficulty increase. I learned that it increases much more rapidly than linearly. At the time, I could expect to solve a board of size 10 at ultra-difficult in twenty minutes to an hour, averaging out on the lower end of the range, but when I first tackled an ultra-difficult at size 13, I was shocked at the monstrous increase in difficulty. It took more than seven hours for me to complete that board. Even the difference between boards of size 12 and 13 was much higher than the difference between 11 and 12 at that same difficulty. It was so difficult that I decided to only include one such puzzle in the book instead of two. It was at that time I labeled the board of size 16 at ultra-difficult "the behemoth" and resolved to conquer it.

One week ago, I decided it was time to make the attempt. I generated a behemoth board using the "standard" generator algorithm, as I wanted this to be a classic game of Hexakai, a game in its original form. I've linked the board here if you want to give it a shot for yourself. If you do, don't refer to my image above for hints, as some of those values are wrong.

I began with my usual strategies of favoring diagonals with the fewest cells missing, focusing on a single value throughout the board with triangular elimination, and other strategies. With this, I did make some headway, but these strategies quickly proved to be insufficient. I started making tentative assignments, and for the first time, experimented with nested tentative assignments, but this strategy was mathematically untenable, as each additional layer exponentially decreased the probability that I was on the correct path. I pivoted my approach to make more use of pencil markings and study the relationships between those marked values, i.e., the possible values each cell can have, and created a new strategy. This strategy showed me that, after seven hours of gameplay, I'd already made an irrevocable mistake, one that would be hard to identify. I decided to reset the board at that point.

After taking a break for a few days, I started again. This time, I meticulously penciled in all potential cell values for every empty cell. Most cells had at least five possible values, some upwards of eight. From there, I started again with my old strategies to make some minor headway, then I switched to the new strategy I created in the previous attempt. From there, I made significantly more progress, but I still reached an impasse. After trying a few non-nested tentative assignments, I realized that I should be using the tentative assignments to disprove possibilities, not just to find definitive assignments. Before, I was only using it on cells with two values remaining, or on occasion, diagonals where a certain value could only exist in one or two cells. Sometimes I'd reach a contradiction and swap out the selected value, but the expectation was that I would either certainly find a contradiction or find the solution to the entire board. With this paradigm shift, I began ruling out single possibilities in single cells, not always making assignments. Over time, I was able to rule out enough possibilities in key cells to proceed with making value assignments, and after numerous repetitions of these new strategies, I was able to reach a point of critical mass. Enough information was available to enable me to find all remaining values using the simple, standard strategies.

That was a good feeling. As I filled in the remaining values, I kept in mind the possibility that I could still reach a contradiction, in which case I'd need to backtrack to my last tentative assignment and remove its current assignment as a possibility, but my intuition told me this would not be needed. Even if it were, I'd presumably come right back to that point of critical mass. Eventually, all of the cells were in, and I'd reached the moment of truth. Would clicking the submit button show me a board of green, or a board of red?

It was a board of green! The animation and board completion sound fired, and I'd officially conquered the behemoth. According to the app, it took me roughly 55 hours, including time spent away from the game. However, this doesn't account for the first attempt, as everything started from scratch once I hit "reset" after that attempt.

I feel that I can now say that I've mastered this game of mine. However, there are still harder boards I can generate. I may come back in some time and generate another behemoth using the one of the advanced generators. I know that hollow center games are more difficult to solve than standard games, and I'm sure some of the other generators are more difficult still. Perhaps in a few months or so, I'll revisit this. For now, I'll conclude by saying that this playthrough was immensely difficult yet highly enjoyable, and if you love complex, challenging puzzles and enjoy this game, I'd recommend that you try to take on the behemoth for yourself here.

In the meantime, I'm going to publish a post in the near future that compiles all of the strategies I've developed while playing through games of various sizes and difficulties.