| soduko
| | Joined: 10 Oct 2005 | | Posts: 50 | | : | |
Items |
|
 Posted: Sat Jul 29, 2006 12:28 am Post subject: New way to solve Sudoku (computer only) |
 |
|
I am puzzeling with a new way to solve sudoku with a computer.
(OK it is possible to do this by hand but I wont do it)
I am still in the programming stage but here is the outline of this method:
PS some of this only starts making sence after reading the whole outline
The program is build round fit(full implication tables) in short they are a more rigid variation of trebbortables (just a big 729 * 729 table) and also constraint-to-placement and placement-to-constrait tables are used
Fit(a,b) = forced iff placement a implies placement b
Fit(a,b) = blocked iff placement a blocks placement b
Ps the Fit table can thus contain three possible values: empty, forced or blocked
PS 2, forced, blocked and empty are just numerical constants nothing else.
Fit tables can in principle be split in two different tables
a PIT (positive implication table) size 729*81 for forced placements (not binary) and
a NIT (negative implication table) size 729 * 729 binary table for blocked placements
a placement cannot force more than 80 placements (one for every other cel in a sudoku grid )
but a placement can block more than 81 placements.
We also have a whitelist and a blacklist (the whitelist contains at most 81 placements the blacklist at most 729 minus something)
filling fit table before start.
| Code: |
for Pa = 1 to 729 (all placements)
for i = 1 to 4
c = placement-to-constraint(Pa, i)
for j = 1 to 9
Pb= constraint-to-placement(c,j)
fit(pa,pb) = blocked
next
fit(pa,pa) = forced or empty (not sure what is best but do not forget it)
next
next
|
For starting we just put all the clues as placements in the whitelist.
From this whitelist we create the blacklist and enlarge the whitelist
(if Pa is on the whitelist then
all b where Fit(a,b) = blocked are put on the blacklist
and all b where Fit(a,b) = forced are put on the whitelist)
from the blacklist we remove the placements from the constraint-to-placement list
and if Pb is on the blacklist then all a where Fit(a,b) = forced are put on the blacklist
If a constraint is left with only one placement option this placement is put on the whitelist.
The above takes care of all hiddden and naked singles.
Linking
After this we look at all constraits that have two placementoptions left
(call them P1 and P2)
every placement that blockes P1 forces P2 and vv
every placement that blockes P1 blocks al blockers from P2 and vv
Making chains
if Fit(a,b) = forced then all blockes and forces from b also apply to a
(NOT vv)
if Fit(a,b) changes from forced to blocked or vv then Placement a is blocked and can be put on the blacklist
This makes all weak chains, (strong chains are just seen as two weak chains in opposite direction)
After this we can do verities (same as in the Trebbor tables)
if all placements from a constraint-to-placement entry
forces placement A then put A on the whitelist
blocks placement A then put A on the blacklist
and even an other kind of test is possible
if a placement a leaves only one placement option in a constrait
(call this placement b, all others are blocked by a or on the blacklist ) then Fit(a,b) = forced
In principle this method does not understand triplets and higher sets but I am wondering if they are really neccesary for solving any sudoku (because the power of Trebor tables and chains is available)
Otherwise the Jaap1 and Jaap2 algorithems are implementable in this method (because of the use and availability constraint arrays)
but I think they will use more time and are more difficult to program than this simpel algoritm
Other basic logical rules also apply to Fit tables:
if fit(a,b) = blocked then fit(b,a) = blocked, !! this does not hold for fit(a,b) = forced
for all Pa, Pb and Pc if
fit (Pa,Pb) = forced and fit (Pb,Pc) <> empty then fit(Pa,Pc) = fit (Pb,Pc)
the above two combined
for all Pa, Pb and Pc if
fit (Pa,Pb) = forced and fit (Pc,Pb) = blocked then fit(Pa,Pc) = blocked
and maybe even others
the blacklist is even representable as
fit(0, a) = blocked (means something like "some clue blocks a")
and the whitelist as
fit(0, a) = forced (means something like "some clue forces a")
Maybe this is even quicker than DLX (but i only program in basic)
because there is no backtracking the whole method is strait forward logic
Anybody any comments or suggestions on this idea?
(Yes i have to do some more programming myself)
(and i must learn C, but maybe i am to old for that)
Ps while writing all kind of ideas came up and i put them in this post but this is only one of the reasons why this post is a bid chaotic |
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
