[request to foilman]Lack of big puzzles 
MondSemmel KwonTom Obsessive Puzzles: 3953 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 KwonTom Obsessive Puzzles: 3237 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 KwonTom 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 KwonTom Obsessive Puzzles: 1395 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 KwonTom Obsessive Puzzles: 4293 Best Total: 20m 22s  Posted  2007.12.09 21:45:56 My LoopDeLoop 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 kwontom 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.) LoopDeLoop
Last edited by Tilps  2007.12.09 22:04:50 
astrokath KwonTom Obsessive Puzzles: 3093 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 KwonTom 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 KwonTom Admin Puzzles: 1720 Best Total: 24m 8s  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 printout 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 KwonTom 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. 
Something doesn't seem quite right here  the amount of work needed to handle a click shouldn't depend on the size of the puzzle at all.
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 KwonTom 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.

I have a widescreen monitor too, and many people these days have 19+" flat screens. If the "get slow" Javascript problem can be solved, why not allowing larger user puzzles to the benefit of so many. And when posting large user puzzles the author should also display the loopy string in the puzzle description field for those who do not have larger monitor. These are non competitive puzzles, so it should not create a controversy. 
MondSemmel KwonTom Obsessive Puzzles: 3953 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'm not quite sure what you mean by that. Marking impossible locations as X? Using Higlander patterns? 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 KwonTom Obsessive Puzzles: 3093 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 KwonTom Obsessive Puzzles: 1966 Best Total: 30m 27s  Posted  2007.12.10 21:40:39 MondSemmel,
"NPcomplete" 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 "nonpolynomial", 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 KwonTom Obsessive Puzzles: 1083 Best Total: 12m 56s  Posted  2007.12.10 22:40:07
Quote: Originally Posted by hught The NP means "nonpolynomial"

No it doesn't. It means "nondeterministically polynomial". If you guess the right answer you can prove it's true in polynomial time. Unfortunately, guessing is nondeterministic. 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 exponentiallyhard 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 KwonTom Obsessive Puzzles: 4293 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 KwonTom Obsessive Puzzles: 3237 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 KwonTom Obsessive Puzzles: 4293 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 KwonTom 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 KwonTom 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 KwonTom Obsessive Puzzles: 1395 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. 