| Discussions on User Beast Puzzles | lodenkamper
Kwon-Tom Fan
Puzzles: 21
Best Total: 47m 58s | Posted - 2008.06.12 00:27:54
Thanks for user beasts 70-73. I can confirm that the solutions for these are unique, according to my solver.
Naivoj - Are the solving times you've posted for the user beasts
a) the time to solve and verify uniqueness, or
b) the time to solve without verifying uniqueness? | pqg
Kwon-Tom Obsessive
Puzzles: 6385
Best Total: 15m 37s | Posted - 2008.06.12 23:33:18
Finished #73, so I don't think it's too tough for human solvers. Naivoj, what did you mean by your comment that "you can't rely on highlander deductions"? True, there aren't many simple highlander rules to be applied, but highlander principles can be used in combination with trial and error extensively.
Last edited by pqg - 2008.06.12 23:35:01 | MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s | Posted - 2008.06.12 23:56:55
Quote: Originally Posted by pqg Finished #73, so I don't think it's too tough for human solvers. Naivoj, what did you mean by your comment that "you can't rely on highlander deductions"? True, there aren't many simple highlander rules to be applied, but highlander principles can be used in combination with trial and error extensively. |
I'm quite sure that what he meant was that as long as the uniqueness of the puzzle wasn't confirmed (#5 had 2 solutions, but I didn't notice that, either), highlander deductions might or might not work. If a puzzle has 2 solutions and you apply a highlander deduction to this puzzle, you might get 0 solutions instead, i.e. have a wrong conclusion.
I've now finished all puzzles except for #72 (made a mistake somewhere...I'll probably have to do it again^^) and #73 (I found it fascinating that the left third of the puzzle was more or less forced, so the parts that make this puzzle difficult are basically all located on the right two thirds of the puzzle.) I guess the diagonal cluster in the center of the puzzle (which contains lots of 1s and 2s) is part of what makes this puzzle so difficult - for humans and/or computers. Or not - I haven't solved it yet. | Naivoj
Kwon-Tom Addict
Puzzles: 314
Best Total: 33m 50s | Posted - 2008.06.13 07:15:19
Quote: Originally Posted by lodenkamper ...Naivoj - Are the solving times you've posted for the user beasts a) ... b) ... |
Now up to now I only ran our uniqueness test normally with a CPU time of 11m 10s.
After I read your note I ran it for the first time from the reverse string and it requires an unexpected 9h 16m 22s !
So the solving times of our solver for #73 on an X86 Intel 2.2 GHz processor are:
- Solving without verifying uniqueness: 7m 47s; Reverse: 0h 12m 57s
- Solving verifying uniqueness: 11m 10s; Reverse: 9h 16m 22s | Naivoj
Kwon-Tom Addict
Puzzles: 314
Best Total: 33m 50s | Posted - 2008.06.13 08:01:39
Everybody knows you are out there, many of us now see you at night in the sky. What I want to know is how much time it takes you guys (Pqg and MondSemmel) to travel to the earth?
I am a simple mortal earth being and when trying to manually solve #73 (without computer assistance), I get the first 12-13 columns and a lot on wide perimeter areas, but a very large center section remain blank. Once I stick with an exploration which brought me to like 90% completed only to reach a dead-end. Another time I tough I was making significant progress with many forced lines, so just to make sure I used our solver to validate my position, to found out it was a wrong one (my fault obviously). At the point I have reached I found it very hard to get conclusive explorations. The trick is probably, what I always have difficulty to do, to keep an exploration that looks good.
Quote: Originally Posted by pqg .. Naivoj, what did you mean by your comment that "you can't rely on highlander deductions"? ... |
Would you both agree anyhow that #73 is the hardest beast ever posted? If not which one is?
Too bad user beasts can not be posted in the regular user puzzle page, so we know how many solve #73. So to address this, I am starting a new club (which I will not join soon).
Last edited by Naivoj - 2008.06.13 08:04:04 | pqg
Kwon-Tom Obsessive
Puzzles: 6385
Best Total: 15m 37s | Posted - 2008.06.13 09:30:05
OK, I see what you meant now - have to admit if I'd understood at the time that the puzzle's creator wasn't convinced of it's uniqueness, I don't think I'd have bothered trying it!
While there are few recognised highlander patterns applicable, general highlander principles are useful. EG: If you have isolated a subsection of a puzzle which has 4 line endings entering it (name them A,B,C and D clockwise from any point), then you can use T&E to find solution(s). If there are 2 possible ways to complete the section with A connecting to B and C to D then Highlander tells you that A must connect with D (it can't join C because that would block B and D from each other). You can extend this kind of reasoning to sections with more entering lines (I used it with 6 and even 8 on quite large subsections of #73) and, most usefully, on sections that are not completely isolated - provided you confirm that the 2 solutions leave the same interface with unsolved areas.
My solved time for #73 was around 17h, but that's because I left it overnight, and was doing some other things on and off while completing it the next day - I'd guess I was actually working on it for well under half that - maybe 6-7h? BTW, I have never used colouring, just parity counting.
Incidentally, my time would have been much quicker had I gone with my hunches earlier - I had ideas for what were the most likely solutions for 3 or 4 big sections and was almost disappointed to find they were all correct (the difficulty of this puzzle having been hyped up, meant I was expecting a less intuitive solution) - usually it was a case of "well, this line forces a solution for the whole area - without it, my impression are that multiple solutions will be possible, but it's going to take a lot of work to prove they're equivalent" Because I don't normally like to test more than one assumption at a time (is that what you meant by no recursion?) I spent a lot of time plugging away at doing that work, when if I'd gone with intuition I'd have got there much faster. (Note that's not blind intuition, but the product of many non-rigorous T&E explorations)
Although I haven't done all your user beasts (done ~10 of them, including #18 ), I have done everything in the archives (including user puzzles and BotMs). It's not easy to evaluate which is the most difficult, though #73 was certainly one of the toughest. When you take into account the skewing effect whereby puzzles done more recently seem easier than ones I struggled over a while back (because I'm a better solver than I used to be), it makes a strong case for being the most difficult, but I don't think its difficulty is such an order of magnitude above everything else as your solver stats suggest.
PS I too would like if beasts could be posted in the user puzzles section, or failing that, if there was some way you could keep track of which ones you've done. (that applies to BotM as well as user beasts)
Last edited by pqg - 2008.06.13 09:51:18 | Naivoj
Kwon-Tom Addict
Puzzles: 314
Best Total: 33m 50s | Posted - 2008.06.22 08:37:42
Quote: Originally Posted by pqg ...While there are few recognized highlander patterns applicable, general highlander principles are useful. EG: If you have isolated a subsection of a puzzle which has 4 line endings entering it (name them A,B,C and D clockwise from any point), ...) |
6 Lines + 4 Crosses
It's like an extended basic highlander 2.
Pqg could you please post one or 2 of these recognized highlander patterns?
As there are not a lot of white spaces they must be large size patterns like the one I just post.
I try to apply your isolated subsection highlander technique without success. But I believe it is good as you solve #73 with it. I don't know how you can apply it in a large section as the portion tower the center of the puzzle remain unsolved (unless you are really advanced).
About posting in the ET club? As this is not a competitive puzzle, only the (approximate) active solved time should count: time between session doesn't matter.
Quote: Originally Posted by pqg ...(the difficulty of this puzzle having been hyped up, meant I was expecting a less intuitive solution) ... Because I don't normally like to test more than one assumption at a time (is that what you meant by no recursion?) I spent a lot of time plugging away at doing that work, when if I'd gone with intuition I'd have got there much faster. (Note that's not blind intuition, but the product of many non-rigorous T&E explorations) ...) |
- Yes one recursion level means you do not start a new exploration until the current one is completed.
- I will be posting another beast #88, which requires 2 recursion levels to our solver.
Last edited by Naivoj - 2008.06.24 09:34:30 | MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s | Posted - 2008.06.22 13:46:09
I've finally solved #73 (after not doing anything with it for over a week). It's definitely among the most difficulty puzzles you've posted, but I'm also not sure whether it's really the most difficult one.
You were right about the total absence of trivial highlander patterns, but obviously more advanced highlander deductions were still applicable.
I've posted a longer post in your E.T. thread, too, although I'm sorry to say that I don't know my solving time.
I've now solved all your beast puzzles (#1 to #73) again  - could you post some more?^^
I appreciate the very difficult ones, too, but I generally enjoy every puzzle you post, no matter whether its difficulty is easy or very hard  .
Last edited by MondSemmel - 2008.06.22 13:47:18 | pqg
Kwon-Tom Obsessive
Puzzles: 6385
Best Total: 15m 37s | Posted - 2008.06.22 14:03:46
Quote: Originally Posted by naivoj Pqg could you please post one or 2 of these recognized highlander patterns? |
When it comes to collecting patterns, I think there comes a point when the number and size of the patterns makes it counterproductive to memorise and use them all - it becomes more efficient to simply make the same deductions from first principles (T&E if necessary, or more usually just in your head) each time. Where this point arrives will vary from solver to solver depending on solving style and memory - I suspect humans will reach it much sooner than automated solvers. Personally, it's been passed some time ago; there's already far more patterns documented in the forum than I find it worthwhile to remember - I don't use any with more than 3 numbers, except for those potentially infinite diagonal chains of 2's)
Ultimately, the subsection idea I outlined earlier is no more than a generalisation of the highlander principle - eliminating options which lead to multiple possible solutions. I should perhaps have emphasised more that it can be applied to any area - whether or not it's isolated - provided you ensure that the 2 similar solutions leave the same 'edge' with unsolved areas, and it's in this form that I used it extensively in #73. (If you discount the relatively more straightforward left hand third of the puzzle and divide the rest into quarters, the top right is the easiest, and I did it in 2 or 3 sections, followed by the bottom right which had to be tackled as a whole) | Jankonyex
Kwon-Tom Obsessive
Puzzles: 5680
Best Total: 9m 35s | Posted - 2008.06.23 10:13:20
User Beast #073- Solution:
here
Last edited by Jankonyex - 2008.06.23 16:43:38 | astrokath
Kwon-Tom Obsessive
Puzzles: 3258
Best Total: 13m 42s | Posted - 2008.06.23 14:59:46
That solution looks good to me so far.
Interestingly, you've ruled out some areas that I couldn't for ages, but left others that I found quite easy. | MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s | Posted - 2008.07.05 22:47:59
Was the stuff I posted in the #73 puzzle thread useful?
Naivoj, will you post a few more user beasts soon? I'm currently doing lots of them for a second time due to lack of new ones^^.
It's interesting how much easier all puzzles become if you know them already; it almost doesn't matter if you haven't seen the specific puzzle for a month or more - I still remember the difficult sections and solve the rest first, etc., and a few types of deductions (e.g. bigger highlander deductions) are quite memorable, as well.
Last edited by MondSemmel - 2008.07.05 23:08:10 | Naivoj
Kwon-Tom Addict
Puzzles: 314
Best Total: 33m 50s | Posted - 2008.07.06 07:38:50
Quote: Originally Posted by mondsemmel ... Naivoj, will you post a few more user beasts soon? ... |
Last edited by Naivoj - 2008.07.06 07:39:06 | MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s | Posted - 2008.07.06 19:22:24
Quote: Originally Posted by naivoj Quote: Originally Posted by mondsemmel ... Naivoj, will you post a few more user beasts soon? ... |
I will soon, but you got to tell us which star you're coming from, once you solve upcoming #88. >-) >-) >-) >-) |
I'm looking forward to the next batch!
I don't think there are any truly unsolveable puzzles in Slither Link. After all, as soon as you deduct a cross or a line, it will stay there, making the rest of the puzzle a bit easier/bringing you one step closer to the solution.
One might want to give up if the difficulty is too high, or perhaps one makes a mistake (which is the worst thing that could happen, as it makes one lose both time and, more importantly, confidence), but except for that, even if you solve the puzzle one line/cross at a time, you will arrive at the solution in the end, no matter how long it takes.
That's why I like this website - it's mainly about finding a solution efficiently, not just about finding a solution. And if it's about efficience, I still have a long way to go^^.
EDIT: Although I'd capitulate at any Slither Link puzzles bigger than the beasts - not only does the time consumption increase exponentially, but they would also be bigger than my screen...
Last edited by MondSemmel - 2008.07.06 19:25:12 | Naivoj
Kwon-Tom Addict
Puzzles: 314
Best Total: 33m 50s | Posted - 2008.07.07 06:47:47
Hello Lodenkamper,
Could you please validate #74-#88.
It is good for the users of this site to have another source corroborating the uniqueness of these beasts.
In case you missed it, I did reply (close to the top of current page at 2008.06.13 03:15:19) to your last post regarding the solving times of our computer program. I will like to know what are the CPU times of your program for #73 (including the reverse string). | lodenkamper
Kwon-Tom Fan
Puzzles: 21
Best Total: 47m 58s | Posted - 2008.07.08 01:44:13
Quote: Originally Posted by naivoj Hello Lodenkamper,
Could you please validate #74-#88.
It is good for the users of this site to have another source corroborating the uniqueness of these beasts.
In case you missed it, I did reply (close to the top of current page at 2008.06.13 03:15:19) to your last post regarding the solving times of our computer program. I will like to know what are the CPU times of your program for #73 (including the reverse string). |
I can confirm that #74-#88 all have unique solutions according to my solver.
I did see your earlier reply regarding timings. I've been a bit distracted lately, but I should be able to pull some timing results together in the next few days. | lodenkamper
Kwon-Tom Fan
Puzzles: 21
Best Total: 47m 58s | Posted - 2008.07.08 07:48:07
puzzle P1_time N P2_time
73rev 10.1s 679 2.5s
73 10.0s 679 3.0s
74 10.0s 961 4.1s
75 4.9s 333 1.3s
76 8.1s 790 4.3s
77 8.3s 625 3.4s
78 5.9s 480 1.6s
79 5.7s 277 0.7s
80 3.3s 375 1.1s
81 2.1s 232 0.6s
82 4.8s 596 1.3s
83 2.9s 201 0.5s
84 3.6s 154 0.5s
85 1.9s 266 0.7s
86 5.8s 570 1.9s
87 10.0s 739 2.5s
88rev 18.3s 1204 8.3s
88 18.8s 1204 8.0s
puzzle = user beast # (#rev is the reversed version of the puzzle)
P1_time is the time for solver first pass (deductions only, no backtracking)
N is the number of unknowns remaining after first pass
P2_time is the time for solver second pass (deductions + backtracking search)
Total solve time is P1_time + P2_time. | lodenkamper
Kwon-Tom Fan
Puzzles: 21
Best Total: 47m 58s | Posted - 2008.07.08 08:24:34
A few comments to follow up on my previous post of timing results:
1) In general, the user beasts are much harder for my solver than the regular beasts of the month. For example, the hardest monthly beast for my solver is Feb 08 (P1_time = 4.0s, N = 295, P2_time = 0.8s). These numbers are comparable to the easier user beasts (e.g., user beast #84).
2) Relative difficulty correlates well (but not perfectly) with puzzle rating. Of this set of timings, #88 is clearly the most difficult puzzle by a large margin. Other user beasts comparable to or more difficult than #88 for my solver are numbers: 4, 9, 17, 18, 38, 41, 42, 47, 49, 61, and 69.
3) All times given are times to find a solution and verify uniqueness.
4) My solver makes no use of highlander deductions or patterns, so puzzles which are made relatively easy by such methods may be relatively hard for my solver.
5) Results are not affected by puzzle reversal. This is as expected, because the guesses for backtracking search are not selected in a systematic order. Instead, activity based heuristics (e.g., as in a SAT solver) are employed to select the guess variables. | Naivoj
Kwon-Tom Addict
Puzzles: 314
Best Total: 33m 50s | Posted - 2008.07.10 10:16:18
Thanks LodenKamper for validating #74-88.
I get distracted all the time too, and often have no time to come here.
Your solving times are just amazing compare to our solver. For #88 you are about 50 times faster! The best our solver can do is 3m 7s for #88rev by using a special setting where only basic rules and basic patterns are applied and where it goes in high level of regressions ASAP. In this latest case you "only" are 7 times faster.
- We found out that employing many rules & patterns actually slow down the program when using high level of recursions
- Our normal setting is to use all rules and patterns and minimum level of recursion (but numerous passes):
- 1 level of recursion for #73; 2 levels for #88;
Of course highlander patterns can not be used when verifying uniqueness, but our solver uses them otherwise as it's trying to simulate human solving. #18(150), #69(91), #41(1,69), #31(50), #64(49) and #61(38 ) are the user beasts with most highlander patterns applied by our solver.
- Note that our solver can not make highlander deductions, it can only apply highlander patterns
Some solver stats for the more difficult beasts you mentioned (#recursive.level, #highlander.patterns):
- #4(1,10), #9(0,22), #17(1,14), #18(1,150), #38(0,7), #41(1,69), #42(0,2), #47(0,10), #49(1,16), #61(1,38) and 69(1,91).
- 4 of the 6 puzzles with most highlander patterns are in your list! | MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s | Posted - 2008.10.20 14:25:51
Hey - I was wondering (once again - my hunger for user beasts is apparently insatiable^^) whether anybody would be so kind as to either post some more user beasts or point me to programs capable of generating equally difficult beasts which are proven to have only one solution .
Sadly, I have no programming knowledge, and I haven't had any luck whatsoever in convincing one of my friends (who does have said knowledge) to try out Slither Link...
I completely understand that those of you with the best puzzle generators probably won't want to post said programs (creating them must be a lot of work, after all), but if you could post some more beasts, I'd be very happy =). |
|
