Numerichain Puzzle
Bob Harris
In the puzzle below, the numbers 1 through 99 are to go into the 99 squares.
The numbers should form a chain-- 1 is next to 2, 2 next to 3, and so on
(diagonals don't count).
The only other information you are given is the numbers that surround the
eight lettered points. For example, the four squares touching H should
contain 84, 89, 92, and 93. The tricky part is that you don't know what
order they should go in.
Can this puzzle be solved given no more information than that?
If you want to try to solve it online, point your java-enabled web browser
at
http://nitlion.home.mindspring.com/numerichain/2003aug1.html
Numerichain Puzzle, August/1/2003
---------------------------------
(view with a monospace font)
+ - - + - - + - - + - - + - - + - - + - - + - - + - - + - - + - - +
: : : : : : : : : : : :
: : : : : : : : : : : :
+ - - + - - + - - + - - + - - + - - + - -(H)- - + - - + - - + - - +
: : : : : : : : : : : :
: : : : : : : : : : : :
+ - - + - - + - - + - -(C)- - + - - + - - + - - + - - + - -(F)- - +
: : : : : : : : : : : :
: : : : : : : : : : : :
+ - -(A)- - + - - + - - + - - + - - + - - + - - + - - + - - + - - +
: : : : : : : : : : : :
: : : : : : : : : : : :
+ - - + - - + - - + - - + - - + - - + - - + - - + - - + - - + - - +
: : : : : : : : : : : :
: : : : : : : : : : : :
+ - - + - - + - - + - - + - - + - - + - - + - -(G)- - + - - + - - +
: : : : : : : : : : : :
: : : : : : : : : : : :
+ - - + - - + - - + - -(D)- - + - - + - - + - - + - - + - - + - - +
: : : : : : : : : : : :
: : : : : : : : : : : :
+ - -(B)- - + - - + - - + - - + - - + - - + - - + - - + - - + - - +
: : : : : : : : : : : :
: : : : : : : : : : : :
+ - - + - - + - - + - - + - - + - - + - - + - - + - -(E)- - + - - +
: : : : : : : : : : : :
: : : : : : : : : : : :
+ - - + - - + - - + - - + - - + - - + - - + - - + - - + - - + - - +
A: 1,2,9,10
B: 15,16,17,18
C: 28,97,98,99
D: 33,34,35,36
E: 47,48,49,50
F: 59,60,63,64
G: 69,70,73,74
H: 84,89,92,93
--
-- Bob Harris =======================================================+
| To reply, carefully remove the plastic wrapper from my address |
+====================================================================+
Ted S.
<plastic...@wrappermindspring.com> wrote in
news:BB4F3159.33501%plastic...@wrappermindspring.com:
The original post is being preserved as spoiler space.
>Howdy,
>
>In the puzzle below, the numbers 1 through 99 are to go into the 99
>squares. The numbers should form a chain-- 1 is next to 2, 2 next to
>3, and so on (diagonals don't count).
>
>The only other information you are given is the numbers that surround
>the eight lettered points. For example, the four squares touching H
>should contain 84, 89, 92, and 93.
"SHOULD"? Don't you mean "MUST"? If the given numbers are only a
suggestion, it makes the puzzle *much* easier. :-p
>The tricky part is that you don't
>know what order they should go in.
>
>Can this puzzle be solved given no more information than that?
Obviously, yes. I don't think you'd be cruel enough to put a puzzle that
couldn't be solved on your web-site. :-)
As it turned out, the only really difficult thing was figuring out the
order in which the first numbers would be around (A). After that, and
once it became clear which of the four squares around (C) contained the
number 28, it wasn't all that difficult, since one could work backwards
from each end.
>If you want to try to solve it online, point your java-enabled web
>browser at
> http://nitlion.home.mindspring.com/numerichain/2003aug1.html
>
>Numerichain Puzzle, August/1/2003
>---------------------------------
>(view with a monospace font)
+ - - + - - + - - + - - + - - + - - + - - + - - + - - + - - + - - +
: : : : : : : : : : : :
: 07 : 06 : 05 : 96 : 95 : 94 : 93 : 92 : 91 : 62 : 61 :
+ - - + - - + - - + - - + - - + - - + - -(H)- - + - - + - - + - - +
: : : : : : : : : : : :
: 08 : 03 : 04 : 97 : 98 : 83 : 84 : 89 : 90 : 63 : 60 :
+ - - + - - + - - + - -(C)- - + - - + - - + - - + - - + - -(F)- - +
: : : : : : : : : : : :
: 09 : 02 : 27 : 28 : 99 : 82 : 85 : 88 : 65 : 64 : 59 :
+ - -(A)- - + - - + - - + - - + - - + - - + - - + - - + - - + - - +
: : : : : : : : : : : :
: 10 : 01 : 26 : 29 : 30 : 81 : 86 : 87 : 66 : 67 : 58 :
+ - - + - - + - - + - - + - - + - - + - - + - - + - - + - - + - - +
: : : : : : : : : : : :
: 11 : 12 : 25 : 32 : 31 : 80 : 75 : 74 : 69 : 68 : 57 :
+ - - + - - + - - + - - + - - + - - + - - + - -(G)- - + - - + - - +
: : : : : : : : : : : :
: 14 : 13 : 24 : 33 : 34 : 79 : 76 : 73 : 70 : 55 : 56 :
+ - - + - - + - - + - -(D)- - + - - + - - + - - + - - + - - + - - +
: : : : : : : : : : : :
: 15 : 16 : 23 : 36 : 35 : 78 : 77 : 72 : 71 : 54 : 53 :
+ - -(B)- - + - - + - - + - - + - - + - - + - - + - - + - - + - - +
: : : : : : : : : : : :
: 18 : 17 : 22 : 37 : 40 : 41 : 44 : 45 : 48 : 49 : 52 :
+ - - + - - + - - + - - + - - + - - + - - + - - + - -(E)- - + - - +
: : : : : : : : : : : :
: 19 : 20 : 21 : 38 : 39 : 42 : 43 : 46 : 47 : 50 : 51 :
+ - - + - - + - - + - - + - - + - - + - - + - - + - - + - - + - - +
A: 1,2,9,10
B: 15,16,17,18
C: 28,97,98,99
D: 33,34,35,36
E: 47,48,49,50
F: 59,60,63,64
G: 69,70,73,74
H: 84,89,92,93
--
Ted S.: change .spam to .net to reply by e-mail
Homer Simpson: I'm sorry Marge, but sometimes I think we're the worst
family in town.
Marge: Maybe we should move to a larger community.
<http://www.snpp.com/episodes/7G04.html>
Fred the Wonder Worm
In article <Xns93C9E4DF8B47D8j...@127.0.0.1>,
Ted S. <fe...@bestweb.spam> wrote:
[ Solution to Bob's puzzle snipped ]
Note that the solution is not unique -- the squares 70,71,72 and
74,75,76 may be swapped with each other. Other than that it is
unique, however.
Nice puzzle, Bob!
Cheers,
Geoff.
-----------------------------------------------------------------------------
Geoff Bailey (Fred the Wonder Worm) | Programmer by trade --
ft...@maths.usyd.edu.au | Gameplayer by vocation.
-----------------------------------------------------------------------------
Willem
) Howdy,
)
) In the puzzle below, the numbers 1 through 99 are to go into the 99 squares.
) The numbers should form a chain-- 1 is next to 2, 2 next to 3, and so on
) (diagonals don't count).
)
) The only other information you are given is the numbers that surround the
) eight lettered points. For example, the four squares touching H should
) contain 84, 89, 92, and 93. The tricky part is that you don't know what
) order they should go in.
)
) Can this puzzle be solved given no more information than that?
)
) <puzzle snipped>
No, it can't. There are two possible solutions, you need additional
information around the G-spot.
Very nice puzzle, nevertheless!
SaSW, Willem (at stack dot nl)
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
Bob Harris
>> Can this puzzle be solved given no more information than that?
and Ted S. replied:
> Obviously, yes. I don't think you'd be cruel enough to put a puzzle that
> couldn't be solved on your web-site. :-)
Actually, I *am* that cruel as it turns out.
Fred the Wonder Worm wrote:
> Note that the solution is not unique -- the squares 70,71,72 and
> 74,75,76 may be swapped with each other. Other than that it is
> unique, however.
>
> Nice puzzle, Bob!
The puzzle was generated randomly by the applet.
You can try out more of them at the web site. Type in any name in the field
below the puzzle, then hit the 'NEW PUZZLE' button. Or just hit the 'NEXT
PUZZLE' button and it will make up a name for you. Of course, the name is
just used to seed the random number generator that's used to generate the
chain.
As it stands, the applet generates a random set of queries (places you know
info about), using rules about how closely they can be spaced. It makes no
attempt to guarantee that it gives you enough (or even too much)
information. The applet allows you to add your own queries to resolve
situations where you don't have enough information.
Bob H
Willem
) Actually, I *am* that cruel as it turns out.
)
) The puzzle was generated randomly by the applet.
)
) As it stands, the applet generates a random set of queries (places you know
) info about), using rules about how closely they can be spaced. It makes no
) attempt to guarantee that it gives you enough (or even too much)
) information. The applet allows you to add your own queries to resolve
) situations where you don't have enough information.
I've been playing with the applet for some time now, I must say it is a
rather nice and addicting puzzle.. I may look into an AI solving
algorithm sometime. See if my rusty skills are any good (last time I wrote
a solver AI was almost 10 years ago, for minesweeper)
Bob Harris
> I've been playing with the applet for some time now, ...
Let me know if you'd like to try a larger size. The largest I've tried is
25x25.
> ... I must say it is a rather nice and addicting puzzle..
Glad you like it.
I borrowed the idea from "LaChaino", which was invented by Michael Taylor
(it appeared in World Game Review some time in the early to mid 1980s). In
both puzzles you are trying to deduce a number chain. LaChaino is a more
difficult puzzle, though, because it you are given the *product* of the four
numbers around a query point, rather than the four numbers.
> I may look into an AI solving algorithm sometime. See if my rusty skills are
> any good (last time I wrote a solver AI was almost 10 years ago, for
> minesweeper)
I'd be very interested in seeing the results of your AI solver, if you do
it. I've thought about adding a 'training' mode to the applet that would
teach someone how to solve these. But that's not worth as much to me as
creating something else.
A couple years ago a friend wrote a pretty-stupid depth first search program
was able to solve a 10x10. I forget the running time-- I think it was an
hour or two.
One of the most interesting parts of this project, for me, was devising an
algorithm to generate the chain. Early attempts were pretty slow and prone
to getting stuck.
Bob H
Danny Kodicek
"Bob Harris" <plastic...@wrappermindspring.com> wrote in message
news:BB4FC916.3354B%plastic...@wrappermindspring.com...
> I wrote:
> >> Can this puzzle be solved given no more information than that?
>
> and Ted S. replied:
> > Obviously, yes. I don't think you'd be cruel enough to put a puzzle
that
> > couldn't be solved on your web-site. :-)
>
> Actually, I *am* that cruel as it turns out.
>
> Fred the Wonder Worm wrote:
> > Note that the solution is not unique -- the squares 70,71,72 and
> > 74,75,76 may be swapped with each other. Other than that it is
> > unique, however.
> >
> > Nice puzzle, Bob!
>
> The puzzle was generated randomly by the applet.
>
> You can try out more of them at the web site. Type in any name in the
field
> below the puzzle, then hit the 'NEW PUZZLE' button. Or just hit the 'NEXT
> PUZZLE' button and it will make up a name for you. Of course, the name is
> just used to seed the random number generator that's used to generate the
> chain.
It's a very nice puzzle indeed. Maybe you could get the applet to check
whether the user's solution is correct, rather than whether it matches the
internal solution, otherwise it gets frustrating to have a correct solution
which still doesn't win.
Danny
Willem
) Let me know if you'd like to try a larger size. The largest I've tried is
) 25x25.
Sounds very interesting! I'd like to try some larger sizes.
I don't know how easy it would be to have a user-changeable size.
)> I may look into an AI solving algorithm sometime. See if my rusty skills are
)> any good (last time I wrote a solver AI was almost 10 years ago, for
)> minesweeper)
)
) I'd be very interested in seeing the results of your AI solver, if you do
) it. I've thought about adding a 'training' mode to the applet that would
) teach someone how to solve these. But that's not worth as much to me as
) creating something else.
I've always been very interested in AI puzzle solvers, rather than brute
force, and as far as I can see this is a very nice challenge.
) One of the most interesting parts of this project, for me, was devising an
) algorithm to generate the chain. Early attempts were pretty slow and prone
) to getting stuck.
Yes, I considered that, it's quite a neat little problem in itself.
Time to dig out ye ole compiler and see what I can whip together.
Bob Harris
> It's a very nice puzzle indeed. Maybe you could get the applet to check
> whether the user's solution is correct, rather than whether it matches the
> internal solution, otherwise it gets frustrating to have a correct solution
> which still doesn't win.
My short answer is that the person should make an additional query in this
case, by clicking on an empty dot.
So I guess it's really a case of what's a "correct solution" or not. Using
an (admittedly silly) analogy, I could solve a crossword puzle by filling in
whatever letters I pleased, then be disappointed because my solution doesn't
match the one printed in the back of the magazine.
I guess my perspective on this is based on how I've been solving these up
until two days ago. That was when I added the automated queries. Prior to
that, the applet presented a blank puzzle, and you had to make every query
yourself. I've been solving them this way for years (using pencil and
paper). But I found it kind of tedious to make the first few queries, and I
also thought that having some queries up would make it easier for new
solvers to understand the puzzle. So I added the automated queries. I
didn't make any attempt for them to uniquely determine the solution. In
fact, for the smaller puzzles the number of queries provided is usually many
more than are needed.
Now, you can pretty much tell if you have the internal solution or not. If
you've completed a chain, and nothing on the screen is red, and the applet
doesn't say "congratulations", then you know you must have something
'wrong'. What you have is consistent with the information you see, of
course, but it's still not the solution. In a sense, this in itself is
extra information about the solution.
You can try that 'no queries given' variation at
http://nitlion.home.mindspring.com/numerichain/9x11nq.html
Thanks for the feedback!
Bob H
Bob Harris
> Sounds very interesting! I'd like to try some larger sizes.
I've set up 14x14 at the web site now.
http://nitlion.hom.mindspring.com/numerichain/14x14.html
> I don't know how easy it would be to have a user-changeable size.
Not very hard. I've considered it. It's mostly a matter of finding space
in the applet window to put a component that would allow such selection.
One issue is that the applet window size really needs to be bigger for
larger puzzles, and that would require me to rethink the way the applet
interfaces with the browser. Currently the puzzle size and applet window
size are specified in the html for whichever size you're running.
> ) One of the most interesting parts of this project, for me, was devising an
> ) algorithm to generate the chain. Early attempts were pretty slow and prone
> ) to getting stuck.
>
> Yes, I considered that, it's quite a neat little problem in itself.
The method I use is a depth first search, stopping when it find a solution.
It sweeps across the grid by diagonals, keeping track of how the small chain
pieces are connected, joining them as it goes, and using coin flips whenever
it has a choice of which path to explore. It's got a little smarts built
into it to avoid getting stuck, but only using local rules.
The resulting chains might possibly have some bias resulting from this
algorithm, in that one type of chain might be more likely than another. But
if there is I haven't noticed it yet. The endpoints are chosen unformly
(within the contraints of what can yield a valid chain) before the search
begins. And when a solution is found, it's randomly flipped and/or rotated.
It's unlikely that this algorithm will generate a spiral or a
snakes-and-ladders arragnement, but those are a very small percentage of all
the possible chains anyway.
Thanks for your thoughts,
Bob H
Leroy Quet
> Howdy,
>
> In the puzzle below, the numbers 1 through 99 are to go into the 99 squares.
> The numbers should form a chain-- 1 is next to 2, 2 next to 3, and so on
> (diagonals don't count).
>
> The only other information you are given is the numbers that surround the
> eight lettered points. For example, the four squares touching H should
> contain 84, 89, 92, and 93. The tricky part is that you don't know what
> order they should go in.
>
> Can this puzzle be solved given no more information than that?
>
Some of those who like this puzzle MIGHT be interested in these
similar numerical "grid-mazes" which I came up with, and posted to
rec.puzzles, a while back.
Threads:
"Letters/Numbers Grid-Maze"
http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&threadm=b4be2fdf.0211291519.5b041a70%40posting.google.com&rnum=5&prev=
Thanks,
Leroy Quet
Willem
)> In the puzzle below, the numbers 1 through 99 are to go into the 99 squares.
)> The numbers should form a chain-- 1 is next to 2, 2 next to 3, and so on
)> (diagonals don't count).
)>
)> The only other information you are given is the numbers that surround the
)> eight lettered points. For example, the four squares touching H should
)> contain 84, 89, 92, and 93. The tricky part is that you don't know what
)> order they should go in.
)>
)> Can this puzzle be solved given no more information than that?
)>
)>....
I've gotten a first version of an AI solver together, which does reasonably
well, is quite fast, but seems to miss some obvious patterns.
I'm currently thinking about the obvious patterns it's missing, and I also
think it's a good starting point to build brute force on top of.
The idea is simply to have a list of positions each number can be in, and
then iteratively restrict the lists from neighbouring numbers.
For example, if the number 12 can be at four different positions, then the
numbers 11 and 13 can only be at the 12 positions surrounding these, so you
can remove all other positions for the lists of 11 and 13.
But you also need to use the reverse information; what numbers can be at a
given position. So far, it only checks for single numbers at given
positions, but as said it misses a lot of obvious patterns.
I'll update when I get a good idea how to solve this.
Vikas Navik
recently):
+ - - + - - + - - + - - + - - + - - + - - + - - + - - + - - + - - +
: 7 : 6 : 5 : 96 : 95 : 94 : 93 : 92 : 91 : : :
: : : : : : : : : : 62 : 61 :
+ - - + - - + - - + - - + - - + - - + - -(H)- - + - - + - - + - - +
: 8 : 3 : 4 : 97 : 98 : 83 : 84 : 89 : 90 : : :
: : : : : : : : : : 63 : 60 :
+ - - + - - + - - + - -(C)- - + - - + - - + - - + - - + - -(F)- - +
: 9 : 2 : 27 : 28 : 99 : 82 : 85 : 88 : : : :
: : : : : : : : : 65 : 64 : 59 :
+ - -(A)- - + - - + - - + - - + - - + - - + - - + - - + - - + - - +
: 10 : 1 : : 29 : 30 : 81 : 86 : 87 : : : :
: : : 26 : : : : : : 66 : 67 : 58 :
+ - - + - - + - - + - - + - - + - - + - - + - - + - - + - - + - - +
: : : : : 31 : 80 : : : : : :
: 11 : 12 : 25 : 32 : : : 75 : 74 : 69 : 68 : 57 :
+ - - + - - + - - + - - + - - + - - + - - + - -(G)- - + - - + - - +
: : : : : : 79 : 76 : : : : :
: 14 : 13 : 24 : 33 : 34 : : : 73 : 70 : 55 : 56 :
+ - - + - - + - - + - -(D)- - + - - + - - + - - + - - + - - + - - +
: : : : : : 78 : 77 : : : : :
: 15 : 16 : 23 : 36 : 35 : : : 72 : 71 : 54 : 53 :
+ - -(B)- - + - - + - - + - - + - - + - - + - - + - - + - - + - - +
: : : : : : : : : : : :
: 18 : 17 : 22 : 37 : 40 : 41 : 44 : 45 : 48 : 49 : 52 :
+ - - + - - + - - + - - + - - + - - + - - + - - + - -(E)- - + - - +
: : : : 38 : 39 : : : : : : :
: 19 : 20 : 21 : : : 42 : 43 : 46 : 47 : 50 : 51 :
+ - - + - - + - - + - - + - - + - - + - - + - - + - - + - - + - - +
Vikas