| Solver algorithm | koyan
Kwon-Tom Fan
Puzzles: 21 | Posted - 2014.04.12 09:53:24
So, I have been working the last period on a solver algorithm.
It is work in progress (aka, I am trying constantly to improve it, both in the logic and the visual aspect), but you can see the current version at:
http://www.kokkorogiannis.gr/slitherlink/
Each step of the process is visible at:
http://www.kokkorogiannis.gr/slitherlink/?showdos=1
And at this one it tries to solve a hard 20x20
http://www.kokkorogiannis.gr/slitherlink/?preset=11
On the above link you can see the state it arrives without trying brute force.
With brute force enabled you can see it at:
http://www.kokkorogiannis.gr/slitherlink/index.php?brute=1&preset=11
(You will have to wait for the page to load, as it takes a minute or so...)
Questions:
1) do you know any other solvers out there? I would like to benchmark my algorithm against them at a later point
2) Does anyone of you have any puzzles in some kind of machine readable format? (So that then I will write a converter, and convert them to my own format, and test the algorithm against them).
Opinions and critisisms (even if they are cruel) are welcome
(note: the task I put to myself was if I could write an algorithm that would solve the puzzles without reading other peoples algorithms first). | v_e_e_n_c_a
Kwon-Tom Obsessive
Puzzles: 2080
Best Total: 32m 53s | Posted - 2014.04.13 06:53:10
Quote: Originally Posted by koyan Questions:
1) do you know any other solvers out there? I would like to benchmark my algorithm against them at a later point
2) Does anyone of you have any puzzles in some kind of machine readable format? (So that then I will write a converter, and convert them to my own format, and test the algorithm against them).
|
Ad 1) Yes, I wrote a solver years ago. I tried to solve your puzzle and it is fully solved nearly immediately - just few ms - no brute force used.
Ad 2) The well known format has this structure:
[width]x[height]:[clues]
where clues is a sequence of numbers and letters like this
which is 3x3
then first row can be encoded as 1b
second row a23
third row c
letters mean how many empty subsequent fields are there (a = 1, b = 2, c = 3, d = 4, etc)
So this puzzle will be 3x3:1ba23c, which can be simplified as 3x3:1c23c
The puzzle provided by you has this encoded form (which can be simplified):
20x20:c23a2a121a32c233c02d3g21ab31b3b13a3a3a2a12b22e1d1a2cc1a2a213131d2a13a3b13f22a3b3d2b1230b13b1a2b1b1a2c2b2b1a2222c3b3b32b3a2a32a2a1c3b2b3a21aa223g2a1122a3233a21b3a3f2a12a1a2a2a1a12122b1ca231d322a33c3ba1a1b32a1a1b2a2b22a21b2a3d21b32aa201223b2d1d32h2d112b3c2a33a2b23b2a1a2a222a1c02e3b0 | koyan
Kwon-Tom Fan
Puzzles: 21 | Posted - 2014.04.13 14:30:44
Quote: Originally Posted by v_e_e_n_c_a
Ad 1) Yes, I wrote a solver years ago. I tried to solve your puzzle and it is fully solved nearly immediately - just few ms - no brute force used.
|
Aparently I can improve it a lot.
What do you define as brute force in this case?
The function I have defined as brute force I would describe as following:
"For any line that is not marked, mark it and see if it leads you to an impossible situation".
Because I wrote the whole algorithm in php (well, real programmers are having heart attacks when they read this phrase, but we work with what we have), even this function takes a lot of time, so this is what I consider as "brute force".
Do you already use this in your solver?
Quote: Originally Posted by v_e_e_n_c_a
Ad 2) The well known format has this structure:
[width]x[height]:[clues]
where clues is a sequence of numbers and letters like this
|
Any idea where I can find some puzzles in this format? Of varying difficulties.
I will then write a small script to convert them to the array of arrays that I am using.
Thank you!
Konstantinos | v_e_e_n_c_a
Kwon-Tom Obsessive
Puzzles: 2080
Best Total: 32m 53s | Posted - 2014.04.13 14:49:09
Quote: Originally Posted by koyan Thank you! Aparently I can improve it a lot. What do you define as brute force in this case? The function I have defined as brute force I would describe as following: "For any line that is not marked, mark it and see if it leads you to an impossible situation". Because I wrote the whole algorithm in php (well, real programmers are having heart attacks when they read this phrase, but we work with what we have), even this function takes a lot of time, so this is what I consider as "brute force". Do you already use this in your solver? |
No, I did not use any trial and error, only rules for deduction and other general (shading, do not closing loop too early, locks etc.) and own methods. So it has polynomial time complexity. I wrote it in C#.
Quote: Originally Posted by koyan
Any idea where I can find some puzzles in this format? Of varying difficulties.
I will then write a small script to convert them to the array of arrays that I am using.
|
It is called Loopy format and you can find a lot of puzzles in this format here on this forum. You can get also beast puzzle in this format. Eg. this month beast - look at http://kwontomloop.com/beast.php?ym=201404 and Loopy format.
Last edited by v_e_e_n_c_a - 2014.04.13 14:51:08 | koyan
Kwon-Tom Fan
Puzzles: 21 | Posted - 2014.04.13 15:52:22
Quote: Originally Posted by v_e_e_n_c_a Quote: Originally Posted by koyan
Do you already use this in your solver?
|
No, I did not use any trial and error, only rules for deduction and other general (shading, do not closing loop too early, locks etc.) and own methods. So it has polynomial time complexity. I wrote it in C#. |
hmm, then I am missing some rules there.
General question (to whoever does not mind sharing their secrets): At this stage:
http://www.kokkorogiannis.gr/slitherlink/index.php?preset=11
what rules have I missed?
Quote: Originally Posted by koyan
Any idea where I can find some puzzles in this format? Of varying difficulties.
I will then write a small script to convert them to the array of arrays that I am using.
|
It is called Loopy format and you can find a lot of puzzles in this format here on this forum. You can get also beast puzzle in this format. Eg. this month beast - look at http://kwontomloop.com/beast.php?ym=201404 and Loopy format.
Thanks.
Homework for my next weekend then. Create a converter for the Loopy format.
BTW: the new version (which was my ultimate goal), is now live:
http://www.kokkorogiannis.gr/slitherlink/index2.php
(I wanted not only a solver, but a pure html (no java, no flash) page that would show each step of the solution process).
Comments and critique are welcome. | Tilps
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | Posted - 2014.04.14 00:32:10
Trial and error has polynomial time complexity if you don't do unbounded nesting of trials.
There are many categories of things a solver can do, I vaguely classify them like so.
1) Direct application of the game rules - count of lines at an intersection, count of lines around a square, trivial loop closing too early detection.
2) Pattern matching - this specific combination of numbers, lines, crosses leads to these specific additional results. (My solver doesn't use any of this directly, because they are difficult to generalize to arbitrary graphs that I support. Although equivalent progress can often be made by my 'cell pairs' logic.)
3) Derived properties - metadata about edges or squares which can be acquired through various means, and can provide additional logical progression, either just due to direct logical interaction with the puzzle rules, or interactions with each other or in combination with trials. Examples include 'shading', 'two edges are the same', 'two edges are opposites', 'two edges are not both lines', 'two edges are not both crosses'...
4) Common consequences. Consider the super-position of consequences that come from setting an edge to a cross, or the same edge to a line. Anything in common must be true. I separate this from standard trial and error because unless the common consequences are highly localized compared to the edge being considered people generally don't do this much.
5) Basic trial and error. Try setting an edge to a cross or an edge to a line, if one leads to a violation of the game rules, the other must be true. Usually repeated for every edge until progress stops.
6) Nested trial and error. This considers trials within trials, to some fixed depth and uses logic like if both sides of a nested trial fail, the parent trial is failed, or otherwise the common consequences might be increased. Nested trials are often limited to a subset of all possible trial locations because of the extreme cost.
7) Recursive trial and error. In this case, rather than considering each possible edge for a trial, you always only consider the 'next available edge', until the board is filled or a contradiction is found. Backtracking from each dead end and trying the next opposite trial until everything has been considered. This approach can be written very simply, and is guaranteed to solve all puzzles and can even often solve them very quickly if written with the right amount of logic built-in - but because it is very far from how people solve puzzles, it can be difficult to be used as a method of judging puzzle difficulty.
8 ) Local brute force. My 'cell pairs' step considers every pair of neighbouring squares and tries ever possible combination of edges on/off to derive metadata, or simple patterns that would otherwise require trial and error or hard coding. This is exponential cost in the number of edges involved - but for the classic square grid this is only 7.
My solver powers LoopDeLoop - browser version written using the Silverlight plugin is here - http://www.themissingdocs.net/LoopDeLoop.html
The more complete windows .Net application is here - http://www.themissingdocs.net/downloads/LoopDeLoop.exe | Nis
Kwon-Tom Obsessive
Puzzles: 2208
Best Total: 22m 1s | Posted - 2014.04.15 20:53:19
Quote: Originally Posted by koyan
hmm, then I am missing some rules there.
General question (to whoever does not mind sharing their secrets): At this stage:
http://www.kokkorogiannis.gr/slitherlink/index.php?preset=11
what rules have I missed?
|
You have this position, with the 2 and ? being the same colour:
Rules need to be formulated that allows you to solve this pattern | Authority
Kwon-Tom Obsessive
Puzzles: 3329
Best Total: 9m 56s | Posted - 2014.04.16 17:13:29
Quote: Originally Posted by koyan
1) do you know any other solvers out there? I would like to benchmark my algorithm against them at a later point
|
I have an online solver here: Slitherlink Solver/Generator. There's some of my handmade puzzles there as well which should be good for your testing purposes. An XML file of those is here. They have a different feel than computer-generated ones. The solver started off as javascript (using the DOM to hold the puzzle state, man that was slow), then I used php, then java, now it's back to javascript and a lot faster, but still pretty slow, and missing a lot of stuff (like cell coloring). As it stands it only does numbers 1 and 2 of tilps' list.
Client-side languages are better for this sort of web-based thing; web hosts don't like long-running or too-numerous php processes.
Your solver looks good, it reminds of me of my older versions which used a similar HTML-table display, but is already in advance of mine. I had the same findings as you: brute force is a total speed-killer. But it is the easiest thing to code for the solving of difficult puzzles. | koyan
Kwon-Tom Fan
Puzzles: 21 | Posted - 2015.07.23 15:49:55
So, a year later I remembered this small personal project again
I have made a new version of the solver.
Improvements:
1) I am using objects heavily. Each box tries to solve itself, each point as well. Things seem to be moving much faster than before
2) It takes as input the LOOPY format (Right now I only have put it a few ones in there).
3) After it does the steps I have programmed it, if it is not solved, it does a trial an error.
Still it seems to be faster than the previous one (better thought algorithm)
You can see it at: http://www.kokkorogiannis.gr/slitherlink/v2/index.php?preset=12
and http://www.kokkorogiannis.gr/slitherlink/v2/index.php?preset=11
Question:
On the second board there, (right after the point it says "After 4 levels of clues "), is there any clue that I am forgetting? I am wondering how you solve it without trial and error. | Darklady
Kwon-Tom Obsessive
Puzzles: 5369
Best Total: 9m 37s | Posted - 2015.07.23 18:09:01
Quote: Originally Posted by koyan Question:
On the second board there, (right after the point it says "After 4 levels of clues "), is there any clue that I am forgetting? I am wondering how you solve it without trial and error. |
In the upper-left corner, the inside of the loop has to pass between the two 3s. When you look at how "color" spreads, 3s are always dead ends, so there's no other possible route. | koyan
Kwon-Tom Fan
Puzzles: 21 | Posted - 2015.07.24 06:29:31
Quote: Originally Posted by Darklady Quote: Originally Posted by koyan Question:
On the second board there, (right after the point it says "After 4 levels of clues "), is there any clue that I am forgetting? I am wondering how you solve it without trial and error. |
In the upper-left corner, the inside of the loop has to pass between the two 3s. When you look at how "color" spreads, 3s are always dead ends, so there's no other possible route. |
Yes, and this is how I would solve it on paper as well. But I do not see how this falls into a pattern. (I ll squeeze my mind a little more) | koyan
Kwon-Tom Fan
Puzzles: 21 | Posted - 2015.08.18 16:57:53
So, a new version is online:
Apart from the solver itself (Which solves it each time you ask it), I made it to save the solution, and to present it nicely.
Here is an example:
http://www.kokkorogiannis.gr/slitherlink/v4/index2.php?preset=20
Comments and suggestions welcome. |
|
