Minimal Solver logic/pseudo-logic

tilps · Posted: Sun Jun 19, 2005 6:55 am Post subject: Minimal Solver logic/pseudo-logic

Hi,

From my reading around and a bit of work on the problem writing my own solver, there appears to be two concepts
1. Cell value setting
2. Possibility pruning.

As far as I can tell there is only two rules (which are effectively the same rule in a broader sense) for Cell value setting.
1. if possibilities say there is only one option in a cell, that is the correct choice.
2. if possibilities say there is only one option in a group for a specific number, that cell is the correct choice for that number.

Possibility pruning consists of the most basic rule plus additional rules.
The most basic rule being, if you set a location, then no other numbers can be in that cell and that number cannot be in any other cells in same row/column/block(group) of the set cell.

From here you introduce additional rules, some people go down the brute force, trying huge numbers of combinations at random and pruning possibilities to match the only solution found. Other people apply 'logic'.
The way this logic is played out is that effecitvely apply not trial and error, but trial and 'see what happens'. If there are two possibilities for something, and the same thing happens on both branches, then you can apply that 'same difference' back to the original set and call it logic.

When it came to writing my own solver, writing 97 different 'additional rules' didnt appeal when they are virtually all expressible as 'try a or b and determine the common changes and apply them back'. So that is what my solver does.
My solver consists of the standard cell setting rules and the most basic possibility pruning rule, plus the 'find possibility pairs and try a or b and determine common changes and apply them back' rule. In actuality it'll go further and do 'find possibility tripplets and try a or b or c and determine common changes...' and higher orders, which I thought I would need to solve locked tripplets problems - but i'm yet to find a puzzle (or generate one) which actually requires this additional power. It solves rubylips's 48 retry puzzle with only investigating possibility pairs.
I should clarify what determine common changes means. For each possibility pair a and b, it calls a restricted solve for each of trying a and b, restricted to performing the 3 core functions and 1 less lookahead. In the pairs case this means not using the lookahead capabilities. If solve claims there exists no solutions, then it is not considered in determine common changes. A common change is a possibility which was true before the lookahead but is false in all considered futures.

What I am wondering is why I havent found a puzzle which requires second order lookahead logic creation, why 'trial and error required' problems fall to what is effectively first order logic? Are there 9x9 puzzles which cant be solved using first order lookahead logic creation?

Simes · Posted: Sun Jun 19, 2005 9:12 am Post subject:

angusj · Site Admin

Edit: Oops, make a mistake.
I thought 2 were insoluble when in fact they weren't.

Simes · Posted: Sun Jun 19, 2005 12:45 pm Post subject:

angusj · Site Admin

tilps · Posted: Sun Jun 19, 2005 2:15 pm Post subject:

tilps · Posted: Sun Jun 19, 2005 2:37 pm Post subject:

Maybe the fact that my algorithm 'makes progress' when one of the two options is 'trivially impossible' makes it cover both logic and 'nishio' type first order rules. I might try disabling that and seeing how many problems it can still solve. Althought I still expected second order to be required to solve some problems.

Doug · Posted: Sun Jun 19, 2005 10:26 pm Post subject:

I'm still not clear on your definition of "common change" or what you mean by "1 less lookahead". 1 less than what? Also, you say "same difference" earlier. Is this the same as "common change"?
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

tilps · Posted: Sun Jun 19, 2005 11:10 pm Post subject:

Okay so I disabled making progress in the one option fails case, and my algorithm now fails to solve lots of things, even with 3 lookahead. Which makes an interesting datapoint to anyone wondering whether 'logic' can solve all puzzles.

For doug, to try and clarify further. Say you have a specific position and with in this position there is a possibility pair. Any pair of options which are the only options for a cell, or column/row/group with same number is a possibility pair. Call these two options A and B. If you try A, it has immediate consequences, but lets follow through these consequences under the basic core 3 rules, the 'trivial' rules of cell value setting and the most basic rule of possibility pruning. This leads to modifications of the possibility state of the board. Save this state. Do the same for B and save that state. Now for each possibility in the board prior to performing A or B, see if that possibility no longer exists in Either A or B. That is a common change. If it is not possible in either A or B then it is not possible at all, so you can eliminate that possibility from the original board, and continue onwards with the original board.
This is logical lookahead 1. However, this discription neglects that choosing A may result in an inpossible board, under the trivial rules. If it did, then B is true and A can be ignored. Conversly if B results in an impossible board under trivial rules, then B can be ignored.

Logical lookahead 2 takes possibilty triplets. Because of the nature of possibility tripplets, in order to capture all logic associated with them you have to not just allow for the trivial rules in looking ahead. You also have to allow lookahead 1. So there will be options A B and C which you start with. You try A, applying the core rules and Lookahead 1 rules to the virtual board. Then try B with same, and C with same. Then for each possibility on the original board, if it is not possible in A B and C then you can remove it from the original board. Again this neglects the impossible board situation but that can be extended in the obvious manner.

Logical lookahead n - takes possibility (n+1)lets, tries each one with core rules and anything upto lookahead n-1, and applies the common changes back to the original board.

My current conjecture is that Logical Lookahead n without allowing the impossible board situation - is equivelent to the definition of 'logic' that most people use. It should cover any logic rules already in use, and also ones still being thought up. Logical Lookahead 1 covers xwing/swordfish/jellyfish/etc Logical Lookahead 2 covers locked tripplets, and the equivelent tripplexwing type logics. Logical Lookahead 1 with allowing use of the impossible board situation adds some nishio, and some other progress through failure rules. It however is still not brute force. Logical lookahead 1 doesnt do anything other then core rules after attempting an option, and it only attempts options on possibility pairs. Logical lookahead 1 does not cover locked tripplets, but the addition of nishio-like attacks through the failed board situation may effectively make that redundant.

tilps · Posted: Mon Jun 20, 2005 12:31 am Post subject:

Doug · Posted: Tue Jun 21, 2005 9:15 pm Post subject:

tilps--

Still not positive about your algorithm. When you say: "but lets follow through these consequences under the basic core 3 rules, the 'trivial' rules of cell value setting and the most basic rule of possibility pruning", I take it you mean apply the simple three rules iteratively to the whole board to update it. In other words, the algorithm follows the chain of logic, possibly with many intermediate updates for the entire board, until a final board state is reached. Is that correct? That's the only interpretation that makes sense to me. Thus Logical Lookahead 1 is not a 1 deep lookahead in the sense of applying the three simple rules one time for each row, column, block to get the next (ply 1) update of the board, but possibly a ply n lookahead.

Small point on wording. When you say "see if that possibility no longer exists in Either A or B" and also when you say "If it is not possible in either A or B", I think you should use an "and" instead of an "or". You want cells that when updated under both possibilities result in the impossibility of a number in that cell in both updates, not one or the other. (English is ambiguous the way you have worded things. People commonly say "or" in this situation, when they mean "and", the meaning being gleaned from context. Here the only thing that makes sense is and, so I take it that is your meaning. But I had to use "Logical Lookahead 1" on your writing to see that. Wink

Assuming these interpretations are correct, I think Logical Lookahead 1 is equivalent to the "Bingo" algorithm that MadOverloard has implemented. So far no puzzles have been found that cannot be done this way. But I have seen the ply go verrry deep to solve certain puzzles. I've seen at least 9 deep iteration updates of the entire board required before a value could be excluded for certain puzzles. Edit: No, the "bingo" algorithm seems to be different from Lookahead 1 as it allows the setting of values in triples, etc.. But it is not Lookahead 2 either, since it sets no further values when computing the implication, ie doesn't do Lookahead 1 in the process.

Regarding the necessity for Logical Lookahead 2: I haven't seen any need for it yet on 9x9 sudoku. I think for larger boards it will be necessary, but its tempting to conjecture that its not for 9x9.... What might be true is that by using Logical Lookahead 2 or higher, lower ply solutions to some difficult puzzles might be found. That would be interesting, I think. My guess is that for certain puzzles, the depth of lookhead in Logical Lookahead 1 would be reduced, but that most of the time it won't help. Some puzzles just require deep lookaheads!
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage

tilps · Posted: Wed Jun 22, 2005 12:48 am Post subject:

Yes it follows the chain of logic iteratively, otherwise it wouldnt cover swordfish or higher order fishycycles. I dont consider the application of 'pure' logic to be lookahead.

As to gramatical error there - either should work as splitting the sentence into not possible in A and not possible in B, but I am no gramatical expert.

tilps · Posted: Wed Jun 22, 2005 11:16 am Post subject:

Okay, have finally gotten round to testing, and ignoring the fact that they are unsolvable appears to work, havent found any which it cant solve yet. Looks like 'logic' is back on track for being able to solve anything.