Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

fittable solver
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
soduko

Joined: 10 Oct 2005
Posts: 50
:

Items
PostPosted: Wed Jun 24, 2009 11:40 am    Post subject: fittable solver Reply with quote

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
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Wed Jun 24, 2009 8:22 pm    Post subject: Reply with quote

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
View user's profile Send private message
ChPicard

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

Items
PostPosted: Wed Jun 24, 2009 11:56 pm    Post subject: Re: fittable solver Reply with quote

soduko wrote:
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.



Is your solver fast?

Compare with these:

http://www.setbb.com/sudoku/viewtopic.php?t=1664&start=0&postdays=0&postorder=asc&highlight=&mforum=sudoku
Back to top
View user's profile Send private message
strmckr

Joined: 24 Apr 2009
Posts: 52
:

Items
PostPosted: Thu Jun 25, 2009 9:00 am    Post subject: Reply with quote

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
View user's profile Send private message
soduko

Joined: 10 Oct 2005
Posts: 50
:

Items
PostPosted: Thu Jun 25, 2009 5:19 pm    Post subject: Reply with quote

at the moment it does 1-4 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
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Thu Jun 25, 2009 6:36 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
soduko

Joined: 10 Oct 2005
Posts: 50
:

Items
PostPosted: Sat Jun 27, 2009 7:42 pm    Post subject: oops little setback Reply with quote

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
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Sat Jun 27, 2009 10:47 pm    Post subject: Reply with quote

I have a QuickBasic compiler. I'd be glad to make an executable of your program.

That will speed it up! Cool
Back to top
View user's profile Send private message
soduko

Joined: 10 Oct 2005
Posts: 50
:

Items
PostPosted: Fri Jul 03, 2009 12:20 pm    Post subject: Reply with quote

i am trying to let my program solve the Easter monster by logic alone

but it doesn't get far Crying or Very sad

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. Twisted Evil

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
View user's profile Send private message
strmckr

Joined: 24 Apr 2009
Posts: 52
:

Items
PostPosted: Sat Jul 04, 2009 2:52 am    Post subject: Reply with quote

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
View user's profile Send private message
soduko

Joined: 10 Oct 2005
Posts: 50
:

Items
PostPosted: Mon Jul 06, 2009 8:11 pm    Post subject: Reply with quote

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
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Mon Jul 06, 2009 10:48 pm    Post subject: Reply with quote

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 Exclamation Very Happy

i dont think gsfs -q2 examines all proposition pairs........

C
Back to top
View user's profile Send private message
strmckr

Joined: 24 Apr 2009
Posts: 52
:

Items
PostPosted: Tue Jul 07, 2009 7:12 am    Post subject: Reply with quote

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 1-9 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
View user's profile Send private message
soduko

Joined: 10 Oct 2005
Posts: 50
:

Items
PostPosted: Fri Jul 10, 2009 4:33 pm    Post subject: Reply with quote

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
View user's profile Send private message
strmckr

Joined: 24 Apr 2009
Posts: 52
:

Items
PostPosted: Fri Jul 10, 2009 6:43 pm    Post subject: Reply with quote

i know that most solvers use

RC,Rn,Cn,Bn as seperated arrays to represent the grid as well.

as 4 x,y,N(1-9) arrays

where 1-9 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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron