[seqfan] Re: Minimal simple loop puzzle
hv at crypt.org
hv at crypt.org
Sat Feb 26 19:37:42 CET 2022
Elijah Beregovsky <elijah.beregovsky at gmail.com> wrote:
:Dear seqfans!
:Simple loop (usually shortened to sloop) is a logic puzzle consisting of a
:square grid with some cells colored black. You have to draw a single loop
:passing through centers of all white cells. So, basically, the task is to
:find a hamiltonian cycle in a grid graph with some vertices deleted.
:(Example puzzle: https://puzz.link/p?simpleloop/8/8/201000000g010)
See also <https://www.janko.at/Raetsel/Rundreise/index.htm>.
:Question: what is a(n), the smallest possible number of shaded cells in a
:uniquely solvable n x n sloop puzzle?
Also: how many uniquely solvable n x n puzzles exist, and how many are
maximal (ie with the minimum number of shaded cells), with or without
symmetries.
:Checking all possible arrangements of shaded cells is not feasible --
[...]
Well you can rule out some cases simply, eg those that leave an isolated
edge or corner cell (eg shading [0, 1], or shading [0, 0] and [0, 2]).
My first thought beyond that is that if you can determine a subregion
that has multiple solutions for a particular pair of entry/exit points,
and the complementary region has a path starting/ending at the same pair,
then one or the other region must change. That logic can be applied
recursively to break a large grid up into multiple smaller regions.
It is sometimes valuable to start by analysing simple cases of the more
general m x n grid - probably starting with 3 x n and 4 x n here - to look
for patterns and recurrences that might tell you more about the problem.
:I wrote a Mathematica program checking 500000 randomly chosen arrangements
:of i black cells for each i of the same parity as board size n between n/2
:and 2n (no mathematical reason for such bounds, just a hunch). If an
:arrangement is balanced, then I attempt to FindHamiltonianCycle, at most 2
:of them.
Considering the 8x8 or 10x10 cases, for example, I think it would not be
out of reach to analyse all relevant cases for the 4x4 (respectively 5x5)
subgrid, then look at how those can fit together to form a complete valid
solution. Since you already know a(10) <= 10, if analysis of the 5x5 grid
with _no_ shaded cells shows that it is always ambiguous you would only
need to consider 5x5 regions with at most 7 shaded cells, but even
C(25, 10) is only a bit over 3e6.
Handling odd n is slightly less obvious: either use squares that are
slightly too small (eg 5x5 for a 11x11 grid), with some glue logic to handle
the leftover bands connecting them, or analyse each of the different shapes
needed (eg 5x5, 5x6 and 6x6 for a 11x11 grid).
I have no familiarity with Mathematica though, I don't know how suitable
a tool it is for this sort of thing.
See also the second paragraph in [1] under 'Algorithms': if there are
more efficient algorithms that just count the paths rather than listing
them, it may well be possible to do even better if all you want to know
is whether the number is less, equal or greater than 1.
Hugo
[1] https://en.wikipedia.org/wiki/Hamiltonian_path_problem
More information about the SeqFan
mailing list