In the last year or so a puzzle has been appearing in 'The Guardian' (a UK newspaper). It looks like this:
and the instructions are as follows:
Lay tracks to enable the train to travel from village A to village B. The numbers indicate how many sections of rail go in each row and column. There are only straight rails and curved rails. The track cannot cross itself.
I have been doing these puzzles for a while now and was wondering (a) if there was only one solution to a given puzzle, and (b) if the given cells - there are four in this example and that's usually the case - were actually necessary to solve the puzzle, or just made it easier: and if they were necessary, how many were required?
I have now written a program (using Microsoft C#) to generate and test these puzzles. Here's a sample track:
The program randomly chooses a left-hand-side entry point, then randomly chooses any of the allowed track segments until it finds a 'way out' on the lower side (most attempts will fail, and a new sequence will be tried - the number of attempts required for a solution is recorded in the 'Attempts' box).
The surprise result is that, as far as I can see, there is a unique solution, even without any 'hint' (given) cells being defined. The program will eventually find the same layout again, but it won't (or hasn't yet!) found a different one. Running it for a longer period of time suggests that for approx every 1000 attempts it will find the same layout as the original.
Onto my questions:
- (a) is there indeed a unique solution, given only the entry and exit points and the row/column totals? (or is there a flaw in my programming/ randomisation?)
- (b) if there is a unique solution without the hint cells, is it possible to solve the puzzle other than by trial-and-error?