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?
-- -- Bob Harris =======================================================+ | To reply, carefully remove the plastic wrapper from my address | +====================================================================+
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.
-- 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>
) 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
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.
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.
) 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)
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
Willem wrote: > 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.
> 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.
) 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.
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
Danny Kodicek wrote: > 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.
> 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.
