| [request to foilman]Lack of big puzzles |
MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s | Posted - 2007.12.09 00:00:42
I've been doing the "Beast of the Month" for a while now (each at least twice, I think), but they do get boring after doing the same ones repeatedly. I've been wondering if you could offer more big (or even bigger) puzzles that don't necessarily have to be competitive - the Beast of the Month isn't competitive either, after all.
My personal opinion is that while small puzzles are superior on the computer (you don't have to print them, you don't waste the majority of the paper, printing takes too much time compared to the time it takes to solve them, etc.), larger puzzles are more comfortable when printed (until the puzzle is so big that its resized version is illegible when printed) because you don't have to do them completely at the same time, you aren't as limited with trying different solutions, et cetera.
I tried using Loopy, but I thought (maybe I'm wrong, though) that its puzzles weren't as good as the ones from here - and other puzzles don't offer an easy printout option. I thought about buying the official Slither Link books from nikoli, but I guess I only really want the square ones (not with 3, 5 or more corners), and they probably won't have that many big ones.
On a more general note, I really like the puzzles and the Kwontomloop programm from this website but I've already done all weekly puzzles at least once (and I'm currently in the process of doing them all over again because you only get the offer to play a Wrong immediately after finishing them, and I'm currently trying to get all Wrongs, too), so I was wondering if you could, in some form, offer more?
PS: I have no idea of the processing power and time involved in creating the puzzles from this page and, theoretically, bigger ones - after all, Slither Link is NP complete (whatever that means) so the processing time increases exponentially. Maybe creating bigger puzzles isn't even feasible or possible?
At any rate, I'd be happy about any kind of answer. |
Brian
Kwon-Tom Obsessive
Puzzles: 4767
Best Total: 9m 6s | Posted - 2007.12.09 05:33:29
If you've liked my puzzles, I could generate a few larger ones. Just let me know what size. (I'm not sure how the difficulty level will translate, since I haven't done many real large ones.)
Last edited by Brian - 2007.12.09 05:33:48 |
RaDiCaLedward_26
Kwon-Tom Addict
Puzzles: 335
Best Total: 33m 17s | Posted - 2007.12.09 18:29:32
I have an idea about this. You could make weekly puzzles that are bigger than the weekend puzzles but smaller than the beasts. I'm glad this was brought up because i agree with what Mond is saying. |
chairman
Kwon-Tom Obsessive
Puzzles: 1397
Best Total: 17m 32s | Posted - 2007.12.09 18:51:15
Quote: Originally Posted by brian If you've liked my puzzles, I could generate a few larger ones. Just let me know what size. (I'm not sure how the difficulty level will translate, since I haven't done many real large ones.) |
I like your puzzles very much, Brian, just as I like the beasts, though it seems that the beasts are getting easier by the time. I'd be interested to see larger sized puzzles of yours. The maximum size of user puzzles is 20x14, but a loopy string here at the forum would be just as convenient (and easier to print). |
Tilps
Kwon-Tom Obsessive
Puzzles: 6507
Best Total: 20m 22s | Posted - 2007.12.09 21:45:56
My Loop-De-Loop program offers the ability to print out directly, and if you are willing to wait a while can generate pretty huge puzzles (depending on difficulty level the amount of time it takes to generate differs quite greatly).
However, the puzzle type will differ significantly from kwon-tom style as the solver/generator doesn't use preprogrammed patterns at all. This lack of patterns means that sometimes you have to increase the difficulty level before certain aspects which a human considers trivial appear regually in the puzzle, as the logic required to derive the pattern is complex, but localized and easily memorable.
I was working on a version which supported loading/saving as loopy format, but I think I got sidetracked. (Indeed I did, I might see what I can do about that tonight, finally have the file format, so it shouldn't take too long.)
Loop-De-Loop
Last edited by Tilps - 2007.12.09 22:04:50 |
astrokath
Kwon-Tom Obsessive
Puzzles: 3258
Best Total: 13m 42s | Posted - 2007.12.09 22:29:12
Quote: Originally Posted by mondsemmel I've been doing the "Beast of the Month" for a while now (each at least twice, I think), but they do get boring after doing the same ones repeatedly. |
Are you completing them without the use of 'crutches'? |
Naivoj
Kwon-Tom Addict
Puzzles: 314
Best Total: 33m 50s | Posted - 2007.12.10 07:37:33
If Foilman want to do something about this, I think the first step is to allow larger user puzzle. I am suspecting just that might be difficult to implement.
I just post several largest (20x14) user puzzles. |
foilman
Kwon-Tom Admin
Puzzles: 3410
Best Total: 24m 6s | Posted - 2007.12.10 16:24:48
The main limitation on the size of puzzles to solve "online", via this site, is the Javascript code underlying it - any bigger than about 20x14 and it starts to get slow. Also it's harder to fit the puzzles on a small display (I'm fine with my widescreen monitor but not everyone has one!), so I've kept the interactive puzzles small.
However, I could fairly easily add a "weekly" puzzle, which isn't quite as big as a beast, but is larger than 20x14, and make it print-out or export only. Or maybe two beasts a month... one fairly easy (like they are currently) and one harder for those who like a challenge?
Ultimately I'd like to get the puzzles running in Java, or Flash, or something a bit easier to scale up than Javascript, then you could indeed solve huge puzzles online too. But my time is very limited these days so don't count on it happening soon!!!! |
jasonharper
Kwon-Tom Obsessive
Puzzles: 1349
Best Total: 25m 18s | Posted - 2007.12.10 17:10:07
Quote: Originally Posted by foilman The main limitation on the size of puzzles to solve "online", via this site, is the Javascript code underlying it - any bigger than about 20x14 and it starts to get slow. |
I took a quick look at the page source of a puzzle, and I think the problem is your use of getElementById. If, instead of the ID, the onMouseDown handlers passed this (which will be a direct reference to the img objects), those lookups could be eliminated. |
Naivoj
Kwon-Tom Addict
Puzzles: 314
Best Total: 33m 50s | Posted - 2007.12.10 18:14:18
Quote: Originally Posted by foilman Also it's harder to fit the puzzles on a small display (I'm fine with my widescreen monitor but not everyone has one!), so I've kept the interactive puzzles small.
|
|
MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s | Posted - 2007.12.10 19:21:54
I also wonder how the difficulty level of bigger puzzles would generally compare to the smaller ones when generated with generators that haven't been adjusted for that purpose. Would be interesting to try some, though!
Quote: Originally Posted by astrokath Are you completing them without the use of 'crutches'? |
I occasionally use pencils to do something similar to the "Fix Current Position" feature, e.g. in the Beast of the Month from June 2007 (the part in the top center area requires tons of time and thinking, if memory serves correctly, this was the most difficult one) using a pencil to try a path, see if it leads to a logical conflict so I can cross out that possibility, then look if I can continue with my normal solution methods or if I have to try another path with trial & error again. Do you mean that? I had to do that several times, with small parts of perhaps every second or third puzzle or something like that.
Thanks for the answer, foilman. You might want to look at the java plugin from www.janko.at, e.g. from a puzzle like http://www.janko.at/Raetsel/Slitherlink/100.a.htm (The most difficult one from their site according to their difficulty ranking, I remember needing several hours and all colours to complete it - although that counts as "far too difficult" for me already.) - it has a size of 45x30, so it's even larger than the beasts at 40x30, and while its initial loading times are only okay (my browser freezes for a few seconds after opening one of the very large puzzles), afterwards there are no problems anymore.
According to statistics frequently cited these days about the energy saving possibilities (or lack thereof) of black websites in comparison to white ones, nowadays 75% of all monitors are flat screens, e.g. TFTs (and therefore need an almost equal amount of energy to display the colours black and white), so it's probably reasonable to assume that the amount of people with at least 19 inch monitors is steadily increasing - though I don't have any statistics backing that assumption. |
astrokath
Kwon-Tom Obsessive
Puzzles: 3258
Best Total: 13m 42s | Posted - 2007.12.10 20:05:45
Quote: Originally Posted by mondsemmel Quote: Originally Posted by astrokath Are you completing them without the use of 'crutches'? |
I'm not quite sure what you mean by that. Marking impossible locations as X? |
No X's, and no pencils!
Quote: Originally Posted by mondsemmel Using Higlander patterns? |
I must confess, I still rely on my good friend McLeod... |
hught
Kwon-Tom Obsessive
Puzzles: 1967
Best Total: 30m 27s | Posted - 2007.12.10 21:40:39
MondSemmel,
"NP-complete" means that the problem is on a par with the infamous "travelling salesman" problem ("what is the shortest route taking in all N islands?") when it comes to a computational solution.
The NP means "non-polynomial", and is a reference to the fact that the formula for the time taken to perform an exhaustive search for a solution rises exponentially with size, rather than just being a polynomial function of the size. So small problems are tractable, but larger ones rapidly grow unmanageable.
Question for the mathmos: what's the formula for the number of different possible paths round a grid of size m by n? |
procrastinator
Kwon-Tom Obsessive
Puzzles: 1083
Best Total: 12m 56s | Posted - 2007.12.10 22:40:07
Quote: Originally Posted by hught
The NP means "non-polynomial"
|
No it doesn't. It means "non-deterministically polynomial". If you guess the right answer you can prove it's true in polynomial time. Unfortunately, guessing is non-deterministic.  So if you don't need a deterministic guarantee that you will solve it, you might solve it in polynomial time.
Quote: Originally Posted by hught
and is a reference to the fact that the formula for the time taken to perform an exhaustive search for a solution rises exponentially with size, rather than just being a polynomial function of the size.
|
No. This has never been proven. For all we know, NP is just the same as polynomial, though we strongly suspect otherwise. And by definition all polynomial problems are also NP.
Quote: Originally Posted by hught
So small problems are tractable, but larger ones rapidly grow unmanageable.
|
Basically hardware improves exponentially so it will outstrip any polynomial eventually. No such guarantee with exponentially-hard problems.
Quote: Originally Posted by hught
Question for the mathmos: what's the formula for the number of different possible paths round a grid of size m by n?
|
I haven't looked it up, but I really doubt anyone's solved that. It looks like a really hard problem with no likely applications.  |
Tilps
Kwon-Tom Obsessive
Puzzles: 6507
Best Total: 20m 22s | Posted - 2007.12.11 02:01:57
Quote: Originally Posted by procrastinator I haven't looked it up, but I really doubt anyone's solved that. It looks like a really hard problem with no likely applications. |
Which is what I thought about the number of distinct finite topologies of size N, and yet it turned out someone had worked it out... Although I think their formula was complicated enough that it was computationally faster to just generate them all and count the distinct ones... |
Brian
Kwon-Tom Obsessive
Puzzles: 4767
Best Total: 9m 6s | Posted - 2007.12.11 03:54:08
Quote: Originally Posted by hught Question for the mathmos: what's the formula for the number of different possible paths round a grid of size m by n? |
I did look at this a while ago, but without much success. I wrote a program to determine this number for small m and n. Here are the numbers that I got (for m=n, including the "empty" path):
For (m,n) = (1,1) : 2
For (m,n) = (2,2) : 14
For (m,n) = (3,3) : 214
For (m,n) = (4,4) : 9350
For (m,n) = (5,5) : 1222364
For (m,n) = (6,6) : 487150372
For (m,n) = (7,7) : 603841648932
For (m,n) = (8,8 ) : 2318527339461266
For (m,n) = (9,9) : 27359264067916806102
For (m,n) = (10,10) : 988808811046283595068100
For (m,n) = (11,11) : 109331355810135629946698361372
For (m,n) = (12,12) : 36954917962039884953387868334644458
For (m,n) = (13,13) : 38157703688577845304445530851242055267354
For large m and n, it's probably going to look something like c^(m*n) for some constant c.
Last edited by Brian - 2007.12.11 03:54:45 |
Tilps
Kwon-Tom Obsessive
Puzzles: 6507
Best Total: 20m 22s | Posted - 2007.12.11 05:26:13
Vaguely connected, I am wondering if there is an efficient heuristic for determining 'interesting' closed loops of cells on a grid. Where interesting is defined as the loops for which all bar one or two edges are either known (or have a known same/not same relationship). For further reduction of result space, maybe the ones which have least enclosed area are the only ones needed to be identified. |
procrastinator
Kwon-Tom Obsessive
Puzzles: 1083
Best Total: 12m 56s | Posted - 2007.12.11 12:49:06
Quote: Originally Posted by brian Here are the numbers that I got (for m=n, including the "empty" path):
|
Couldn't find your list in the online encyclopedia of integer sequences, with or without the empty path, so I think we really are out of luck. |
procrastinator
Kwon-Tom Obsessive
Puzzles: 1083
Best Total: 12m 56s | Posted - 2007.12.11 12:50:13
Quote: Originally Posted by tilps Quote: Originally Posted by procrastinator I haven't looked it up, but I really doubt anyone's solved that. It looks like a really hard problem with no likely applications. |
Which is what I thought about the number of distinct finite topologies of size N |
You can't tell me that doesn't have applications? |
chairman
Kwon-Tom Obsessive
Puzzles: 1397
Best Total: 17m 32s | Posted - 2007.12.11 15:53:31
Quote: Originally Posted by naivoj If Foilman want to do something about this, I think the first step is to allow larger user puzzle. I am suspecting just that might be difficult to implement.
I just post several largest (20x14) user puzzles. |
Thanks for the puzzles. I am trying them from hard to less hard. Somehow an archived puzzle slipped into your collection though. 6/9 equals foilman's 25th November 2006. |
