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   

sudoku (9x9) and sudocoup (NxN/QWH) solver/generators

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Software
View previous topic :: View next topic  
Author Message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Wed Jan 25, 2006 6:18 am    Post subject: sudoku (9x9) and sudocoup (NxN/QWH) solver/generators Reply with quote

common public license (cpl1.0) source for two command line
solver generators has been posted at
http://www.research.att.com/sw/download/tgz/ast-sudoku.2006-01-24.tgz
even though it is open source there is a license handshake
for rationale see
http://www.research.att.com/sw/download/faq.license.html

sudoku is a 9x9 technique based solver/generator
I stopped coding new techniques at x-cycles (~simple coloring)

sudocoup is an NxN sudoku/QWH solver/generator coded for speed
its a backtrack solver, but solves most 9x9 sudoku without backtracking
using a 1 level forward check

for a refreshing change neither solver employs dancing links
Back to top
View user's profile Send private message Visit poster's website
ChPicard

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

Items
PostPosted: Wed Apr 02, 2008 8:26 pm    Post subject: Sudocoup (NxN/QWH) solver/generators Reply with quote

gsf wrote:

sudocoup is an NxN sudoku/QWH solver/generator coded for speed
its a backtrack solver, but solves most 9x9 sudoku without backtracking
using a 1 level forward check


Hi

Is sudocoup available? I can't download it.

Thanks
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Wed Apr 02, 2008 10:37 pm    Post subject: Re: Sudocoup (NxN/QWH) solver/generators Reply with quote

ChPicard wrote:
gsf wrote:

sudocoup is an NxN sudoku/QWH solver/generator coded for speed
its a backtrack solver, but solves most 9x9 sudoku without backtracking
using a 1 level forward check

Is sudocoup available? I can't download it.

got to http://www.research.att.com/sw/download/ and hit the ast-sudoku link
to see the latest available source tarball release
Back to top
View user's profile Send private message Visit poster's website
serbo

Joined: 22 Dec 2008
Posts: 6
:

Items
PostPosted: Fri Jan 02, 2009 3:27 pm    Post subject: gsf's solver explained Reply with quote

I am using this version of solver:
Code:

$ sudoku-linux.i386 -V
sudoku (AT&T Research) 2008-09-10

First let me point out some inconsistencies in order that solving
techniques are applied.
When I have puzzle:
Code:

..6...1.3...4...65..36.9.4.3..25......4...7......43..1.8.3.56..62...8...7.9...2..

this is what I get for different constraint allowed to use:
Code:

$ sudoku-linux.i386 -f%Q
  777 FNW         C28.M/S2.p/F7.43/N1.10/W1.2.1
$ sudoku-linux.i386 -f%Q -qFNBTH
   42 FNT         C28.M/S2.p/F6.35/N2.18/T1.2.0.1
$ sudoku-linux.i386 -f%Q -qFNBTHW
  777 FNW         C28.M/S2.p/F7.43/N1.10/W1.2.1

Here you can see that W is used out of order.

Another issue is when puzzle has X or Y cycles (like next one). Scoring is very different when -v2 option is used:
Code:

.23.....76.....23.....36......9..87.97.5.8.61.86..7......75.....95.....23.....95.


Code:

$ sudoku-linux.i386  -f%Q
 6677 FNBWX       C28.M/S2.p/F5.21/N4.26/B2.6.4.2/W2.4.0.1.1/X2.16

$ sudoku-linux.i386  -f%Q  -v2
[1]  N18 [17][45][84][99]=6 [34][68]=2 [57][64][86][42][79]=3 [76][15][69]=9
         [93][31][25][87]=7
     N3  [23][38]=9 [72]=6
         box-line 8 b/2    [44][54][64][74][84][94]
         box-line 5 b/2    [11][21][31][71][81][91]
         box-line 8 b/2    [18][28][38][48][58][68]
         box-line 8 r/3    [74][75][76][84][85][86]
     B4  [94][18][85]^8 [11]^5
     N4  [16]=5 [95]=8 [55][96]=2
     F1  [53]=4
         x-cycle  1  1  4a [22]-[94][92]-
         x-cycle  2  4  4a [14]-[92][94]-
         x-cycle  3  4  4a [22]-[94][92]-
     X3  [22]^1 [14][22]^4
     F1  [22]=5
         box-line 4 b/2    [21][22][23][27][28][29]
         box-line 1 r/3    [14][15][16][34][35][36]
     B2  [29]^4 [14]^1
     F2  [14][29]=8
     N1  [33]=8
         x-wing   4 1 r/3  [11][15][18]/[61][65][68]/[81][85][88]
     W3  [41][71][78]^1
         x-wing   5 4 r/4  [11][15][17][18]/[61][65][67][68]/[71][75][77][78]/[81][85][87][88]
     W1  [37]^4
         x-cycle  6  1  7e [18][11][32][92][94][85]-[88]  =>  [18][11][94]=
         x-cycle  7  1  9a [24][94][92][32][11][61][43][46][26]  =>  [24][18]=[26]
         x-cycle  8  1  3c [32]=[26][92]
         x-cycle  9  1  3f [37][26][73]-
         x-cycle 10  1  9b [43][46][26][24][94][92][32][11]-[61]  =>  [43][37]-[61]
         x-cycle 11  1  3d [46]-[37][65]
         x-cycle 12  1  3d [61]-[46][32]
         x-cycle 13  1  3c [65]=[43][85]
         x-cycle 14  1 12c [77][37][18][11][32][92][94][24][26][46][43][73]  =>  [77]=[65][73]
         x-cycle 15  1  3d [92]-[88][94]
         x-cycle 16  4 10a [71]-[85][94][11][18]-[67][77]-  =>  [71]-[67][49]-
         x-cycle 17  4  9a [88]-[85][94][11][18]-[67][77]-  =>  [88]-[67][49]-
         x-cycle 18  1  4d [11][18][37][32]  =>  [11]-[92][77]
     X13 [11][24][92][85][73]^1 [26][43][65][32][94][77]=1 [71][88]^4
     F13 [11][24][39][46][67][85][92]=4 [18]=1 [37][49][61]=5 [73]=2 [88]=8
     F4  [41]=2 [71]=8 [78]=4 [81]=1
     S
16149 FNBWX       C28.M/S2.p/F5.21/N4.26/B2.6.4.2/W2.4.0.1.1/X2.16.12.6.5.4.1

Note the differences between two scores (6677 and 16149). Which one is right? Also note that most of 6677 is from swordfish and jellyfish that are in that puzzle.

If I have puzzle without fishes the difference is much more exposed as in this puzzle with Y cycle:
Code:

.9..4....31...58.64....7...1...8.7....31.45....9.5...1...3....89.84...73....1..6.


Code:

$ sudoku-linux.i386 -f%Q
  261 FNY         C28.M/S2.p/F1.9/N2.37/Y1.14

$ sudoku-linux.i386 -f%Q -v2
[1]  N22 [28][49]=4 [23][19][75]=7 [87][73][16][38]=1
         [82][11][43][94][39][78]=5 [92][35]=3 [67]=6 [32][14][96]=8 [37]=9
     N15 [13][34]=6 [62][77][93]=4 [76][99]=9 [91][52][64]=7
         [33][59][18][97]=2 [17]=3
         y-cycle  1  2 14e [24][86][85]=[71][72][42]-[44]  =>  [24][86][85]=
         y-cycle  2  2  3d [25]-[71]=[24]
         y-cycle  3  2  3d [42]-[24]=[72]
         y-cycle  4  2 10b [61]=[25][24][44]>  =>  [61]=[25]-[44]>
         y-cycle  5  2  3c [72]=[61][42]
         y-cycle  6  2 20b [85]=[71][72][42]-[44][24][25]=[61][66]>  =>  [85]=[24]-[66]>
         y-cycle  7  3  5a [46][66]=[48]
         y-cycle  8  3  5c [66]=[48][68]
         y-cycle  9  3  3d [68]-[46][66]
         y-cycle 10  6  3a [46][71]=[42]
         y-cycle 11  6  3d [51]-[46][71]
         y-cycle 12  6  3d [72]-[51][86]
         y-cycle 13  9  6a [48][44]>[58]
         y-cycle 14  9  6a [55][44]>[58]
     Y14 [86][42]^2 [24][72][61][85]=2 [46][68]^3 [66]=3 [46]^6 [71][86]=6
         [48][55]^9
     F9  [25][44][58]=9 [42][55]=6 [46]=2 [48]=3 [51][68]=8
     S
21637 FNY         C28.M/S2.p/F1.9/N2.37/Y1.14.20.7.4.1.1.0.1


Now comes my real questions.

How do I use -KCL and/or -kCR option to output cycle into ps file?
I want to see
Code:

         x-cycle  2  4  4a [14]-[92][94]-

from my second example. I have been reading manual many times and can not figure it out. Would you be so kind to show me exactly which option and how to use them along with -P and whatever else is needed?

(I have been looking at those tree cell in cycle for 1/2 hour until I recognized Empty Rectangle in box 1 - not very bright solver, am I?)

And what does that small letter means in cycle description (this one has 4a)?
4 should be number of nodes (is ER counted in as a node?)
What is 'a'? What does other letters mean?

This should be more than enough for one message Smile
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Sat Jan 03, 2009 5:38 am    Post subject: Re: gsf's solver explained Reply with quote

serbo wrote:
I am using this version of solver:
Code:

$ sudoku-linux.i386 -V
sudoku (AT&T Research) 2008-09-10

First let me point out some inconsistencies in order that solving
techniques are applied.
When I have puzzle:
Code:

..6...1.3...4...65..36.9.4.3..25......4...7......43..1.8.3.56..62...8...7.9...2..

this is what I get for different constraint allowed to use:
Code:

$ sudoku-linux.i386 -f%Q
  777 FNW         C28.M/S2.p/F7.43/N1.10/W1.2.1
$ sudoku-linux.i386 -f%Q -qFNBTH
   42 FNT         C28.M/S2.p/F6.35/N2.18/T1.2.0.1
$ sudoku-linux.i386 -f%Q -qFNBTHW
  777 FNW         C28.M/S2.p/F7.43/N1.10/W1.2.1

Here you can see that W is used out of order.

the constraint method letters are broken down by order
-f %#sQ lists the default constraint order with orders: FN{B2B3}T2H2W2T3H3W3T4H4W4XYKOG
this shows that W2 (x-wing) is attempted before T3 (naked triples)
if x-wings are not in scope then the puzzle can be solved with a naked triple
Quote:

Another issue is when puzzle has X or Y cycles (like next one). Scoring is very different when -v2 option is used:
Code:

.23.....76.....23.....36......9..87.97.5.8.61.86..7......75.....95.....23.....95.


that's a bug -- for consistent ratings don't use the -v option
Quote:

Now comes my real questions.

How do I use -KCL and/or -kCR option to output cycle into ps file?
I want to see
Code:

         x-cycle  2  4  4a [14]-[92][94]-

from my second example. I have been reading manual many times and can not figure it out. Would you be so kind to show me exactly which option and how to use them along with -P and whatever else is needed?

the XY code listing code stopped working when I changed the XY alg to use ternary cycles
I'll get back on that
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Software All times are GMT
Page 1 of 1

 
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