| New Here; Experienced at SlitherLink, though |
LeadMagnet
Kwon-Tom Addict
Puzzles: 263
Best Total: 34m 6s | Posted - 2007.08.08 20:05:13
Hey everybody, figured I'd introduce myself since I just joined here. I usually do slither link puzzles at puzzle-loop.com, but that seems to have been down alot lately, so I googled for a new place to play and found this site 
Anyway, it's nice to find a site that has a forum/community. Happy Puzzling!
-LeadMagnet |
foilman
Kwon-Tom Admin
Puzzles: 3613
Best Total: 24m 6s | Posted - 2007.08.08 20:48:28
Welcome and good luck!!  |
leadmagnet
Kwon-Tom Addict
Puzzles: 263
Best Total: 34m 6s | Posted - 2007.08.09 14:50:27
Thanks. I'm glad to be here.
On a side note, I was wondering. Has anyone ever written a program to solve slither link puzzles? It seems to me that it would be kinda hard to get a computer to make all the leaps of intuition required for a logic puzzle like this.
Last edited by leadmagnet - 2007.08.09 14:51:33 |
foilman
Kwon-Tom Admin
Puzzles: 3613
Best Total: 24m 6s | Posted - 2007.08.09 14:53:48
Yes, actually the same code I use to design the puzzles on this site can solve them too... it takes forever on some of the hard user-submitted puzzles, but it does get there eventually...! |
procrastinator
Kwon-Tom Obsessive
Puzzles: 1083
Best Total: 12m 56s | Posted - 2007.08.09 15:06:07
Quote: Originally Posted by leadmagnet Has anyone ever written a program to solve slither link puzzles? It seems to me that it would be kinda hard to get a computer to make all the leaps of intuition required for a logic puzzle like this. |
Slither-link puzzles can only have one solution. How do you think foilman knows that all his puzzles have only one solution? Somehow I doubt he proves it by hand every day. Or would trust himself not to make a mistake if he tried. 
A few others have mentioned writing such programs on the forum. By the sound of it, tilps in particular has worked pretty hard at his.
Welcome aboard. BTW, I notice you've only done two live puzzles. If you click on "Home", you get a list of the last week's puzzles and which ones you've done. (the archives also keep track of which old puzzles you've done) Once you've done a week's worth, you'll get a time for that week, and can see yourself climbing up the ladder. Some of the puzzles later in the week might be beyond you at first, but messing around with Fix Position will help you learn which possibilities to consider when you get stuck. |
Tilps
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | Posted - 2007.08.09 21:43:35
Leaps of intuition are hardly anything when you can try 3million positions a second.
Making a solver which plays like a person and does it well, thats a different question. |
leadmagnet
Kwon-Tom Addict
Puzzles: 263
Best Total: 34m 6s | Posted - 2007.08.09 22:00:24
Quote: Originally Posted by tilps Leaps of intuition are hardly anything when you can try 3million positions a second.
Making a solver which plays like a person and does it well, thats a different question. |
I tried making a brute-force solver once, but it seems to fail horribly at anything remotely large. Especially the 25x30's over at puzzle-loop.com. :-\ |
Tilps
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | Posted - 2007.08.09 23:15:52
25x30 is a pretty big puzzle size.
Brute force solvers need some smarts or they will indeed take forever. My brute force solver actually runs the non-brute force solver first simply because it usually saves a few seconds off the solving time. The non-brute force solver used in conjuction with the brute force solver doesn't need to be terribly smart in order to save a very large proportion of the time.
I haven't seen many puzzles which it takes that long to solve on. It does take quite some time to generate a puzzle of anything that size and larger. |
leadmagnet
Kwon-Tom Addict
Puzzles: 263
Best Total: 34m 6s | Posted - 2007.08.10 01:08:45
Quote: Originally Posted by tilps 25x30 is a pretty big puzzle size.
Brute force solvers need some smarts or they will indeed take forever. My brute force solver actually runs the non-brute force solver first simply because it usually saves a few seconds off the solving time. The non-brute force solver used in conjuction with the brute force solver doesn't need to be terribly smart in order to save a very large proportion of the time.
I haven't seen many puzzles which it takes that long to solve on. It does take quite some time to generate a puzzle of anything that size and larger. |
What do you mean by "that long" to solve? Like, from what I've seen, a brute force program can take a 5x5 in a second or two, but takes exponentially longer for bigger puzzles. Incorporating some logic into the solver (although it slows down the 5x5 time). Does speed up the times for 10x10, and even produced results in under 5 minutes for a normal difficulty 20x20. But even on a hard 15x15, it seems to take forever.
On a slight aside, though. You appear to have a good bit of experience with this. In my own program, I've managed to incorporate a decent amount of logic. One of my sticking points, however, is the Highlander logic. Did you incorporate logic for these situations into your program? I'm very interested in how it could be coded.
EDIT:
And yes, I can see how running the non-brute force first could save up to %50 of the processing time for each line (or X) determined.
Last edited by leadmagnet - 2007.08.10 01:10:03 |
Tilps
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | Posted - 2007.08.10 01:22:20
Adding highlander support to the solver becomes a feature you have to remove when it is a generator, it also has to be disabled when you are a verifier.
Highlander doesn't solve a puzzle, it finds a solution to the puzzle. If you have a specific puzzle with two solutions, you could use highlander to 'prove' that there are no solutions at all.
That being said I have not attempted to add highlander to my solver - mainly because I consider it 'cheating' - although I do regually use it on kwontom loop because the challenge is not solving the puzzle, its solving it fast. (And given how bad I am at that, I'll take every cheat I can  )
As for how long is 'that long' I can generate a 25x30 puzzle in 20minutes or so with the full solver. The solving of that puzzle (which is beyond my abilities to solve without nested fixed position) is done in approx 2seconds by my brute force solver with initial solving by my iterative 1 look ahead solver with advanced logic.)
Last edited by Tilps - 2007.08.10 01:58:04 |
mathmaniac
Kwon-Tom Obsessive
Puzzles: 1293
Best Total: 20m 57s | Posted - 2007.08.12 16:14:44
if your looking for a good solver, you can download loopy and import puzzles to be solved.
http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ |
