| Sparse puzzles and extended highlander solutions |
LoopGuy
Kwon-Tom Obsessive
Puzzles: 761
Best Total: 45m 59s | Posted - 2012.07.14 18:12:40
I've always been attracted to puzzles that are sparse. By "sparse", I mean that have unique solutions that include a large number of line segments for each number. I've posted one to the public user puzzles that is the best I've found yet, with 7 line segments per number.
I define sparse that way to avoid solutions which "cut off" most of the space. For example, I could put this into any corner of a bigger puzzle and use only 3 numbers:
But that's only 2.67 line segments per number, and isn't very interesting either.
Some of these (maybe all of them) seem to be easily solvable by what I call an "extended highlander" technique. In other words, for this puzzle to be unique, it has to have a bunch of lines running through all this space with no numbers.
Anyone else know of any sparse unique puzzles? I'm afraid the computer program I wrote is too slow to find significantly bigger ones (although I have some ideas to make it faster).
Last edited by LoopGuy - 2012.07.14 18:12:55 |
MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s | Posted - 2012.07.15 02:28:35
Hm. This is an interesting idea. I'm afraid I don't have anything meaningful to contribute right now. Except for this, but it seems a bit obvious...
An line of zeroes could be infinitely extended to the left while preserving the the purpose of the puzzle. But I'm not sure if that would result in a "sparse" puzzle by your definition.
EDIT: In general, I'm thinking a puzzle with one single one, two or three and a huge number of zeroes might potentially result in the kind of puzzle you are asking for.
EDIT2: I realized the puzzle above would have a better ratio of lines to numbers if the line of 00000s were replaced with a chain of 020202020, ending in 0 on both sides:
Last edited by MondSemmel - 2012.07.15 02:40:22 |
LoopGuy
Kwon-Tom Obsessive
Puzzles: 761
Best Total: 45m 59s | Posted - 2012.07.15 03:00:10
Actually, that brings up an interesting topic as well. For every zero you add, you add four line segments, so as the width grows bigger, the ls/n factor goes to 4.0, which is not bad. While smaller sizes do better then that, I've been thinking that larger sizes will be less sparse, so that may be as sparse as it gets at something like 20x5.
Ah, and now you added the 020202... lines. That gives us a limit of 6 ls/n. Nice.
Last edited by LoopGuy - 2012.07.15 03:02:12 |
muhorka
Kwon-Tom Obsessive
Puzzles: 2960
Best Total: 13m 45s | Posted - 2012.07.15 11:03:47
But i can reach infinity ls/n. See the example
But ignore the 2 bottom rows (so size is 10x1), so there will be only 2 numbers and as many lines as you want. But this way isnīt so intristing as your puzzle. |
MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s | Posted - 2012.07.15 14:10:13
Quote: Originally Posted by muhorka But i can reach infinity ls/n. See the example |
Haha! I didn't think of that. That's actually amazing. |
LoopGuy
Kwon-Tom Obsessive
Puzzles: 761
Best Total: 45m 59s | Posted - 2012.07.15 19:53:06
I agree, anything with a side of 1 can be made as sparse as you want. Technically, a 1x1 needs no numbers, as I understand the definition of the puzzles, so I'm not even sure the ls/n definition I'm suggesting is even valid for that case.
It still leaves the question open about puzzles with sides > 1. |
muhorka
Kwon-Tom Obsessive
Puzzles: 2960
Best Total: 13m 45s | Posted - 2012.07.16 18:15:42
I find 2 another examples of 4 ln/n.
(size 2x3)
And one with 5 ln/n
Last edited by muhorka - 2012.07.16 18:22:09 |
Brian
Kwon-Tom Obsessive
Puzzles: 4909
Best Total: 9m 6s | Posted - 2012.07.17 01:38:29
This pattern (repeating the inside 30-0 section) gets you up to a 6.666... limit.
|
Brian
Kwon-Tom Obsessive
Puzzles: 4909
Best Total: 9m 6s | Posted - 2012.07.17 17:15:38
The small grids are aided by the grid's borders, so in a sense their ratios are inflated because of the hidden 0 clues on the outside of the grid. Maybe the more "natural" question is what's the best ratio you can get on an infinite grid, one without borders. And here I suspect the best ratio you can get is 4, achieved a single "4" clue. If that's not allowed, I think you can get arbitrarily close to 4 but not reach it. One way of doing this is by using lots of runs of 30 - 03 to create "borders":
|
LoopGuy
Kwon-Tom Obsessive
Puzzles: 761
Best Total: 45m 59s | Posted - 2012.07.18 01:59:55
Quote: Originally Posted by Brian I suspect the best ratio you can get is 4, achieved a single "4" clue. If that's not allowed, I think you can get arbitrarily close to 4 but not reach it |
I'm not sure, but since you do get border effects at wherever the boarders are, I wonder if you are actually slightly over 4, not under 4, for any finite puzzle, not matter how large. Yes? No?
I'll let some of the more experience puzzle builders take a crack at some larger puzzles. I don't trust my skills as a puzzle builder (or solver) yet to determine if a puzzle is unique or not, and my computer program is in pieces at the moment as I try to speed it up to handle larger puzzles.
Last edited by LoopGuy - 2012.07.18 02:00:20 |
Brian
Kwon-Tom Obsessive
Puzzles: 4909
Best Total: 9m 6s | Posted - 2012.07.18 04:22:55
Quote: Originally Posted by LoopGuy I'm not sure, but since you do get border effects at wherever the boarders are, I wonder if you are actually slightly over 4, not under 4, for any finite puzzle, not matter how large. Yes? |
I was suggesting the same question but without borders--basically, where you have to clue in the "borders" yourself with 0's or use some other method to ensure that there's still only one solution. And in this case I don't think you can reach 4 (except if we allow the single "4" clue), although you can get arbitrarily close using bigger and bigger puzzles. |
LoopGuy
Kwon-Tom Obsessive
Puzzles: 761
Best Total: 45m 59s | Posted - 2012.07.18 07:01:04
Quote: Originally Posted by Brian
I was suggesting the same question but without borders--basically, where you have to clue in the "borders" yourself with 0's or use some other method to ensure that there's still only one solution. And in this case I don't think you can reach 4 (except if we allow the single "4" clue), although you can get arbitrarily close using bigger and bigger puzzles.
|
Going back to MondSemmel's idea, if you don't bother with boarders, but just repeat the following forever, don't you get equal exactly 4? Or can we even have an infinite puzzle without running into problems with the definition of a loop?
|
Brian
Kwon-Tom Obsessive
Puzzles: 4909
Best Total: 9m 6s | Posted - 2012.07.18 20:17:15
Yeah, when I said "infinite grid", I really just meant a big borderless grid. Infinite puzzles or loops don't really make sense. And you're right that MondSemmel's pattern is another way to get arbitrarily close to 4, when you use it in larger and larger puzzles.
Last edited by Brian - 2012.07.18 20:17:34 |
mathmaniac
Kwon-Tom Obsessive
Puzzles: 1293
Best Total: 20m 57s | Posted - 2012.07.18 22:42:32
Quote: Going back to MondSemmel's idea, if you don't bother with boarders, but just repeat the following forever, don't you get equal exactly 4? Or can we even have an infinite puzzle without running into problems with the definition of a loop? |
This would work except it doesn't have a single solution. One of the rules of slither link is that there must be only one solution to the puzzle. |
LoopGuy
Kwon-Tom Obsessive
Puzzles: 761
Best Total: 45m 59s | Posted - 2012.07.18 23:27:39
Quote: Originally Posted by mathmaniac This would work except it doesn't have a single solution. One of the rules of slither link is that there must be only one solution to the puzzle. |
I had missed that the lines could u-turn at any one place and go back to the side they came from. I'm still at the point where I trust my computer programming then I trust my mind (and I am quite aware that I make mistakes at programming AND loops). |
mathmaniac
Kwon-Tom Obsessive
Puzzles: 1293
Best Total: 20m 57s | Posted - 2012.07.19 00:19:03
Imagine this puzzle, but the middle section with the zeroes is expanded infinitely. The infinite limit here would be 4 ln/n. I included the lines to make it clearer.
Last edited by mathmaniac - 2012.07.19 00:24:21 |
MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s | Posted - 2012.07.19 01:39:16
Quote: Originally Posted by Brian This pattern (repeating the inside 30-0 section) gets you up to a 6.666... limit. |
Quote: Originally Posted by mathmaniac |
A quick suggestion: I think these two puzzle designs are probably good (and interesting) enough that you could turn them into proper, interesting User Puzzles (e.g. 10x10?). What do you two think?
Last edited by MondSemmel - 2012.07.19 01:39:57 |
LoopGuy
Kwon-Tom Obsessive
Puzzles: 761
Best Total: 45m 59s | Posted - 2012.07.28 03:55:13
Quote: Originally Posted by muhorka I find 2 another examples of 4 ln/n. |
That one works, but this one is 6 ls/n:
Quote: Originally Posted by muhorka |
Alas, this one has two solutions, so it doesn't work.
Quote: Originally Posted by muhorka |
There seems to be a whole bunch of 5's at 4x3. Interestingly, they all have 2's and all but two have 3's. No 0's or 1's. This one's pretty compact:
While this one has only 2's, no 3's
|
MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s | Posted - 2012.07.28 09:41:13
Quote: Originally Posted by LoopGuy Quote: Originally Posted by muhorka |
Alas, this one has two solutions, so it doesn't work. |
Oh wow, I didn't realize...
That's amazing.
The 3-3 pattern is one of the patterns I learned first, but it only works if there are any other numbers in the puzzle than just these two...
Last edited by MondSemmel - 2012.07.28 09:43:34 |
