| View previous topic :: View next topic |
| Author |
Message |
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
 Posted: Wed Jan 25, 2006 6:18 am Post subject: sudoku (9x9) and sudocoup (NxN/QWH) solver/generators |
 |
|
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 |
|
 |
| ChPicard
| | Joined: 12 Mar 2008 | | Posts: 82 | | : | | Location: Montreal, Canada |
Items |
|
| Posted: Wed Apr 02, 2008 8:26 pm Post subject: Sudocoup (NxN/QWH) solver/generators |
|
|
| 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 |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Wed Apr 02, 2008 10:37 pm Post subject: Re: Sudocoup (NxN/QWH) solver/generators |
|
|
| 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 |
|
|
| serbo
| | Joined: 22 Dec 2008 | | Posts: 6 | | : | |
Items |
|
| Posted: Fri Jan 02, 2009 3:27 pm Post subject: gsf's solver explained |
|
|
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  |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Sat Jan 03, 2009 5:38 am Post subject: Re: gsf's solver explained |
|
|
| 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 |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
