Google’s Think Quarterly carries a Futoshiki puzzle, titled “Long Flight Ahead”.
It’s a 9x9 rather than the traditional 5x5 and, thanks to some recent code improvements, my Futoshiki solver can handle it and save you plenty of time for wondering what the deal is with airline snacks and snooping on your flight neighbours.
Here’s the ASCII version, but I guess you can’t paste it in to the ‘Edit...’ window when it’s an applet because of security. Run FutoshikiPanelSample instead, or click between the cells to define these rules:
> > > < >
^ ^
> > > >
v ^ ^ ^
> <
v ^ v ^
<
v v ^
> > >
v ^ v
< 3
v v ^
>
^ v ^ ^
> > > > < <
^ ^
< < < > > >
Interestingly, someone sent me another copy of that puzzle with a mistake making it unsolvable. Thanks to some other improvements, it’ll now tell you that a lot earlier.
My original implementation was, very consciously, tuned only to the point that it completed a backtracking search of 5x5 puzzles pretty much straight away. As I increased the size, I looked at how many possible solutions there were, assuming no rules. Starting with 1x1: 1, 2, 12, 576, 161280, 812851200... where’s this headed? A quick trip to the On-Line Encyclopedia of Integer Sequences™ tells us that the next items are bigger still, and we’re up to 5524751496156892842531225600 for a 9x9 Latin square.
Long story short, it’s a bit cleverer now: it keeps track of which numbers are still possible, uses the rules to eliminate even more and shares references to collections rather than making repeated copies. One of the most effective changes was to always try to fill the cell with the fewest possibilities first of all. In one case, making sure to eliminate possibilities based on repeatedly applying the rules reduced the search space by a factor of a trillion.
Reading through Peter Norvig’s Sudoku solver, and the Hacker News comments makes me realise how much faster this could get if I really wanted to prove a point. But, fast enough is fast enough for now.
)