|
| View previous topic :: View next topic |
| Author |
Message |
| Doug
| | Joined: 28 May 2005 | | Posts: 42 | | : | |
Items |
|
 Posted: Wed Jun 01, 2005 4:29 am Post subject: Limited Implication Trees (Edited Title) |
 |
|
This is an algorithm which can solve certain difficult problems. It is a way of tracking value implications easily.
The idea uses labeled directed graphs. (Edit: In fact, it generates a tree.) The vertices are cell locations. The edges are ordered pairs, where the first element is a possible value for the first cell and the second value is a forced value for the second cell. To keep the algorithm from being the same as "guessing", the second forced value must follow direclty by the new second cell either having only two possible values, or by the first cell having the value of the first element of the ordered pair leaves only one location in the row, column, or block for the second value of the ordered pair, that location being the second cell.
The algorithm is to choose a value for a cell and inductively generating the graph (Edit: tree) of forced values. When a cycle is created, say starting with vertex (cell) x and coming back to x, the second element of the ordered pair leading into x is compared with the first value on the outgoing edge from x. If these dissagree, then the cell can have the first value in the ordered pair leading to that value for x eliminated as a possibility. (Edit: More clearly, when looking at values forced from a particular vertex, if a value is forced on a vertex already visited, and so having a value, the new forced value is checked against the previous value. If it is consistent, then an edge is not added between these vertices. In this way cycles are avoided and a tree is created. This guarentees termination of the algorithm.)
If no cycles are created, or all cycles are consistent, then the next permissable value for that cell is tried and so on. After all (Edit: permissable) values for a cell are tried, the algorithm moves on to the next cell.
Notes:
1) Cycle detection is easy. One makes a table of vertices that have occured in the algorithm. A repeat indicates a cycle. Edit: The algorithm should not add cycles to the graph, rather only including new vertices and forming a tree. When a vertex gets visited again, it is mearly checked for consistency.
2) Labeled directed graphs can easily be represented as a data structures.
---------------
Below are two examples of "challenge" problems which this algorithm resolves.
The first example is from
http://www.sudokusolver.co.uk/codeit.html
*43|98*|25*
6**|425|***
2**|**1|*94
------------
9**|**4|*7*
3**|6*8|***
41*|2*9|**3
------------
82*|5**|***
***|*4*|**5
534|89*|71*
After applying standard techniques this problem acquires the following permissions matrix
| Code: |
1 2 3 4 5 6 7 8 9
-------------------------------------------------------------------
A| 17 4 3 9 8 67 2 5 167
B| 6 789 1789 4 2 5 138 38 178
C| 2 578 578 37 36 1 68 9 4
D| 9 568 2568 13 135 4 1568 7 1268
E| 3 57 257 6 157 8 49 24 129
F| 4 1 5678 2 57 9 568 68 3
G| 8 2 17 5 16 367 49 346 69
H| 17 69 69 17 4 23 38 238 5
I| 5 3 4 8 9 26 7 1 26
|
Starting with vertex A1 and the possible value 7 we get the following directed graph. (I only give the relevent part of the graph. The ordered pairs represent edges and the direction is from left to right.)
A1 (7,1) H1 (1,7) H4 (7,3) C4 (3,6) C5 (6,7) A6 (7,1) A1.
So there is a cycle from A1 to A1 with the edges going in and coming out of A1 being: (7,1) A1 (7,1). Since A1 cannot have both values 1 and 7, it follows that A1 cannot have value 7.
Note that this example was also resolved by a different suggested technique by Mark Summerville. The difference between the techniques is that this suggested algorithm does not require the search for "cyclical groups". On the other hand, using cyclical groups would strengthen the algorithm under discussion. (Knowing them would in some cases allow for more outward edges from a given vertex, namely to those other vertices in the cyclical group.)
Example 2
This is also a challenge problem from:
http://www.sudokusolver.co.uk/challenge.html
*2*|***|***
***|6**|**3
*74|*8*|***
------------
***|**3|**2
*8*|*4*|*1*
6**|5**|***
------------
***|*1*|78*
5**|**9|***
***|***|*4*
After standard techniques this give rise to the following permissions matrix:
| Code: |
1 2 3 4 5 6 7 8 9
-------------------------------------------------------------------
A| 13 2 6 349 35 7 149 59 8
B| 8 9 5 6 2 14 14 7 3
C| 13 7 4 39 8 15 1269 259 169
D| 4 5 7 1 9 3 8 6 2
E| 9 8 3 2 4 6 5 1 7
F| 6 1 2 5 7 8 39 39 4
G| 2 36 9 34 1 45 7 8 56
H| 5 4 8 7 36 9 1236 23 16
I| 7 36 1 8 356 2 369 4 569
|
This problem is resolved by the following directed graph:
A1 (3,1) C1 (1,5) C6 (5,3) A5 (3,1) A1.
Here the edge leading into A1 gives the value 1, while the edge leading out has the value 3. This implies that 3 is not possible for A1 and so it must have the value 1. Giveing A1 the value 1 resolves the problem after standard techniques.
Note in this example, using cyclical groups does not give the implication C1 (1,5) C6 as C1 and C6 are not part of a cyclical group. On the other hand, in other situations, the cyclical groups will give implications that this method misses.
-----------
This algorithm can be improved by initially making a table of cyclical groups and adding edges for them to the directed graph.
These kinds of algorithms (Edit: could be viewed as) a limited form of guessing. But it is likely that certain problems can only be solved using such techniques.
Edit: One thing that is not clear above is whether the permissions matrix is updated after possible values are assigned in the tree generation. (Permissions being updated by just excluding values in rows, columns and blocks.) If this is done, then this algorithm should contain the Nishio rule as a special case. Thinking about this more, is this method just what is refered to as Nishio? The contradiction being the impossibility of placing the value in the first cell of the tree? Hmm. I looked at the Nishio definition thread and it seems to concern itself with only one possible value at a time throughout the grid. This algorithm considers many different values. The contradiction may not be with the initial possibility considered. So it looks more general than Nishio to me.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage |
|
| Back to top |
|
 |
| MadOverlord
| | Joined: 01 Jun 2005 | | Posts: 80 | | : | | Location: Wilmington, NC, USA |
Items |
|
| Posted: Thu Jun 02, 2005 6:43 pm Post subject: Coded it, I think... |
|
|
I've implemented a solver that I think gets to the core of limited implication chains. I call it Simple Forcing Chains. LIC might be a superset of SFC, or they might be equivalent.
My algorithm is to start at a square, make a choice for it, and then wander around the other 2-possibility squares in its row/col/block that are affected by it, building a chain of "if square A is X that means square B is Y which means square C is Z" until it gets back to square A. If the loop is inconsistant (the square before we get back is the same as the original choice we made for the first square). then we can eliminate a possibility.
This one solves sudokusolver.co.uk's challenge #1 puzzle, but not the #2
| Code: | SudokuSolve.deduce_rule9:
Function deduce_rule9(puzzle() As Integer) As moveList
Dim i,j As Integer
Dim s As String
Dim ml As new moveList
Dim squares(-1),choices(-1) As Integer
// This is the simple forced chains rule. Basically,
// we ask ourselves, "what are the consequences of
// setting a square to a particular value?" and
// follow the chain of consequences, trying to find
// a contradiction. If we do find one, then we know
// our original choice must be incorrect, and we can
// remove it.
// To emulate typical human reasoning capabilities,
// we only look at moves that force other squares
// that have 2 possible values to go to one value.
// Look at each square in turn
for i = 0 to 80
// if it has more than one possibility
if bitCount(puzzle(i)) > 1 then
// for each possibility, explore the consequences
for j = 0 to 8
if bitwise.bitAnd(puzzle(i),bits(j)) = 1 then
// squares and choices are arrays of squares we've already
// visited, and choices we've already made. We use them
// to keep track of the chain; they start out empty.
// note that we are passing our new square choice as
// a bitmap, not a bit number
ml = deduce_rule9_chain(squares,choices,i,bits(j))
// return if successful
if ml.foundMoves then
return ml
end if
end if
next j
end if
next i
// fail
return ml
End Function
SudokuSolve.deduce_rule9_chain:
Function deduce_rule9_chain(squares() As Integer,choices() As Integer,square As Integer,choice As Integer) As moveList
// Simple forcing chains
Dim i,j,k,cs,cv As Integer
Dim s As String
Dim ml As new moveList
// In this algorithm, I'll maintain the squares and choices arrays
// without copying, by expanding them before recursing, and cutting
// them back before returning. I could do this in the other recursive
// routines, but they are sufficiently complex that it was clearer
// not to. But I want to show the programmers out there that I knew
// I could do this... (grin)
// so the first step is to add the new move and choice
// to the squares and choices
squares.append square
choices.append choice
// For our chosen square, look at all its buddies in the rows,
// columns and groups to find another candidate. The candidate
// must be a 2-possibility square that contains the previous
// choice.
// I have some arrays rowBuds(80,7), colBuds(80,7) and blockBuds(80,7)
// that store, for each square, the other members of the row, column
// or block. And from that it is easy to precompute a list of all
// the squares that share a row,col or block with a square, which
// I've stored in allBuds(80,19) [there are always 20 such buddy squares]
for i = 0 to 19
// Get the current square and its value. Note that in this algorithm
// we don't update the possibilities for each square after each choice;
// we keep them the way they currently are, just like a normal non-braniac
// human would.
cs = allBuds(square,i)
cv = puzzle(cs)
// If the square contains the previous choice
if bitWise.bitAnd(cv,choice) <> 0 then
// Then it is not in the current chain of squares
j = squares.indexOf(cs)
if j = -1 then
// And only if the square has 2 possible choices, we can continue
if bitCount(cv) = 2 then
// We haven't visited this square before, so we can
// go deeper, selecting the new square, and using the choice
// remaining after eliminating the last one.
ml = deduce_rule9_chain(squares,choices,cs,bitwise.bitAnd(cv,bitwise.onesComplement(choice)))
// if we found a valid move, then we need to return with it
if ml.foundMoves then
// Remember to shorten the arrays. Technically, since we are exiting
// out of the nesting all the way, we don't need to do this, but I
// think it's sloppy not to do so, and being "clean" tends to prevent
// bugs from creeping into your code, so it's a good habit.
redim squares(uBound(squares)-1)
redim choices(uBound(choices)-1)
return ml
end if
end if
else
// We've run into a square that's already in our chain, which forms
// a loop. If that square happens to be the first one, then we
// check to see if we have a logical inconsistency.
if j = 0 then
// yep, we've looped back to the beginning. Now, we decided that
// that first square had value choices(0). So if the last choice
// we made is also choices(0), we've got an inconsistent loop
// and can clean things up.
// To make things more clear, consider a square with possibilities
// 1234. We chose 1 to test. When we got back to the original
// square, if the previous square was a 4, the
// possibilities left are 123, and it isn't inconsistent. But
// if the previous square was a 1, the original square cannot be
// a 1, so it's a bad cycle!
if choices(0) = choice then
ml.foundMoves = true
// figure out what the new possibilities are; this is the old ones
// less the original choice we made, which we now know cannot be
// true
k = bitwise.bitAnd(puzzle(squares(0)),bitwise.onesComplement(choices(0)))
// add this change to our movelist
ml.s.append squares(0)
ml.v.append k
// if actually solved a square, trigger a reconstraint run
ml.reconstrain = (bitCount(k) = 1)
// tell them what happened
ml.comment = " Rule 9 : Found a simple forcing chain. If we assume that square" + chr(13)
ml.comment = ml.comment + " " + theSquare(squares(0)) + " is <" + showbits(choices(0)) + "> then we can make the"
ml.comment = ml.comment + " following chain of conclusions:" + chr(13) + chr(13)
for k = 1 to uBound(squares)
ml.comment = ml.comment + " " + theSquare(squares(k)) + " must be <" + showbits(choices(k)) + ">, which means that" + chr(13)
next k
ml.comment = ml.comment + " " + theSquare(cs) + " must be <" + showbits(bitwise.bitAnd(cv,bitwise.onesComplement(choice))) + ">." + chr(13) + chr(13)
ml.comment = ml.comment + " Since this is logically inconsistent, " + theSquare(squares(0)) + " cannot be <" + showbits(choices(0)) + ">." + chr(13)
// trim back those squares (neatness counts!)
redim squares(uBound(squares)-1)
redim choices(uBound(choices)-1)
// and return our victory
return ml
end if
end if
end if
end if
next i
// return failure; remember to cut back the arrays
redim squares(uBound(squares)-1)
redim choices(uBound(choices)-1)
return ml
End Function
|
|
|
| Back to top |
|
|
| MadOverlord
| | Joined: 01 Jun 2005 | | Posts: 80 | | : | | Location: Wilmington, NC, USA |
Items |
|
| Posted: Sat Jun 04, 2005 2:33 pm Post subject: |
|
|
Doug, I started playing with an extension of Simple Forcing Chains this morning.
It occurred to me that if I could find a valid forcing loop in the puzzle, then if I could find a loop that hangs off it (a chain that exits the main loop via one vertex and re-enters at another) that was self-contradictary, it would invalidate the main loop.
However, after thinking about it for a bit, it seems to me that the new subchain, plus the segment of the original loop it connects to, would itself form a simple forcing loop that we would already have detected as self-contradictary, so nothing is gained.
If I am wrong and there's something to be gained from this, please let me know. |
|
| Back to top |
|
|
| someone_somewhere
| | Joined: 28 Aug 2005 | | Posts: 1 | | : | |
Items |
|
| Posted: Sun Aug 28, 2005 10:34 am Post subject: Re: Limited Implication Trees (Edited Title) |
|
|
[quote="Doug"]
Below are two examples of "challenge" problems which this algorithm resolves.
The first example is from
http://www.sudokusolver.co.uk/codeit.html
*43|98*|25*
6**|425|***
2**|**1|*94
------------
9**|**4|*7*
3**|6*8|***
41*|2*9|**3
------------
82*|5**|***
***|*4*|**5
534|89*|71*
After applying standard techniques this problem acquires the following permissions matrix
[code]
1 2 3 4 5 6 7 8 9
-------------------------------------------------------------------
A| 17 4 3 9 8 67 2 5 167
B| 6 789 1789 4 2 5 138 38 178
C| 2 578 578 37 36 1 68 9 4
D| 9 568 2568 13 135 4 1568 7 1268
E| 3 57 257 6 157 8 49 24 129
F| 4 1 5678 2 57 9 568 68 3
G| 8 2 17 5 16 367 49 346 69
H| 17 69 69 17 4 23 38 238 5
I| 5 3 4 8 9 26 7 1 26
Hi,
I think that if you take a look at the number 6 that can be in row A columns 6 and 9 only and in row I columns 6 and 9 only, we have a
X-wing situation and this means that number 6 can't be in row G column 6 and can't be in row D column 9 and can't be in row G column 9.
This X-wing will solved much easy this example.
P.S. nothing against your nice algorithm, but no need for your first example.
see u, |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
