| Logic vs. brute force |
lodenkamper
Kwon-Tom Fan
Puzzles: 21
Best Total: 47m 58s | Posted - 2006.06.15 01:08:42
In the paper vs. computer topic, an interesting discussion about logic vs brute force in solving puzzles has come up. As I see it, it is helpful to consider two extreme cases:
A) pure brute force --- little or no progress can be made incrementally. Human solution requires deep analysis for nearly every line and x in the early going, and/or significant trial and error. Computer solution requires extensive searching and/or enumeration of possibilities.
B) pure logic --- incremental progress is very easy. The entire puzzle can be solved (by human or computer) with local logic.
Real puzzles tend to fall in between these two extremes, since B types tend to be too easy and A types can be brutally difficult. Also, of course, people differ widely in their ability to see possibilities for making incremental progress, so the same puzzle can be logically solvable for one person and require brute force for another person. So there isn't really a clear dividing line betweeen puzzles which are "logically solvable" and those which are not. Especially since "local logic" can mean different things to different people (or even to different computer solvers).
Sudoku puzzles have this same kind of uncertainty, and it amuses me to see Sudoku book authors fussing over exactly where to draw the line.
One of the things that makes kwon-tom loop puzzles interesting for me is that it is possible to make intrinsically hard puzzles (i.e., that approach the A extreme) that are surprisingly small. The 10x10 "hard puzzle" here, and some of the small (9x9, 10x10) janko.at puzzles seem to be in this category. The severe difficulty of these small puzzles leads me to suspect that if this kind of puzzle can be made large enough, it may not be humanly solvable. I wonder if any of the folks out there with puzzle generators have looked into this?
My personal dividing line for logic vs. brute force depends on uniqueness --- if I solved the puzzle and am convinced the solution is unique, I feel like I solved it logically. If I solved the puzzle and am not convinced of uniqueness, then it feels more like brute force to me. |
m2e
Kwon-Tom Obsessive
Puzzles: 607
Best Total: 16m 43s | Posted - 2006.06.15 01:56:52
Quote: Originally Posted by lodenkamper My personal dividing line for logic vs. brute force depends on uniqueness --- if I solved the puzzle and am convinced the solution is unique, I feel like I solved it logically. If I solved the puzzle and am not convinced of uniqueness, then it feels more like brute force to me. |
|
mathmaniac
Kwon-Tom Obsessive
Puzzles: 1293
Best Total: 20m 57s | Posted - 2006.06.15 02:01:16
I agree. |
Tilps
Kwon-Tom Obsessive
Puzzles: 6510
Best Total: 20m 22s | Posted - 2006.06.15 03:49:11
Having written both a sudoku generator and a loop-de-loop generator, I have to say that sudoku and loop-de-loop have very different solving distributions interms of how many puzzles require certain levels of strategy.
In Sudoku, something like 90% of randomly generated (minimum clue) puzzles can be solved without lookahead. 99.9999% of randomly generated sudoku puzzles can be solved without using nested lookahead, by using contradictions found from forced moves from a single trial, or from common forced moves from sets of trials. (Actually, I think I disabled contradictions because i found no examples of where it changed whether the puzzle was solveable, and it made the proofs my program provides more acceptable to 'pure logic' people)
In loop-de-loop, the statistics are very different, its very rare for a minimum-clue randomly generated puzzle to be solveable without lookahead, and (quoth from observation of my own solvers, not calculation) less than 50% can be solved without nested lookahead, even with the use of edge coloring (which is really a kind of nested lookahead).
In Sudoku, it makes more sense to argue about these things, because so few puzzles exist (compared to the puzzle space) which can't be solved using iterative deduction. (For quite sometime I thought I had convinced myself that there were no sudoku puzzles which couldn't be solved without nested lookahead - but that would have proved NP=P and won me a million dollars ... ) |
mathmaniac
Kwon-Tom Obsessive
Puzzles: 1293
Best Total: 20m 57s | Posted - 2006.06.15 04:03:25
you lost me |
m2e
Kwon-Tom Obsessive
Puzzles: 607
Best Total: 16m 43s | Posted - 2006.06.15 04:26:28
heh whats the differenece between nested lookahead and lookahead? i THINK i know what you mean but wanna be certain... |
Tilps
Kwon-Tom Obsessive
Puzzles: 6510
Best Total: 20m 22s | Posted - 2006.06.15 04:50:55
For both loop-de-loop and sudoku there are sets of things which are universally agreed upon as 'not lookahead' 3 x's at an intersection, 1 line and 2 x's, 2x's on a cell with a 2 in it. etc etc. I call these 'forced moves'.
Two kinds of lookahead are used, 1) - I set something as true, put an x in or a line (or a number in a cell in sudoku) and then apply 'forced moves' until we reach a contradiction.
2) - I consider a set of options and try each one and its associated forced moves and take the common forced moves. You can only do this if the set of options is logically complete. In sudoku, this is generally 'all the places a specific number can be in a row, column, 3x3 square' or 'all the possible numbers for a single cell' - in loop-de-loop I simply use x and line for a given edge.
Nested lookahead is where neither of the above are enough. In nested lookahead you make multiple placements which aren't forced in a single trial.
Last edited by Tilps - 2006.06.15 04:55:51 |
m2e
Kwon-Tom Obsessive
Puzzles: 607
Best Total: 16m 43s | Posted - 2006.06.15 05:02:42
Ah ok i undetand now  |
foilman
Kwon-Tom Admin
Puzzles: 3411
Best Total: 24m 6s | Posted - 2006.06.15 07:43:17
None of the puzzles on here require nested lookahead then... my puzzle generator isn't clever enough to use it! And in fact I also limit how far ahead it looks on normal lookahead, to keep things within the realm of human solvability... as well as only considering certain edges for lookahead (not ones in the middle of nowhere, for example). In fact, that's what distinguishes a hard from a very hard - just the maximum limit on lookaheads. Easy and medium levels basically just use patterns. |
PuzzleLover
Kwon-Tom Obsessive
Puzzles: 1033
Best Total: 38m 17s | Posted - 2006.06.15 08:39:22
Quote: Originally Posted by foilman None of the puzzles on here require nested lookahead then... my puzzle generator isn't clever enough to use it! And in fact I also limit how far ahead it looks on normal lookahead, to keep things within the realm of human solvability... as well as only considering certain edges for lookahead (not ones in the middle of nowhere, for example). In fact, that's what distinguishes a hard from a very hard - just the maximum limit on lookaheads. Easy and medium levels basically just use patterns. |
|
tilps
Kwon-Tom Obsessive
Puzzles: 6510
Best Total: 20m 22s | Posted - 2006.06.15 09:12:52
Quote: Originally Posted by foilman None of the puzzles on here require nested lookahead then... Easy and medium levels basically just use patterns. |
Do you use paterns within the lookahead as forced moves? - If so, you are probably using a kind of nested lookahead, just like I am with my edge coloring. (and with my cell intersection interactions)
I'm pretty sure I've loaded up a few of the puzzles here into my solver and found them not to be solvable via 'pure' lookahead. |
foilman
Kwon-Tom Admin
Puzzles: 3411
Best Total: 24m 6s | Posted - 2006.06.15 09:24:10
Quote: Originally Posted by puzzlelover Can you give guidelines on what sort of lookahead parameters give a hard or very hard rating in your puzzles? Thanks. |
|
foilman
Kwon-Tom Admin
Puzzles: 3411
Best Total: 24m 6s | Posted - 2006.06.15 09:24:57
Quote: Originally Posted by tilps Do you use patterns within the lookahead as forced moves? - If so, you are probably using a kind of nested lookahead, just like I am with my edge coloring. (and with my cell intersection interactions) |
|
drnull
Kwon-Tom Obsessive
Puzzles: 1053
Best Total: 23m 25s | Posted - 2006.06.15 12:25:29
Quote: Originally Posted by foilman Not really, no... it's not that straightforward! Fundamentally the very hard has a longer lookahead in it, but there are other factors at work like the average difficulty of patterns used, average lookahead distance, etc... |
|
foilman
Kwon-Tom Admin
Puzzles: 3411
Best Total: 24m 6s | Posted - 2006.06.15 12:32:59
No there's no actual fixed number of lines... but 100 lines just to rule out a possibility would be ultra-hard, way beyond very hard. |
lodenkamper
Kwon-Tom Fan
Puzzles: 21
Best Total: 47m 58s | Posted - 2006.06.15 18:27:49
Quote: Originally Posted by tilps Having written both a sudoku generator and a loop-de-loop generator, I have to say that sudoku and loop-de-loop have very different solving distributions interms of how many puzzles require certain levels of strategy.
In Sudoku, something like 90% of randomly generated (minimum clue) puzzles can be solved without lookahead. 99.9999% of randomly generated sudoku puzzles can be solved without using nested lookahead, by using contradictions found from forced moves from a single trial, or from common forced moves from sets of trials. (Actually, I think I disabled contradictions because i found no examples of where it changed whether the puzzle was solveable, and it made the proofs my program provides more acceptable to 'pure logic' people)
In loop-de-loop, the statistics are very different, its very rare for a minimum-clue randomly generated puzzle to be solveable without lookahead, and (quoth from observation of my own solvers, not calculation) less than 50% can be solved without nested lookahead, even with the use of edge coloring (which is really a kind of nested lookahead).
In Sudoku, it makes more sense to argue about these things, because so few puzzles exist (compared to the puzzle space) which can't be solved using iterative deduction. (For quite sometime I thought I had convinced myself that there were no sudoku puzzles which couldn't be solved without nested lookahead - but that would have proved NP=P and won me a million dollars ... ) |
I have played around with Sudoku and kwon-tom loop solvers (although I haven't taken the next step to puzzle generation yet), and I have seen the same pattern as tlips. Specifically, a Sudoku solver that is limited to standard patterns can solve at least 80 to 90% of Sudoku with 17 givens that I gave to it.
In contrast, my kwon-tom loop solver is very strong at using local patterns, but needs improvement on finding loops (e.g., if a move will close a loop, but the closed loop is not completely determined, my solver will not rule the move a contradiction). It is interesting that different kwon-tom loop puzzles can differ radically in terms of how important loop finding is for their solution. The solver as it stands can't solve some puzzles that I find to be relatively easy, while it can solve many puzzles that are difficult for me to solve.
Last edited by lodenkamper - 2006.06.15 20:13:40 |
