View previous topic :: View next topic 
Author 
Message 
 soduko
 Joined: 10 Oct 2005  Posts: 50  :   Items 

Posted: Wed Jun 24, 2009 11:40 am Post subject: fittable solver 


in an old post
http://www.setbb.com/sudoku/viewtopic.php?t=1047
i wrote about another way to solve soduko's (i called the FIT (full implication ) tables, an advancement on trebortables
I finaly made a solver built arround this system and it works awesome.
Even without all logic possible it allready solves (i guess) all of the top 50.000
(I am only running on a basic interpreter and the program has solved the first 10.000 without any sweat)
(still need to make the program more efficient and remove all unnescesary tests, old code ect.)
I would like to put it somewhere for general inspiration and so.
where can i send it to?
will give more details later 

Back to top 


 Adak
 Joined: 27 Feb 2008  Posts: 87  :   Items 

Posted: Wed Jun 24, 2009 8:22 pm Post subject: 


Why not post it, here? This is the sudoku programmer's forum, after all.
If it's too big, or you can't post it here, use swoopshare:
http://en.swoopshare.com/
(Free, and no registration is required)
Be sure to post up the the link to the file, so we can d/l it.
And congratulations on your program. 

Back to top 


 ChPicard
 Joined: 12 Mar 2008  Posts: 82  :  Location: Montreal, Canada  Items 


Back to top 


 strmckr
 Joined: 24 Apr 2009  Posts: 52  :   Items 

Posted: Thu Jun 25, 2009 9:00 am Post subject: 


i do have some suggestions for this based on a concept ive been developing. i have it set as a secret function on my solver ive posted on here.
Paired Propagation:
1 bilocal clues that share the same two houses can form a set of pairs if they share a common candidates, these sets of pairs have specific aligments of clues linked via the confining spaces. {tables}
the idea is that the pair forms a reduction of table sets via linked digtis that are directly implicated by the potential pair.
the linked cells can be of any length and incorparte numorus techiques to further reduce the grid based on implications of a maksed subset state of constraints and can either
a: be the solution,
B: form a contradiction state or a mutistate.
when a contradictive state is derived the propagted pair is false, thus any moves or sets of moves that force the expression of the pair are invalid states.
my solver is currently set to type b: using a back trackign algorith coupled with techniques to induce a invalid puzzle state thus the contradiction is expressed in whole.
but a contradiction is expressed much earlier then that and does not require back tracking: it requires an large amount of tabled sets to be traced at the same time noting reductions of states with out impling them.
{ i havent only started to program it so im using aback tracking method to get it to work. }
i can show how it works on a few puzzles by hand if your intrested.
i also belive the system can be further extened into other types of states as well.
triples/quads,
and Dual paired propagation. {2 directly linked potential paired sets}
when i have it set to solve for
A: it acts more like a permation of potential sets over linkages.
but it solves much faster. 

Back to top 


 soduko
 Joined: 10 Oct 2005  Posts: 50  :   Items 

Posted: Thu Jun 25, 2009 5:19 pm Post subject: 


at the moment it does 14 soduko's per second.
ps this is a QBASIC interpreter and the code is far from optimised. (in an MS dos box on a 2 ghz computer)
it doesn't use houses or anything of that kind it uses more abstract entities like placements constraints and (logical) implications.
in a 9x9 soduko
there are 729 (9 ^3 ) placements (a symbol in a particular cel R1C1=1 till R9C9=9 )
and 324 contraints ( every cel, colum/symbol row/symbol and grid/symbol combination)
every constraint is a list of 9 placements where only one can be part of the solution.
for the rest it is all logic to add placements to the solutions.
block placements that cannot be part of the solution.
make a list of placements that imply or block other placements ect ect.
(and if the placement blocks itself it cannot be part of the solution, if it imply something like that the same)
and that solves the soduko.
(Ok there is a bit more to it but you catch the drift of it)
Will optimise the code a bit more.
(it has lots of unnessecary tests in it just to find programming errors quickly)
will keep you informed. 

Back to top 


 Lunatic
 Joined: 11 Mar 2007  Posts: 166  :  Location: Ghent  Belgium  Items 

Posted: Thu Jun 25, 2009 6:36 pm Post subject: 


soduko wrote:  ps this is a QBASIC interpreter and the code is far from optimised. 
I really would like to see your code. I used to write QBasic programs years ago, and it's not that great step to translate into VisualBasic. _________________ Marc
~~~<><~~~<><~~~<><~~~<><~~~ 

Back to top 


 soduko
 Joined: 10 Oct 2005  Posts: 50  :   Items 

Posted: Sat Jun 27, 2009 7:42 pm Post subject: oops little setback 


oops encountered a little setback.
my program will not solve the easter monster yet.
luckely i have one final bit of logic to include
looks a bit like this
if there is an constraint (p7,p8,p9 ....)
and p1 > p7
and p8 > p5
and p9 > p5
then p1 > p5
tried to program it but was a bit to tired while doing it.
but at least this gives also a bit a flavour of how the program works...
TO BE CONTINIUED 

Back to top 


 Adak
 Joined: 27 Feb 2008  Posts: 87  :   Items 

Posted: Sat Jun 27, 2009 10:47 pm Post subject: 


I have a QuickBasic compiler. I'd be glad to make an executable of your program.
That will speed it up! 

Back to top 


 soduko
 Joined: 10 Oct 2005  Posts: 50  :   Items 

Posted: Fri Jul 03, 2009 12:20 pm Post subject: 


i am trying to let my program solve the Easter monster by logic alone
but it doesn't get far
It stops after reducing the number of candidates to 214 (not including givens) and does not find any new position.
Still have some ideas for improvement.
and maybe even a completely new structure.
Think the problem is hidden/naked triplets (and higher)
(the program doesn't know that 3 symbols just don't fit into 2 positions)
the library where i use the computer doesn't let me download or upload files, so unfortunedly i cannot post the sourcecode.
(and it still needs some cleaning as well) 

Back to top 


 strmckr
 Joined: 24 Apr 2009  Posts: 52  :   Items 

Posted: Sat Jul 04, 2009 2:52 am Post subject: 


options:
are open the file as a txt document then copy that txt into a post on here.
the problem with easter monster and a few other harder puzzles is the fact it cannot be be propagated by singlular clues.
it requires guessing 2/3 postions at the same time.
to force a contradiction. {zero solution states}
the back door size is m3.(3 clues at once to reduce to singles)
back tracking algoriths have a problem and take a longer time solving this puzzle as well.
id have to see how the source works to offer any assitance,
its deffintily not naked/hidden subsets
as you wouldnt be able to solve much of the top 50,000 list with that not working correctly. 

Back to top 


 soduko
 Joined: 10 Oct 2005  Posts: 50  :   Items 

Posted: Mon Jul 06, 2009 8:11 pm Post subject: 


forgot my usb key today (i would forget my head if it was not tightly connected....
the program needs only one extra clue after it has reduced the easter monster to only 214 candidates.
Fittables as i call them are a bit an extra stage on trebortables.
so hidden naked singles are not really a problem, the problem is hidden naked triplets and higher.
(doubles are easely converted to implications)
sorry for forgetting my usb key will publish the raw source code soon.
(but at the moment it is 81 k big)
i 

Back to top 


 coloin
 Joined: 05 May 2005  Posts: 97  :   Items 

Posted: Mon Jul 06, 2009 10:48 pm Post subject: 


I like the idea of this !
Can you examine all the [wrong] proposition pairs ?
If all wrong proposition pairs have difficult "solving" paths  then we have a hell of a puzzle !
strmckr wrote:  ................
the linked cells can be of any length and incorparte numorus techiques to further reduce the grid based on implications of a maksed subset state of constraints and can either
a: be the solution,
B: form a contradiction state or a mutistate. 
I dont think you will ever get a multistate
i dont think gsfs q2 examines all proposition pairs........
C 

Back to top 


 strmckr
 Joined: 24 Apr 2009  Posts: 52  :   Items 

Posted: Tue Jul 07, 2009 7:12 am Post subject: 


for hidden add in an extra set of tables
have them set as sums of the data per digit in a given r,c,B
my program does this fo
r hidden sets.
{its pascal code}
the sets pm array is my representaton of digits 19 at each cell}
Code:  begin
for N:=1 to 9 do {col}
For xs:=0 to 8 do
begin
temp:=0;
for ys:=0 to 8 do
begin
if pm[xs,ys,N]=n
then
temp:=1+ temp;
end;
if temp > 0
then
C[xs,N]:=temp
else
C[xs,N]:=0;
end;
for N:=1 to 9 do{row}
For ys:=0 to 8 do
begin
temp:=0;
for xs:=0 to 8 do
begin
if pm[xs,ys,N]=n
then
temp:=1+ temp;
end;
if temp > 0
then
R[ys,N]:=temp
else
R[ys,N]:=0;
end;
begin
for xb:= 0 to 2 do {box}
for yb:=0 to 2 do
begin
Bxy:=(xb+(yb*3));
For N:= 1 to 9 do
begin
temp:=0;
for it:=0 to 2 do
for i:=(xb*3) to 2+(xb*3) do
begin
Yn:=(it)+(yb*3);
if pm[I,yn,n]=N
then
temp:=1+ temp;
if temp <> 0
then
Box[bxy,N]:=Temp
else
box[bxy,N]:=0;
end;
end;
end;
end;
end; 
its an idea...{im sure the above can be condensed into a singular function}
from the precalculated states of r,c,b
you can call the hidden set to look for the row that has both n,n2 candiates >0 and <3 (pairs) and verify they only occur in 2 cells.
etc for each set type. 

Back to top 


 soduko
 Joined: 10 Oct 2005  Posts: 50  :   Items 

Posted: Fri Jul 10, 2009 4:33 pm Post subject: 


Thanks for the code,
But it is hard to set it over to the data structure of my program.
(The program has no idea about houses and even cels are not really things the solver understand it only knows about placements (R1C1=1 R1C1=2 .... R2C1=5 .... R9C9=9) (in total 81* 9 = 729
and
Constraints (a test that needs to be satisfied 1 time only)
examples
R1C1 (one placement in cel R1C1
R1=8 (one 8 in row 1)
C3=6 ( a 6 in collumn 3)
B3=4 ( a 4 in minigrid (box) 3)
in total there are 81 * 4 = 324 constraints
every constraint has a list of all placements that can fulfil that constraint.
and the rest of the solver is all (implication) logic
at the moment I do it mainly with two big ish tables
729 * 81 for positive implications (if r1c1=1 forces R3C3=5 then
PITarray (r1c1=1,R3C3) = R3C3=5
and
a FIT array that also does negative implications
r1c1=1 blockes R1C1=2 (if not you could have an 1 and a 2 at the same place)
Fittable (r1c1=1, R1C1=2) = blocked
Fittable (r1c1=1, R3C3=1) = blocked
if r1c1=1 forces R3C3=5 then
FITtable(r1c1=1,R3C3=6) = implies
and so on
the problem is that qb cannot hadle arrays that are 729 x 729 big (Or have i just not enough memory, there are many other arrays as well in the program) so had to reduce the fittable to 244 * 244
and had to do some tricks to make it fit.
at the moment all is just integer (2 bytes per value) but i guess i can reduce itr to 1 bit per value in the fittable (only the negative implications there)
but my main purpose is just to get it working.
than to get it working fast. 

Back to top 


 strmckr
 Joined: 24 Apr 2009  Posts: 52  :   Items 

Posted: Fri Jul 10, 2009 6:43 pm Post subject: 


i know that most solvers use
RC,Rn,Cn,Bn as seperated arrays to represent the grid as well.
as 4 x,y,N(19) arrays
where 19 are on and off given restraints of placements or logic structers.
im not sure exactly how your storing the data ?
with this method its easier to identify constraints of houses a bit easier... 

Back to top 


