Solving Loki (11.9) with Oddagons

In this post I'll be solving the puzzle Loki, published by mith in 2022. Here's a link to the original thread.

Loki broke many records and was dubbed the "hardest puzzle in the world". It is one of the few puzzles with SE 11.9, if I recall correctly the 10th to be found. 11.9 is conjectured to be the maximum possible difficulty in a Sudoku puzzle. It was also the first ever puzzle proven to be in T&E(3), breaking a decades-old conjecture that 2 was the maximum. Its discovery opened the floodgates and since then the users on the Sudoku Players' Forum have been largely dedicated to exploring its offshoots and generating hundreds of thousands of extremely difficult puzzles utilising 3-digit chromatic impossible patterns. But can a lowly human solve it? Let's see.

 

 Puzzle string: 57....9..........8.1.........168..4......28.9..2.9416.....2.....6.9.82.4...41.6.. - Sudoku.Coach

 

 After singles:

  

 

Let's take a minute to discuss the pattern known as Trivalue Oddagon (Tridagon). If you look closely at the puzzle you will notice the digits {357} in boxes 5689 form an interesting pattern. I've rotated the puzzle 180 degrees and re-assigned the digits to be {123} for ease of demonstration. What's so interesting about this pattern? Take your time.

 

 

 

...

 

 

 

...

 

 

 

...

 

The surprising fact about this pattern is it's impossible to solve! You can easily verify this yourself by attempting to fill in digits. There's no assignment of 1, 2 and 3 that can fill all these cells without violating the rules of Sudoku. I'll prove it without trial and error by paraphrasing from shye's wonderful proof.

 

First you need to notice the direction of cells within each box of the pattern. Going from left to right, each cell in box 1 is 1 row lower than the last so we can say it's pointing down. The same applies for boxes 2 and 4. The cells in box 5 are pointing up as the cells go up from left to right. For this pattern to be impossible, 3 of the boxes have to be pointing one direction and 1 box has to be pointing the opposite direction.

 

Now each of these boxes must contain the triple {123} in some unknown order. These orders, when read from left to right, can be either ascending (123, 231, 312) or descending (321, 213, 132). If two boxes are horizontally adjacent and pointing the same direction, then their triples will also point the same direction. I'll show an example. We'll assume box 1's triple is in ascending order, let's say 123:

Box 2 can now only be occupied by 231 or 312, which are ascending. 

Similarly, two horizontally adjacent boxes with opposite pointing directions will have their triples pointing in opposite directions.

 

 

Box 4 is occupied by the ascending triple 123. Box 5 can now only be occupied by the triples 132 and 213, which are descending.

 

Finally, because we're reading from left to right, any two vertically adjacent boxes will always have their triples pointing the same direction. 

 

  

(Reading left to right, the possible combinations in both these lower boxes are 231 and 312, which are ascending)

Now with all these rules in place let's follow a loop around the boxes.

Box 1 is either ascending or descending.

Box 2 will point the same direction as box 1

Box 4 will point the same direction as box 1 

Box 5 will point the same direction as box 2, hence will point the same direction as box 1

Box 5 will point the opposite direction to box 4, hence will point the opposite direction to box 1

 

Box 5 has to point in both directions at once, which is impossible, so the pattern is impossible to solve.

 

Now that we know this we can get back to Loki. 

 

 

If 1 were removed from r8c8 we would have the impossible Tridagon pattern. Therefore, r8c8 is 1.

 

After singles we find ourselves in this state.

 

 

You may assume that since the Tridagon pattern has been broken we no longer have any use for it, but that's wrong - there are still relationships between the Tridagon digits we can take advantage of. It's time to introduce the concept of Remote Triples.

 

Within the Tridagon cells we can identify two loops along row/column peers.

 

 

 

The purple cells form a square and the blue cells form a large 8-cell loop. What we'll prove now is that if one purple cell is solved with a non-Tridagon digit, then all the Tridagon digits must be present exactly once in the purple square.

 

We're focusing on the three unsolved purple cells r5c5, r5c8 and r8c5 here. We'll call these the square cells. These must be occupied by 3 different digits. It's trivial to prove that they can't be occupied by 1 digit, because the cells see each other, but not so easy to prove they can't be occupied by 2 digits. 

 

Let's start by throwing away the digits and treating this as a colouring problem. We have 11 cells we wish to colour in with 3 different colours, with the constraint that no colour can be in the same row/column/box as another cell with that same colour. The only way to colour the square cells with 2 colours without violating the constraints is like this:

 

 

The top-right and bottom-left boxes now have two cells which must be filled in with red and a third colour (let's say green). Wherever you put green in the top-right box, it will have to be in the opposite location in the bottom-left box, and vice versa. 

 

 

 

This has the effect of eliminating all possible positions for green in the bottom-right box. But wait: if the top-right and bottom-left boxes contain blue and green already, the final cells in each must be coloured red. This also eliminates all the possible positions for red in the bottom-right box. So, since bottom-right has no spaces for green or red, both the cells have to be coloured in blue, which would violate the constraint that cells with the same colour cannot be contained within the same region. Therefore, this pattern is impossible to colour with 3 colours, therefore the square cells cannot contain only 2 colours. Readers who are paying attention may notice this proof is equivalent to the triplet direction argument we used to prove the Tridagon is impossible earlier.

 

Now replace "colours" with digits and you're back to Sudoku. Since the square cells can't contain 1 digit, and they can't contain 2 digits, they must contain all 3 of the digits {357}. Since there are 3 cells that must contain 3 digits, each one must be present exactly once, effectively making it a big disconnected Naked Triple.

 

How does this apply to the solve? Well, one of the square cells has to be a 7, so we can say the 7s are strongly linked and construct a Grouped AIC:

 

 

 

(7)r8c5 =RT= r5c58 - r5c3 = (7)r789c3 => r8c1<>7

 

After singles and a hidden pair we find ourselves in this state. 

 

Once again we're going to use an Oddagon, this time with two candidates instead of three.

 

 

If 2 were removed from r2c4, all these cells would contain only the candidates {57}. They see each other in sequence, forming a cycle of 5 cells. Let's abstract this to a colouring problem again.

 

 

 

Our goal is to colour this graph with 2 colours, with the constraint that any two linked nodes cannot contain the same colour. Starting anywhere, work your way around the graph, noting that the colours have to alternate as you do. If you colour a node in red, the node 2 steps away has to be red, as do the nodes 4, 6, 8, etc. away - every even number of steps.

 

 

Since the total size of the chain is 5, after 4 steps you'll arrive at another node that has to be red, but since 5 - 4 = 1, this is only 1 step away from your starting position and colouring it in red would be a violation of the constraint. So, it's impossible. More generally if the length of the chain is odd it will have length 2k+1, and after 2k steps you will have to colour the node in red, but since (2k+1) - 2k = 1, this is only 1 step away from the starting position. So, in general, we can say that any odd-length chain with this Sudoku constraint cannot be coloured with 2 colours.

 

By the way, "Oddagon" is short for "Odd Polygon". 

 

The same applies to our Bivalue Oddagon in Loki. Colouring a graph node with red or blue is analogous to placing 5 or 7 in a cell. Connected graph nodes (cells connected by common regions) cannot contain the same colour (digit). So, since the graph colouring puzzle is impossible to solve, so is our Sudoku pattern.

 

Just like in the 1st step of the puzzle, we reason that if r4c2 wasn't 2 we would have a Bivalue Oddagon, making the puzzle unsolvable. Therefore r4c2 is 2.

 

After this the puzzle is solved with singles.

 

 

Alright, that was difficult, a lot of graphing and proofs involved... or was it? I already knew what a Tridagon and an Oddagon were when I first solved Loki. You don't need to think through all of this every time you apply the rules, simply recognising the pattern is enough, and it's a very obvious pattern. This was a 3-step solve, entirely utilising Impossible Pattern Guardians, two of which were as simple as placing the one Guardian in its cell. The only chain required was effectively a Finned X-Wing. With all that said I'd call it a medium difficulty puzzle if you know what a Tridagon is, near-impossible if you try to solve it with Forcing Chains, like SudokuExplainer... it's ironic that the groundbreaking puzzle that tops all these difficulty metrics is so easily defeated.

There are other Tridagon puzzles out there with multiple Guardians which form complex chains, unfortunately none of them have been 11.9 SE yet. Still I doubt they would be as hard as the other notable 11.9s like Champagne Dry, Golden Nugget, Imam Bayildi and Kolk, which are far beyond my abilities to solve.