6
$\begingroup$

In the last year or so a puzzle has been appearing in 'The Guardian' (a UK newspaper). It looks like this:

train track sample

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:

created 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).

I then went on to see if the program could generate another layout, using the same entry and exit points, and having the same row and column totals: created track and test track

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?
Improve this question
$\endgroup$
8
  • $\begingroup$ Kind of obvious, but does your algorithm stop running after the first correct solution? $\endgroup$
    – Nautilus
    Oct 8, 2021 at 17:15
  • $\begingroup$ No, it will pause for a second (so you can view it) then carry on trying to find another. $\endgroup$
    – quilkin
    Oct 8, 2021 at 18:43
  • 1
    $\begingroup$ Just for the heads up, your first generated grid has another solution where some different squares are used or left empty: imgur.com/a/jEbRPmx $\endgroup$
    – Nautilus
    Oct 8, 2021 at 18:55
  • 1
    $\begingroup$ @quilkin A little hint: Instead of random branching, use "backtracking" - it will reliably enumerate all solutions. This should solve the issue. Nice program:) $\endgroup$
    – mafu
    Oct 11, 2021 at 18:57
  • 1
    $\begingroup$ Just so you know: these puzzles are included in Simon Tatham's Portable Puzzle Collection, available for play online, on several computer platforms, as an Android app and I'd expect there's an IPhone app as well. $\endgroup$
    – Oliphaunt
    Oct 16, 2021 at 22:26

4 Answers 4

Reset to default
8
$\begingroup$

In the puzzle you generated, there is

not a unique solution. You can mirror the 3x3 block of track that lies on rows 5-7 to get another solution:
enter image description here
In fact, you can fill that 4x3 block in the bottom right corner in several different ways.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hmmm - looks like you're correct, thanks. Then there must be something incorrect in the way my algorithm chooses tracks - I suspect it's do to with what happens at the edge cells. I'll investigate, then come back and mark your answer. Meanwhile if I leave it unanswered someone else may offer more insights! $\endgroup$
    – quilkin
    Oct 8, 2021 at 10:23
  • $\begingroup$ I have ticked your answer because you were the first to show that my algorithm must be incorrect. I have since discovered that, by adjusting when/if the random generator is re-seeded, the puzzle may find the same solution again or not. But it still has never found a different solution, and you have clearly shown that different solutions exist! $\endgroup$
    – quilkin
    Oct 9, 2021 at 7:44
3
$\begingroup$

I tried to solve the puzzle from the newspaper without using the hints, only the numbers and the village positions. It allows multiple solutions. One ambiguity is in the top left, the other is in the middle at the right edge. You need to use 2 hints to solve the puzzle. The two hints at the villages are not needed.

I could solve it up to the ambiguities with deductions only.

I think the hints are the result of the generation process. A random path is generated, a solver runs on this and random hints are added until the problem becomes unique. Maybe the entry and exit are always marked by a hint to make them more visible.

Besides, the hints add some variety to the type of deductions. And visually it looks better than an empty square. So they are nice to have.

PS: It's better with a picture. This is how far you go without hint. A dot means a track is required there.

enter image description here

Improve this answer
$\endgroup$
3
  • $\begingroup$ Very interesting - do you have any proof that 2 hints are needed, and/or that the entry and exit hints aren't needed? $\endgroup$
    – quilkin
    Oct 12, 2021 at 20:32
  • 1
    $\begingroup$ I don't want to explain the solving process step by step, but without hint the rails at A and B can be inferred logically and what is left is two ambiguous regions that can be filled in two ways. One hint is needed for each, not necessarily the ones given. So yes to your question. But you have to believe me. $\endgroup$
    – Florian F
    Oct 12, 2021 at 22:23
  • $\begingroup$ Thanks - I believe you! But now I have to work out if your method of deciding which cells are occupied is unique to the sample puzzle or if there is a generalised method. $\endgroup$
    – quilkin
    Oct 17, 2021 at 13:22
1
$\begingroup$

Just for the heads up, your first generated grid has another solution where some different squares are used or left empty: imgur.com/a/jEbRPmx

If there's a unique solution, you can take note of these:

- First of all, always extend the tracks to the middle of the next cell accordingly (obvious).

- The corner cells of the active (not guaranteed to be eliminated or filled/connected yet) part of the puzzle are important. Because they have only two adjacent cells, they must be empty if you can be sure that at least one of the adjacent cells is. Likewise, if an adjacent cell being empty creates a contradiction or lack of filled cells, the adjacent cell must be filled.

- If there is one unfilled cell left in a row or column at the edge of the unsolved part of the puzzle at some point, it must be adjacent to a filled segment (the rows/columns with the starting and ending points could be the exceptions).

- You can also try painting the grid like a checkerboard and check for both colors in rows and columns. Since the track is a continuous route, the total number of colored cells are equal or one color is seen on one more occasion than the other among all the filled cells.

Improve this answer
$\endgroup$
0
1
$\begingroup$

My answer to the Guardian puzzle:

[1]: https://i.stack.imgur.com/DpaXs.jpg

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ That's that's correct - but not the answer to the question I was asking! If you enjoyed completing it, there's a new one in The Guardian every Saturday ! $\endgroup$
    – quilkin
    Oct 9, 2021 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.