| Discussions on User Beast Puzzles |
MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s | Posted - 2009.10.04 10:04:38
Hi, I was just wondering if anyone could upload some more beasts again  - It's been quite a while since the last ones.
Alternatively, if anyone could give me a good program to generate highly difficult beast-sized puzzles (40x30) with unique solutions, I'd be more than happy to regularly generate and post them here myself. I'm sorry to say that I have neither the skills nor the talent to write such a program myself.
(My favorite puzzles are those by Naivoj and lodenkamper, and puzzles similar to them.) |
Tilps
Kwon-Tom Obsessive
Puzzles: 6722
Best Total: 18m 37s | Posted - 2009.10.05 11:19:20
I posted some more loop de loop puzzles, 8, 9 and 10 are all results of attempts to make really hard but not requiring nested guess (or highlander since my program has no idea about highlander), but I imagine the difficulty will vary between them.
7 is easier because I had the wrong settings on so I aborted it before it made the puzzle really hard.
Loop de loop is online if you want to give it a try, but fair warning generating a 40x30 puzzle takes a while if you crank the settings for maximum difficulty.
8,9 and 10 were generated on target line fraction 0.9, target boring bits 0.05, simple generator, no restriction, no nested guess (just takes too long), no interactions (obsolete and slows things down), no 'no multiple loop solutions' (since it makes puzzles easier). All colouring options on, common consequences on, edge restrictions on. They took over half an hour each on my machine. (Although I generated all of them at the same time since I have 4 cpus and the generator only uses one.)
Last edited by Tilps - 2009.10.05 11:20:20 |
MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s | Posted - 2009.10.05 13:41:23
Thanks - I haven't looked at your new puzzles yet but will soon. I was just wondering about the following:
Quote: Originally Posted by tilps no 'no multiple loop solutions' (since it makes puzzles easier) |
I'm not a native speaker in English, but does this mean that the puzzles do not have unique solutions (like all the "official" puzzles on kwontomloop.com do)? |
Tilps
Kwon-Tom Obsessive
Puzzles: 6722
Best Total: 18m 37s | Posted - 2009.10.05 19:12:21
All problems should have a unique solution.
If 'no multiple loops' is enabled, the solver makes no attempt to check whether it is closing a loop early. Checking whether a loop is closed early rules out invalid solutions for puzzles where the clues can be solved by 2 or more loops.
Since the way my puzzles are generated guarantees that there exists a single loop solution, if the solver doesn't check for closing the loop early and it finds a solution, there must not exist any way the clues can be (invalidly) solved with 2 or more loops. That is what I mean by 'no multiple loops', there does not exist an invalid solution to the puzzle which is only invalid because it uses more than one loop. |
MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s | Posted - 2009.10.10 12:22:16
Quote: Originally Posted by tilps Loop de loop is online if you want to give it a try, but fair warning generating a 40x30 puzzle takes a while if you crank the settings for maximum difficulty.
8,9 and 10 were generated on target line fraction 0.9, target boring bits 0.05, simple generator, no restriction, no nested guess (just takes too long), no interactions (obsolete and slows things down), no 'no multiple loop solutions' (since it makes puzzles easier). All colouring options on, common consequences on, edge restrictions on. They took over half an hour each on my machine. (Although I generated all of them at the same time since I have 4 cpus and the generator only uses one.) |
What setting do I have to change to get rid of the large areas full of zeros? Right now, both my puzzles (I think I'll generate two more and then post them in the beast thread) have them, and while they were really quite difficult (I may just lack practice, though), the empty areas were a bit frustrating considering how much time it took to generate the puzzles.
I've also solved the first three of your puzzles (I didn't solve LDL10 yet - I made a mistake and had to start over, and I get a bit annoyed at myself when that happens) but while LDL7 definitely was the easiest of the puzzles, all of them had a good level of difficulty - certainly a lot of fun to solve! |
Tilps
Kwon-Tom Obsessive
Puzzles: 6722
Best Total: 18m 37s | Posted - 2009.10.10 23:52:28
The boring bits fraction, reduce that and the areas of 0's should go down. Increasing line length fraction also reduces 0's, but boring bits fraction overrides that in a way which is more likely to succeed to generate a loop.
However if you reduce it too far, the generator may give you a random crappy loop with a big batch of 0's. This is because it tries a limited number of times to make a loop to your specifications before it gives up and just chooses a loop, under the assumption you would at least like to play something...
If you want to experiment with the settings a few times, you can hit abort early during the generation process and it will show you a puzzle (just with most of the numbers still filled in, so not a hard one). That way you can get a feel for whether the settings are working for you before you leave one to run for the full hour.
BTW, when I said over half an hour, I don't actually remember exactly how long...
I'm currently working on a design improvement which will both increase difficulty and possibly improve generation performance. Currently it spends a lot of time to realise that a puzzle is no longer solvable at all as it tries to make a puzzle harder, usually because the puzzle now has multiple solutions in a specific area and currently my code has no way to detect this quickly.
Last edited by Tilps - 2009.10.11 00:02:54 |
Differ
Kwon-Tom Fan
Puzzles: 35 | Posted - 2009.11.18 07:44:19
All this talk of solvers makes me want to create my own!
Also, Tilps: Naivoj's 2-only puzzles defeat your solver pretty handily. Or at least they seem to: your visual solver goes through the same pattern twice (unnecessarily?) and then decides just to brute force the whole thing.
Last edited by Differ - 2009.11.18 07:45:51 |
v_e_e_n_c_a
Kwon-Tom Obsessive
Puzzles: 2080
Best Total: 32m 53s | Posted - 2009.11.20 13:39:39
Interesting results to new Tilps puzzles posted - the harder one LDL 17 is solved by my solver in about 0,1 sec.. And the easier (as he said there were no trials (only the new feature) is only solved in about 90% (in the same time).. |
Tilps
Kwon-Tom Obsessive
Puzzles: 6722
Best Total: 18m 37s | Posted - 2009.11.24 21:46:52
Quote: Originally Posted by differ All this talk of solvers makes me want to create my own!
Also, Tilps: Naivoj's 2-only puzzles defeat your solver pretty handily. Or at least they seem to: your visual solver goes through the same pattern twice (unnecessarily?) and then decides just to brute force the whole thing. |
If Any progress is made on a pass (this includes edge pair restrictions which do not show up in the UI) it tries another pass just in case.
(Also, what looks like 2 passes is actually one pass. It first tries each edge, then it tries setting each cell's cell color. The latter does discover certain things that the former does not.)
I suspect brute force is occurring because my solver still doesn't have a good counting component. So an odd semi-diagonal of 2's means nothing to it.
This would be an advanced cell coloring which knows that in a diagonal sequence of 2's which are locked, the number of edge transitions is equal to the number of 2's. So despite not knowing the cell colors of any of the 2's, you can determine the cell color at the far side. I wonder if I can implement that generically...
Last edited by Tilps - 2009.11.24 22:00:07 |
Tilps
Kwon-Tom Obsessive
Puzzles: 6722
Best Total: 18m 37s | Posted - 2009.11.24 21:49:54
Quote: Originally Posted by v_e_e_n_c_a Interesting results to new Tilps puzzles posted - the harder one LDL 17 is solved by my solver in about 0,1 sec.. And the easier (as he said there were no trials (only the new feature) is only solved in about 90% (in the same time).. |
|
Tilps
Kwon-Tom Obsessive
Puzzles: 6722
Best Total: 18m 37s | Posted - 2009.11.24 21:58:38
veenca's new beast is a nasty one.
Took 25minutes for my latest (unreleased) LDL to verify it only has one solution.
I haven't checked whether nested guess or cell pair interaction logic within trials is able to solve it, but otherwise LDL had to resort to fully recursive trials for the last half of the puzzle.
I've had a look at the puzzle and I don't know how to solve it.
That all being said, I believe there is currently a bug in my program. I recently added a self-test option and it finds numerous 4x4 puzzles which can be generated by my most basic logic, but fail to be solved when I turn my more advanced logic on.
(Edit: found the bug, it only shows up when trying to solve the same puzzle with edge restrictions off, after having them on. Some dodgy caching... doesn't help for veenca's puzzle)
But if that isn't it, I suspect there are a few forms of logical attack which veenca has found which I've never heard of.
Last edited by Tilps - 2009.11.25 03:16:28 |
v_e_e_n_c_a
Kwon-Tom Obsessive
Puzzles: 2080
Best Total: 32m 53s | Posted - 2009.11.24 22:00:50
Quote: Originally Posted by tilps Quote: Originally Posted by v_e_e_n_c_a Interesting results to new Tilps puzzles posted - the harder one LDL 17 is solved by my solver in about 0,1 sec.. And the easier (as he said there were no trials (only the new feature) is only solved in about 90% (in the same time).. |
The new feature is quite powerful... I suspect that it and trials are only partially intersecting sets, there are some things trials cannot discover which cell pairs can. On the other hand there is a lot of stuff trials can discover that cell pairs cannot. |
If cell pairs could make as much as trials, then Slitherlink will not be NP complete.. |
Tilps
Kwon-Tom Obsessive
Puzzles: 6722
Best Total: 18m 37s | Posted - 2009.11.24 23:03:21
Actually, if simple trials could solve every puzzle, slitherlink would not be NP complete.
Trials is not the same as fully recursive brute force. I only ever use fully recursive brute force with the full generator. Trials are just 'local' contradiction detection, or deduction of common truth if no contradiction is found. |
Tilps
Kwon-Tom Obsessive
Puzzles: 6722
Best Total: 18m 37s | Posted - 2009.11.25 07:11:04
veenca beast is solvable with simultaneous trial of two locations rather than just one. In fact it could be done with a 'max trial range' of only 1, which suggests I am missing something pretty basic.
Based on some analysis of my solver, it appears that it is path deduction which results in solving important parts of the puzzle. One day I'll work out a cool algorithm for path deduction... one day...
Last edited by Tilps - 2009.11.25 10:04:17 |
pqg
Kwon-Tom Obsessive
Puzzles: 6385
Best Total: 15m 37s | Posted - 2009.11.25 16:34:45
Just solved veenca's latest beast - nice puzzle. Certainly tougher than any of the recent LDL set tilips posted, though maybe not as hard as some of the ones Mondsemmel generated with Tilips' program previously.
Last edited by pqg - 2009.11.25 16:35:47 |
v_e_e_n_c_a
Kwon-Tom Obsessive
Puzzles: 2080
Best Total: 32m 53s | Posted - 2009.11.26 21:15:38
Quote: Originally Posted by tilps But if that isn't it, I suspect there are a few forms of logical attack which veenca has found which I've never heard of. |
All techniques which I used in my program are from my head. I only took over some basic things - such as locks or shading. Probably the main thing and first success came with the new way how to deal with this techniques and with good interaction between all parts of my solver. But there are lot of new things based on this structure which I invented - such as another type of locks, advanced shading and two powerfull path deduction algorithms.. And some more.. |
Tilps
Kwon-Tom Obsessive
Puzzles: 6722
Best Total: 18m 37s | Posted - 2009.11.27 05:47:28
Yeah I am working on a path deduction system now, I'm just suffering from lazyness or it would be done already. |
Tilps
Kwon-Tom Obsessive
Puzzles: 6722
Best Total: 18m 37s | Posted - 2011.07.24 04:42:32
It has been a very long time - but I was inspired this weekend to have another go at the 'path deduction' problem.
I finally realized that the simple approach I had previously dismissed was both not practically-entirely-useless and also not incredibly-expensive as I had previously assumed it would be.
Some surprising results - despite the additional processing overhead of the new pass which 99% of the time is completely useless - I am getting some massive performance improvements on solving some of these 'really hard' old user beasts.
The most astonishing one is the Veenca beast which previously took 25 minutes. I've upgraded my computer since then, but it definitely wouldn't be twice as fast as before.
With the new pass in place, it takes 3 seconds! |
lodenkamper
Kwon-Tom Fan
Puzzles: 21
Best Total: 47m 58s | Posted - 2012.08.12 23:09:09
I'm thinking of generating some new user beasts soon, and it appears that the main way to increase their difficulty is to reduce the availability of highlander logic.
I believe I have an easy way to do this with my solver, and the following puzzles are relatively small test cases (20x14) to try this out. If anyone solves these test cases, please let me know whether or not highlanders were readily available.
Test#1
Test#2
Test#3
Test#4 |
Zyntax
Kwon-Tom Obsessive
Puzzles: 6534
Best Total: 13m 6s | Posted - 2012.08.13 01:04:29
Highlanders aside, these are going to be difficult to solve with only 1's and 2's. Even the last one with very few 3's is hard just by looking at it. |
