| making a list of rules |
ferkel
Kwon-Tom Obsessive
Puzzles: 536
Best Total: 39m 18s | Posted - 2008.02.09 00:33:55
Hello,
Take a look here:
http://slinker.googlecode.com/svn/trunk/solving_rules_3.txt
The first 13 are the elementary rules needed to capture the laws of slitherlink. I hope the file format is clear - it is intended to be both human and machine readable. Rules apply in rotated and reflected forms, of course.
Following that are 23 rules derived automatically, for up to 3 elements (digits or borders). The engine forbids small loops.
Generating these rules has turned out to be much harder than I thought. I'm still not sure that I've got them all. I'm not even sure what a rule is anymore - the ones we want to see are minimal in some sense, and non-redundant relative to the others. But how do we find the one true ruleset? (if there is such a thing) Are there any rules you would add to this list, for up to 3 elements?
Anyway, the source code is all there too:
http://code.google.com/p/slinker/source/browse/trunk/src/
but it's at a very early stage - I'll post again when it's easier to use.
tim / ferkel
Last edited by ferkel - 2008.02.09 00:40:08 |
Tilps
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | Posted - 2008.02.09 01:27:31
To be pedantic:
Specifying a precondition that there is a non-zero number outside of the test area should probably be notated, because half of the derived rules don't rely on the small loop restriction, while others do.
As an idea:
All rules after 13 should prehaps be a 3 step process rather than 2.
Step 1 shows the minimal configuration, step 2 shows the derived position using previous rules, step 3 shows the additional deductions. Its of interest because any position between step 1 and step 2 also goes all the way to step 3.
Possible start with step 2, and list known step 1's leading to step 2, then step 3
Last edited by Tilps - 2008.02.09 01:28:50 |
jasonharper
Kwon-Tom Obsessive
Puzzles: 1349
Best Total: 25m 18s | Posted - 2008.02.10 11:33:13
Three elements is clearly too restrictive - there are lots of useful, basic patterns that require more than that, such as==>
I gave up on a similar effort to enumerate all patterns when it became apparent that no finite set of patterns would capture the logic of the puzzle. In particular, any pattern that involves diagonally opposite corners of a 2 (like your rules 28-32, 35, and 36) still applies if the 2 is replaced by an arbitrarily long diagonal chain of 2s. Memorizing separate patterns for each possible chain length strikes me as being inelegant... |
foilman
Kwon-Tom Admin
Puzzles: 3614
Best Total: 24m 6s | Posted - 2008.02.10 12:58:06
The puzzle generator I wrote for this site has a whole section on "chains" where you can follow diagonal 2s etc from one point to another... it is very useful to handle those cases - a simple pattern match won't work. I originally did my puzzles almost entirely with simple patterns but those bits of code are gradually getting replaced by more generic algorithms.
I haven't worked on it in a couple of years now, so I can't remember too many specifics off the top of my head - other site updates are taking priority... |
Darklady
Kwon-Tom Obsessive
Puzzles: 5369
Best Total: 9m 37s | Posted - 2008.02.10 19:19:04
Hm... A program could easily follow chains if it keeps track of patterns where only things like "out of these two segments, one is a line and one is an x" can be determined. For example, this:
Leads to this:
Which leads to this:
And so on.
Keeping track of these sorts of patterns may be a bit tricky, but I'd think it would greatly simplify solving complicated areas.
Also, if your engine is going to have some way to avoid forming large loops which don't solve the puzzle, why do you need explicit patterns for the small loops? I'd think the large-loop-protection code would handle them automatically. |
Tilps
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | Posted - 2008.02.10 20:18:32
Regarding 3 elements being too restrictive.
I was thinking that crosses shouldn't count as elements, or should count as less elements then others.
But as an alternative which comparatively reduces the search space for a give number of elements but still increases usefulness. Rather than just having each scenario placed in an open field, additionally try the scenario near/against a single edge/corner.
Additionally, it might be interesting to extend the patern generator to detect 'derived numbers' as well as derived edges.
Regarding chains: they can (mostly) be done using 'same' or 'opposite' tracking, which are pieces of information which my program represents using edge coloring/dashing (or internaly using numbers/negative numbers called edge sets) It would be nice for a pattern generator to treat these as elements of information, but they are tricky to represent visually. |
ferkel
Kwon-Tom Obsessive
Puzzles: 536
Best Total: 39m 18s | Posted - 2008.02.10 21:50:31
Yes, 3 elements is too few to make good puzzles - I'm working on the list for 4 elements at the moment (there are quite a few of them...) I'm hoping that by making rulesets up to perhaps 5 elements we'll be able to make puzzles that are solvable by deduction but still hard. Also it's just a fun thing to try to do.
Last edited by ferkel - 2008.02.11 00:30:20 |
ferkel
Kwon-Tom Obsessive
Puzzles: 536
Best Total: 39m 18s | Posted - 2008.02.12 23:51:04
Here's the list of rules up to 4 elements:
http://code.google.com/p/slinker/source/browse/trunk/solving_rules_4.txt
(128 in total)
Several of these were completely new to me, and knowing them has improved my Kwon-Tom speed!
To clarify:
1) These rules assume that there is at least one non-zero digit beyond the shown area, hence local loops are forbidden. (thanks Tilps)
2) We don't consider rules that include the zero digit. There would be many of them, and none of them are very interesting - the rules with the equivalent crosses are more general.
3) We don't include implied elements that are covered by other rules. e.g. In rule #23 in this file, the 5 lines and 7 crosses that are implied by rules #15 and #16 are omitted.
Interestingly, 2 of the 3-element rules were removed by the program, as they had become redundant. Rules #23 and #25 (in the 3 rules file) were found to be less general than new rules #105 and #107 respectively. i.e. given all the other rules, #105 implied everything that rule #23 did, but not vice versa. Similarly for #107 and the old #25. (Sorry for the re-numbering confusion but I didn't anticipate needing to cross-reference like this!) The fact that rules can become redundant is a side-effect of wanting to see more than the fully minimal rules. Without this we'd have to wait until searching for rules with 16 elements before seeing rule #24, for example.
Making puzzles that are directly solvable with these 128 rules seems to make nice puzzles in the 'easy' category (for a given loop). User puzzle #297 is an example. Hopefully going to 5 elements will give us more difficult puzzles that are still guaranteed to be deducible...
tim / ferkel |
Jankonyex
Kwon-Tom Obsessive
Puzzles: 5680
Best Total: 9m 35s | Posted - 2008.02.13 08:46:57
patterns
Quote: a = "1" can be chanded into one "2" + one "line"
b = "3" can be changed into one "2" + one "cross"
c = "3" can be changed into one "line"
d = "3" can be extended to form "n2-3 diagonally"(n>0) and the new "3" with both b[2],c[2]
[m] = "m possibilities" |
|
jamin
Kwon-Tom Obsessive
Puzzles: 1233
Best Total: 27m 9s | Posted - 2008.02.17 04:17:46
Thanks ferkel,
The 4 rules file had quite a few patterns that I'd not considered to be generalisable (and a few I'd previously worked out myself but forgotten).
It is great to have an organised catalogue of patterns. |
ferkel
Kwon-Tom Obsessive
Puzzles: 536
Best Total: 39m 18s | Posted - 2008.02.25 00:05:56
Slinker has a 0.1 release now. Screenshots and cross-platform downloads here:
http://code.google.com/p/slinker/
There's lots of work to do, but it allows you to generate puzzles with different rulesets and shapes. It can offer hints when you get stuck, showing a rule that can apply. |
ferkel
Kwon-Tom Obsessive
Puzzles: 536
Best Total: 39m 18s | Posted - 2008.02.25 22:56:08
If you were having problems running Slinker on Windows, please download the 0.1.1 release which should work on more systems.
For a quick demo of how Slinker makes its loops, whatever the shape of the grid, hit "Demonstrate the growth rules" on the "Analysis" menu. It shows how the three growth rules in growth_rules.txt when applied at random cause loops to wiggle around and grow.
I'd be interested to know how other programs make their loops. If I'm understanding it correctly, Loopy adds clues at the same time as growing its loop, which is an interesting approach. See: add_full_clues() |
Tilps
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | Posted - 2008.02.26 00:27:38
LoopDeLoop generates its loops by
a) choose a random position and direction.
b) fill that line.
c) choose a random line connected to the end of that line which satisfies the connectability constraint and the no-join constraint and the no-too-short loop constraint.
d) if c) found a line, fill that line and go back to c) unless the loop is closed.
e) if loop is not closed, clear grid and go back to a)
f) Fill every cell with numbers basedon the loop.
g) Prove puzzle is solvable using the target solver - if not, clear grid and go back to a)
The connectability constraint is that if you perform a flood fill starting at the intersection chosen at random at the beginning, the intersection the line we are considering is going to reach to (putting the line in before the flood fill), is filled.
The no-join constraint is implemented by everytime a line is added, the crosses are added at the intersection, and you never attempt to put a line where a cross already is. (Alternatively it could be done by simply checking to see that if the loop has been closed, it was closed by joining to the starting intersection.)
The no-short loop constraint is that the current count of the number of edges placed must be greater than some fraction of the total number of intersections or a line which closes the loop will not be considered.
I ship with a fraction equal to 0.5 - which always succeeds in a short period, but the loops are quite often a bit boring - lots of 0's.
I find that upto 0.8 almost always succeeds in small enough number of tries, and the puzzles are pretty good - I've been meaning to increase my default but I keep forgetting. (Its a configuration setting)
Arround about 0.9 I start to hit my 'maximum number of attempts' cutout too often, which results in it taking the next loop regardless of length so the results are very variable.
(Edited, I thought it was total edges/3 that I used as the basis for line length fraction, but its actually the more optimal intersection count - which makes why 0.9 fails so often more understandable.)
Last edited by Tilps - 2008.02.26 04:26:44 |
Tilps
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | Posted - 2008.02.27 22:51:03
I had a sudden inspiration based off the growth rules.txt which has allowed me to improve the generation times of my solver by a moderate amount.
A large amount of the time spent generating a puzzle is spent verifying puzzles which the solver cannot solve. In the really time consuming cases, this is usually not just because its too hard for the current solver difficulty level, but because it is actually unsolvable.
Growth rules can be reformulated as 'for any given cell if one or more edges are filled, and all such edges form a contiguous line around the border of the cell, then the loop can be modified by switching the filled and unfilled edges.'
With this definition in hand, I now look at every cell of a completed loop that I have decided to use and ask it whether the growth rule could be applied to that cell. Then before each step in the generation process attempts to remove a cells target number, I enumerate all cells which were growth rule candidate. For each of the se cells I collect its immediate neighbours which still have target numbers. If I collect no cells, then I mark the growth rule candidate as protected. If I collect only one cell and the growth rule candidate is empty or has a target number exactly half the count of its edges, then I mark the collected cell as protected. If the current candidate for removing the target number is marked protected, I skip it. (Yes I realise this can be optimised to only consider growth rule candidates which are either the candidate for removal or its immediate neighbours - not a performance critical path and this was faster to write this morning).
I call it the reverse highlander generation system.
Last edited by Tilps - 2008.02.27 22:53:11 |
v_e_e_n_c_a
Kwon-Tom Obsessive
Puzzles: 2080
Best Total: 32m 53s | Posted - 2008.08.31 18:55:16
I hope that this question belongs to this topic.. I am working on solver and generator. Consider that you have created a loop - no matter how it was created. And for example the loop looks like this:
So the clues are:
But no matter what clues are shown - it will results in multiple solutions.. Second solution is:
The question is how your solvers deals with this? Are you seeking for all solutions (or at least find two solutions) and then cancel this configuration.. Or there exists some heuristics which can recognize that this clue configuration can not have unique solution? Thanks for your observes. |
ferkel
Kwon-Tom Obsessive
Puzzles: 536
Best Total: 39m 18s | Posted - 2008.08.31 19:34:11
Hi veenca,
Any puzzle that has a diagonal full of 2's will have two solutions, I think. I've never seen any other examples though - I would love to know if they exist. Maybe we should search for them.
Ferkel |
MondSemmel
Kwon-Tom Obsessive
Puzzles: 6159
Best Total: 7m 47s | Posted - 2008.08.31 19:47:58
Quote: Originally Posted by ferkel Hi veenca,
Any puzzle that has a diagonal full of 2's will have two solutions, I think. I've never seen any other examples though - I would love to know if they exist. Maybe we should search for them.
Ferkel |
?
All puzzles without verified uniqueness can very possibly have multiple solutions e.g. in places where you'd normally be able to apply a highlander pattern.
The most basic case for a generated puzzle with multiple solutions would probably be something like:
And what about something like this? (Adapted from one of the puzzles in the user archives)
|
v_e_e_n_c_a
Kwon-Tom Obsessive
Puzzles: 2080
Best Total: 32m 53s | Posted - 2008.08.31 20:15:38
I don't think that only puzzles with one diagonal filled with 2's have multiple solutions. But how to recognize these cases. Puzzles with highlander rules and the last puzzle shown there can have unique solution - it is only question of adding one or more clues (1 in the last puzzle should be enought - in right place) But with the puzzle I have shown here - it is not only question of clues - even with all clues supplied - it have two solutions. Do you search for another solution before you declare the puzzle to be unique? |
Tilps
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | Posted - 2008.08.31 20:33:32
If at any time my solver proves there is more than one solution, it returns a failure. It doesn't stop at the first solution it finds, unless it has proven it is the only one. (Proving that the solution found is the only solution, without searching, happens a decent amount.) |
v_e_e_n_c_a
Kwon-Tom Obsessive
Puzzles: 2080
Best Total: 32m 53s | Posted - 2008.08.31 21:06:03
But if i solve puzzle only by deduction - i mean pattern rules, color deduction, locked/antilocked edges, local deduction (by contradiction) and so on - then i should declare that the puzzle is unique - am i right? so only if i am trying some possibilities, then i have to try all of them to ensure the uniqueness.. is that true? |
