pascal.germroth.name

The austrian newspaper Der Standard offers another kind of sudoku-like logic puzzle, called Comparsion Sudoku. The usual Sudoku-rules apply, with an added twist: no initial numbers are given, but the lines seperating the fields indicate, which field’s number will be higher.

I tried to solve this by hand, and it’s an awful lot of work, way more than usual Sudoku, thus a script had to do my work:

The algorithm is incredibly naïve, but effective enough to be implemented in JavaScript. You also might want to look into the code, it is not even remotely self-explanatory, in fact, if it hadn’t just worked on my first try, I’d be completely lost.

Check it out!

First step is to determine the minimum difference between every field in a 3×3-part. To do this, we build a directed graph, where every orange edge equals a greater than sign in the original puzzle. The minimum difference between the values of two nodes connected by an orange edge is 1. Then we look for the nodes that are indirectly (via one other node) connected to another node via an orange-1-edge. These are connected with a yellow-2-edge, and so on, until we might be able to connect two nodes with a purple-8-edge. This enables us to determine the lowest and highest possible value for that node: the upper-left node that is pointed to by the 8-edge may only have a value of 1, because the middle node’s value has to be +8, and its highest possible value is 9 as defined by the game rules. And so on. For less obvious setups, we won’t end up with a single solution for a part, but a list of possible values for each node (the demo will only display the first and last value of that list, the color tint gives a hint at the length.)

Second step is to apply the usual Sudoku-exclusion rules: if the first step gave us a single solution for a node, this value can’t show up in the same row, column and part as that node again: we remove it from the list of possible values for the nodes concerned. This might present us with more single solutions, more removals and so on. Once we’re done, there should be a unique solution, or we’ll repeat the first step which should reduce the list of possible values further.