Numberlink and Uniqueness

 Posts: 605
 Joined: Tue 29 Jun, 2010 11:41 am
Numberlink and Uniqueness
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"?

 Site Admin
 Posts: 2761
 Joined: Fri 18 Jun, 2010 10:45 pm
 Location: Edinburgh, Scotland
Re: Numberlink and Uniqueness
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':
"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 . . .
Re: Numberlink and Uniqueness
More simply, any puzzle with (for example) these patterns with differing givens bounding out 1 or more cells
in the corner, or
on an edge
or
in the middle
can't possibly use all the squares.
Code: Select all
.x..
y...
....
Code: Select all
...x.y...
....z....
or
Code: Select all
.x.
y.z
.w.
can't possibly use all the squares.
Re: Numberlink and Uniqueness
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.

 Posts: 605
 Joined: Tue 29 Jun, 2010 11:41 am
Re: Numberlink and Uniqueness
Thanks all!
Realised soon after posting that the pattern below could similarly be slotted in anywhere (including as a trivial 3x3 puzzle grid)
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!
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

 Posts: 1246
 Joined: Thu 24 Jun, 2010 9:27 pm
 Contact:
Re: Numberlink and Uniqueness
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.
In other words since these puzzles are solved using uniqueness, it's critical to know that that uniqueness applies without an "all square" restriction.

 Posts: 34
 Joined: Tue 10 Aug, 2010 5:49 pm
 Location: Moscow
Re: Numberlink and Uniqueness
At 24Hours championship of 2004 there was such puzzle by Laszlo Osvalt:drsteve wrote:Has anyone encountered a puzzle numberlink that does not use all the squares?
Code: Select all
........
........
.AE...A.
..D.B.C.
.E......
.C....BD
........
Re: Numberlink and Uniqueness
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 touchyfeely 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!
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 touchyfeely 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!

 Posts: 1246
 Joined: Thu 24 Jun, 2010 9:27 pm
 Contact:
Re: Numberlink and Uniqueness
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 handmade 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 NPcomplete task to prove your expected solution is unique)
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 handmade 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 NPcomplete task to prove your expected solution is unique)

 Site Admin
 Posts: 2761
 Joined: Fri 18 Jun, 2010 10:45 pm
 Location: Edinburgh, Scotland
Re: Numberlink and Uniqueness
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.
Throw it open to a programming newsgroup if you are that way inclined.

 Posts: 1246
 Joined: Thu 24 Jun, 2010 9:27 pm
 Contact:
Re: Numberlink and Uniqueness
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.
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.
Re: Numberlink and Uniqueness
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: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 handmade 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 NPcomplete task to prove your expected solution is unique)
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 nonempty 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 counterexample! 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 counterexamples where space is blocked off by clues for now, e.g.
Code: Select all
1234
5..6
7..8
9ABC
Code: Select all
.1...
.234.
.3...
.4..1
....2
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
Perhaps I'm meandering too far, but I'd be interested in clearing this up.

 Posts: 34
 Joined: Tue 10 Aug, 2010 5:49 pm
 Location: Moscow
Re: Numberlink and Uniqueness
It's not true unfortunately. A trivial example is: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 nonempty 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
Code: Select all
A.
.A
And here is more interesting example:
Code: Select all
...C
.BA.
....
.AB.
C...
Re: Numberlink and Uniqueness
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!
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!