Another Numberlink, this time monster sized!
I originally used pzprrt to attempt to prove uniqueness as always, but after 4+ hours of running it had yet to find a second solution. (My original attempt was non-unique, and pzprrt took 2 hours to find a second solution.) After posting the puzzle on PuzzleSquareJP anyway, someone linked me to this program. It's an incredible solver, somehow claiming uniqueness in only an hour! Given how old the program is I'm surprised it's not more well-known outside Japan. Maybe that's because nobody in the west constructs Numberlink puzzles at the rate Nikoli does.
Pzprrt is probably more convenient in most cases because its puzz.link implementation makes up for the time it would take to input the solution into the above external program. But it's nice to know that constructors have been using programs for 15 years to verify uniqueness; it makes the constant output from Nikoli make more sense.
I'm curious about the original puzzle with two solutions (or do you know if it had more than 2?)... were the two solutions closely related? (for some hand-wavy definition of "closely related" that seems vaguely intuitive to you)
ReplyDeleteWould it also be possible to post the solution grids?
Sorry for the late response! For some reason, Firefox wasn't allowing me to comment because of some weird login issues.
ReplyDeleteI don't know if it had more than 2, but I purposely set pzprrt to stop as soon as it found a second solution (this way I hoped the computation would be as fast as possible).
While I don't have the solution grids on hand, I can explain where the problem laid. In the original puzzle, there were two 21 clues that were somewhat close to each other. My original solution had the path between these clues travel up and around the grid. It turned out there were solution(s) where the 21s connected directly. Granted, the topology constraints were still subtle enough that it was not *trivial* to connect them directly, but it was possible.
I fully sympathise - there's something going wrong with blogspot.com and blogger.com cookies these days so that if your browser is limiting 3rd party cookie use then it stuffs up the comment form.
ReplyDeleteAnyhow - I've been thinking about numberlink for years, and I'm convinced that there are classes of "deadly" patterns that if you managed to define in enough generality would be enough to cover all the different possibilities numberlink could possibly be non-unique. If that were true, checking uniqueness would then become much easier - you just scan a finished grid and make sure there aren't any of these patterns.
An easy one is where a link takes a detour through 2x2 set of cells instead of just going 1x2 or 2x1.
A harder one is where you an alternating pattern of 2 links like this anywhere in the grid lining up vertically (or else rotated 90 degrees) but perhaps spread over many rows:
<<1
...
2>>
...
<<1
...
2>>
So I guess the point is that I'm trying to get a feel for different puzzles where non-uniqueness comes up to get a sense of what might be a sufficient set of general rules. In some ways the idea is similar to the Reidermeister moves for knot diagrams, where 3 moves are sufficient - an interesting analogy because even if you have the moves trying to prove they are sufficient is not easy.