Numberlink and Uniqueness

Discuss all puzzle-related subject here
Post Reply
nickdeller
Posts: 600
Joined: Tue 29 Jun, 2010 11:41 am

Numberlink and Uniqueness

Post by nickdeller » Mon 09 Aug, 2010 12:34 pm

I can't find an instant answer to this, so I wonder if anybody knows - is it demonstrably true or untrue to say that "For a Numberlink puzzle to have a unique solution, it MUST use all the cells in the grid"?

PuzzleScot
Site Admin
Posts: 2739
Joined: Fri 18 Jun, 2010 10:45 pm
Location: Edinburgh, Scotland

Re: Numberlink and Uniqueness

Post by PuzzleScot » Mon 09 Aug, 2010 1:08 pm

Someone wrote on wiki:

"It is considered that a problem is well designed if and only if it has a unique solution and all the cells in the grid are filled with line, although some Number Link designers do not necessarily stipulate this."

I think that requiring all the cells to be used adds a constraint that helps solving, but parity alone can prove it's not a necessary condition.

eg, the following has a unique solution, but with 2 empty cells, it's probably considered 'poor':

Code: Select all

3 . . . .
. 1 2 4 .
. 3 . . .
. 2 . 4 .
. 1 . . .

detuned
Posts: 1869
Joined: Mon 21 Jun, 2010 2:25 pm
Location: London, UK
Contact:

Re: Numberlink and Uniqueness

Post by detuned » Mon 09 Aug, 2010 1:33 pm

More simply, any puzzle with (for example) these patterns with differing givens bounding out 1 or more cells

Code: Select all

.x..
y...
....
in the corner, or

Code: Select all

...x.y...
....z....
on an edge

or

Code: Select all

.x.
y.z
.w.
in the middle

can't possibly use all the squares.

drsteve
Posts: 726
Joined: Sun 27 Jun, 2010 7:23 am

Re: Numberlink and Uniqueness

Post by drsteve » Mon 09 Aug, 2010 2:59 pm

Has anyone encountered a puzzle numberlink that does not use all the squares? I always assume this will be the case and haven't been caught out yet, but it would seem to be an obvious way to trip up solvers.

nickdeller
Posts: 600
Joined: Tue 29 Jun, 2010 11:41 am

Re: Numberlink and Uniqueness

Post by nickdeller » Mon 09 Aug, 2010 4:01 pm

Thanks all!

Realised soon after posting that the pattern below could similarly be slotted in anywhere (including as a trivial 3x3 puzzle grid)

Code: Select all

xxy
w.y
wzz
I don't recall ever seeing an example in the wild with an unused square, I have to say, but it wouldn't surprise me if there's been one or two - some of the WPC organisers over the years have been very keen to catch people out on assumptions they shouldn't be making!

GarethMoore
Posts: 1209
Joined: Thu 24 Jun, 2010 9:27 pm
Contact:

Re: Numberlink and Uniqueness

Post by GarethMoore » Mon 09 Aug, 2010 10:37 pm

One thing to catch the unwary is you can't simply state "all squares are used" as part of the rules, because it's critical to solving them at a reasonable difficulty level that you don't need this - otherwise lines bending back on themselves would be fine! So our rules are wrong. I've written more about this on the web app thread.

In other words since these puzzles are solved using uniqueness, it's critical to know that that uniqueness applies without an "all square" restriction.

AndreyBogdanov
Posts: 33
Joined: Tue 10 Aug, 2010 5:49 pm
Location: Moscow

Re: Numberlink and Uniqueness

Post by AndreyBogdanov » Tue 10 Aug, 2010 6:29 pm

drsteve wrote:Has anyone encountered a puzzle numberlink that does not use all the squares?
At 24-Hours championship of 2004 there was such puzzle by Laszlo Osvalt:

Code: Select all

........
........
.AE...A.
..D.B.C.
.E......
.C....BD
........

detuned
Posts: 1869
Joined: Mon 21 Jun, 2010 2:25 pm
Location: London, UK
Contact:

Re: Numberlink and Uniqueness

Post by detuned » Wed 22 Sep, 2010 9:50 pm

Perhaps I'm flogging a dead horse here, but recently I've tried making numberlink.

I think we're all agreed that using uniqueness is generally the best thing to do whilst solving, but you can't do this when you make them. Does anyone have any thoughts here? I recall having a brief chat with Thomas Snyder in Philadelphia about his approach - splitting up paths into two or more until uniqueness is "forced". I guess that will eventually work, but it's still touchy-feely at heart.

The puzzle I've got here (won't post for now - its potentially part of a project ;) ) whilst I'm fairly certain is unique, this is only based on a feeling - which is a bit annoying!

GarethMoore
Posts: 1209
Joined: Thu 24 Jun, 2010 9:27 pm
Contact:

Re: Numberlink and Uniqueness

Post by GarethMoore » Thu 23 Sep, 2010 10:57 am

I've no idea how Nikoli prove theirs have unique solutions - I'd love to know!

One other way to make them is to start with a loop that visits every square, and break it up into segments - some Nikoli ones work like that. Possibly that helps in some way, but I'm not sure.

I expect there is some sort of graph theory routing algorithm that can help solve them - if you can untangle possible layouts and then try to fit them into the grid then I expect there is a lot of simplication that can be done there, computationally. A recursive search, even with all the optimisations I can think of, is just far too slow. I hand-made a 10x10 puzzle with 6 lines and my solver didn't finish checking it within the hour or so I ran it for (in C# on a fast computer). If that search knew that certain connections must pass inside or outside other ones then it could be pruned down to perhaps a more manageable size, but even so a deep recursive algorithm is going to be hopeless with a 36x20 one or whatever they go up to! (Since, of course, it is an NP-complete task to prove your expected solution is unique)

PuzzleScot
Site Admin
Posts: 2739
Joined: Fri 18 Jun, 2010 10:45 pm
Location: Edinburgh, Scotland

Re: Numberlink and Uniqueness

Post by PuzzleScot » Thu 23 Sep, 2010 11:49 am

I know Dave Green at Conceptis uses a program to verify ALL their puzzles have a unique solution, which is quite a feat!
Throw it open to a programming newsgroup if you are that way inclined.

GarethMoore
Posts: 1209
Joined: Thu 24 Jun, 2010 9:27 pm
Contact:

Re: Numberlink and Uniqueness

Post by GarethMoore » Thu 23 Sep, 2010 11:53 am

Conceptis make Numberlink? I've never seen one and there isn't one on their website that I can spot. Are they in certain books or magazines?

Only reference I can see is at http://www.conceptispuzzles.com/index.a ... fo/news/32 but that's from 2007 and they don't seem to have appeared since, and the link is dead. Maybe they were relatively rubbish. :)

It's actually perfectly possible to make numberlink on a computer, so long as your puzzles are suitably constrained. My point was that you can't guarantee in the general case that any puzzle can be proven to be unique in reasonable time - if you're happy to rapidly abandon "tough" puzzles and try a new random start point you'll soon find valid numberlink puzzles. That way you end up with most numberlink puzzles I've ever seen outside those of Nikoli.

detuned
Posts: 1869
Joined: Mon 21 Jun, 2010 2:25 pm
Location: London, UK
Contact:

Re: Numberlink and Uniqueness

Post by detuned » Thu 23 Sep, 2010 4:26 pm

GarethMoore wrote:I've no idea how Nikoli prove theirs have unique solutions - I'd love to know!

One other way to make them is to start with a loop that visits every square, and break it up into segments - some Nikoli ones work like that. Possibly that helps in some way, but I'm not sure.

I expect there is some sort of graph theory routing algorithm that can help solve them - if you can untangle possible layouts and then try to fit them into the grid then I expect there is a lot of simplication that can be done there, computationally. A recursive search, even with all the optimisations I can think of, is just far too slow. I hand-made a 10x10 puzzle with 6 lines and my solver didn't finish checking it within the hour or so I ran it for (in C# on a fast computer). If that search knew that certain connections must pass inside or outside other ones then it could be pruned down to perhaps a more manageable size, but even so a deep recursive algorithm is going to be hopeless with a 36x20 one or whatever they go up to! (Since, of course, it is an NP-complete task to prove your expected solution is unique)
The way I've done mine is as I approach making many other puzzles - pick a pattern, and then play around a bit. Now I'm confident that the pattern in itself is fairly constrained (It has a pair of 2x2 blocks of clues, near opposite corners), but I don't know. The best I have for now is ensuring that one path does not go through a 2x2 block of squares. Formally:

Assume we are given a numberlink grid with some clues. Let S be the set of possible solutions (which is finite, and also possibly empty. We'll ignore the empty case, and we'll be particularly interested when the size of this set is 1). If we suppose one element of S has an arrangement such that a single strand occupies a 2x2 box, then #S >1. You can convince yourself of this via some case analysis.

What would be more interesting is turning this into a sufficient (rather than necessary condition) for #S=1. That is to say, if #S>1, then there exists an element of S such that some strand occupies a 2X2 box. Equivalently, (if S is non-empty and)if there are no elements of S such that a strand occupies a 2x2 box, then #S=1.

I have no idea whether such a statement would be true or not - I would certainly be very interested in seeing a counter-example! I suppose as a tool it is not much use - in order to prove that #S=1 you would already, a priori, know the value of #S.

I suppose one interesting result (if you'll meander with me through my train of thought), based on the contrapositive logic to this 2x2 rules is that if you have a numberlink arrangement that omits a 2x2 square somewhere, then that arrangement can't possibly be unique[*]. This again requires a bit of case analysis - but the guiding principle is one of the strands bordering the 2x2 square could dip into it to make an alternative longer path.

[*] we'll ignore counter-examples where space is blocked off by clues for now, e.g.

Code: Select all

1234
5..6
7..8
9ABC
This severely limits what the solution to a uniquely solvable numberlink puzzle that doesn't use all the squares could look like. We've previously discussed the case where you artificially block off squares - but are these in fact the only examples? This would give another route to attack uniqueness. I can't recall a nikoli puzzle that divided up the grid into two components...although neither does this:

Code: Select all

.1...
.234.
.3...
.4..1
....2
Still, there is a principle of "blocking off" going on here with the 2 strand. It's not easy to formally tie that down. At the moment, I'm sort of viewing it like this. Imagine a solution to a numberlink. Basically you can classify its strands as separating and non-separating. A strand is separating if it divides the grid into two(or more) components of white space, where white space does not include clues. In my silly example, 1 is non-separating; 2 is separating (2 components); 3 is non separating; and 4 is separating (3 components).

Now we have to analyse the components of white space, and more specifically their boundaries. There are three possible types of boundary component.
  • The strand;
  • the edge of the grid;
  • clues
If all the white space is to be used up, then you need at least 2 clues (of the same type) on the boundary of each component, with the clues adjacent to the white space via an edge (as opposed to touching only at a corner point. Perhaps this ambiguity can be cleared up in the definition anyway).

Perhaps I'm meandering too far, but I'd be interested in clearing this up.

AndreyBogdanov
Posts: 33
Joined: Tue 10 Aug, 2010 5:49 pm
Location: Moscow

Re: Numberlink and Uniqueness

Post by AndreyBogdanov » Thu 23 Sep, 2010 6:04 pm

detuned wrote:What would be more interesting is turning this into a sufficient (rather than necessary condition) for #S=1. That is to say, if #S>1, then there exists an element of S such that some strand occupies a 2X2 box. Equivalently, (if S is non-empty and)if there are no elements of S such that a strand occupies a 2x2 box, then #S=1.

I have no idea whether such a statement would be true or not
It's not true unfortunately. A trivial example is:

Code: Select all

A.
.A
It has exactly two solutions but no of them has occupied 2x2 box.

And here is more interesting example:

Code: Select all

...C
.BA.
....
.AB.
C...
It has two solutions again, both without empty squares and both without 2x2 boxes.

detuned
Posts: 1869
Joined: Mon 21 Jun, 2010 2:25 pm
Location: London, UK
Contact:

Re: Numberlink and Uniqueness

Post by detuned » Thu 23 Sep, 2010 8:58 pm

Andrey, that second example is indeed interesting!

I have been trying to think a little more about this, given that's unlikely nikoli use a computer to verify their larger puzzles (or even their smaller puzzlers - it just seems like an inelegant option.

Now that example is interesting because not only are the position of the clues symmetric, but so are the clues themselves. I wonder whether you'd have (at least!?!) two solutions for every such entirely symmetric arrangement?

I am beginning to think that it's possible to make a statement about uniqueness given the existence of one solution that fills up the grid in the "right" way. What the right way is needs to be clarified, but this example clearly shows that puzzles with total symmetry must be ruled out!

Post Reply