fittable solver

soduko · 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

Adak · 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.

ChPicard · Posted: Wed Jun 24, 2009 11:56 pm Post subject: Re: fittable solver

strmckr · 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.

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

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.

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

soduko · 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

Adak · 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! Cool

soduko · 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 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)

strmckr · 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.

soduko · 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

coloin · 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 · 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 1-9 at each cell}

soduko · 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.

strmckr · 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(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...