Sudoku Programmers :: View topic

FAQ

Memberlist

Usergroups

Profile

Unique puzzle
Goto page Previous 1, 2

Sudoku Programmers Forum Index -> Setting sudoku

View previous topic :: View next topic

Author

Message

eclark

Joined: 28 Dec 2005

Posts: 70

Items

Posted: Mon Jan 30, 2006 10:53 pm Post subject:

no, thats the way gsf's program outputs stuff a stands for 1 b for 2 and so on

gsf

Joined: 18 Aug 2005

Posts: 411

Location: NJ USA

Items

Posted: Tue Jan 31, 2006 4:59 am Post subject:

tarek wrote:

gsf wrote:

there's a disconnect somewhere
the canonical ordering must take into account 90 deg rotation
and all other symmetry transforms and cell relabeling

Yes it should, but the method you just described produces 2 different canonical orderings, one for columns & one for rows (I Think Rolling Eyes

)

The output from your program is which one ?

still a disconnect
the canonicalization algorithm can be implemented as nested loops over row/col/box/label permutations
where the output is one permutation of cell indexes and one permutation of cell labels
I originally forgot to include 90 deg rotation in the description
that can be done by adding additional permutations to the outermost loop
the algorithm ends up checking more permutations
but it still outputs only one answer

gsf

Joined: 18 Aug 2005

Posts: 411

Location: NJ USA

Items

Posted: Tue Jan 31, 2006 5:01 am Post subject:

eclark wrote:

Ok so we are trying to find the answer that is as close as possible to
12345678912345..... as possbible ? or am I tottally off ?

close -- the top box is fixed at

Code:

1 2 3
4 5 6
7 8 9

not the top row

gsf

Joined: 18 Aug 2005

Posts: 411

Location: NJ USA

Items

Posted: Tue Jan 31, 2006 5:45 am Post subject:

tarek wrote:

The setting you chose eclark is probably for a 16*16 sudoku, you should only have 1-9 in a 9*9 sudoku

for 9x9 sudoku the %c format prints the canonical puzzle with solution cells labeled A-I (for 1-9) instead of .
this allows one 81 char string to represent both the original puzzle and the solution

given eclark's puzzle

Code:

. . . | . 6 . | . . 3
. . 4 | . 1 . | . . .
. 6 3 | 8 5 . | . 2 .
-------+-------+------
4 . 5 | . . 3 | . . 2
7 . . | . 8 . | 5 . .
. 2 . | . . . | . 1 6
-------+-------+------
. . . | . . . | 4 . .
. . . | . . 8 | . . .
5 . . | . 3 . | 6 . 9

this pipeline

Code:

sudoku -f%c eclark.dat |
sudoku -f%#.c%.%c%.%C%.%#pg%#Pg

produces

Code:

12....7...5...9.32....3...6..4....9..9.6724......4.......19..7.....2...3.7....81.
12CDEF7HID5FGH9A32GHIB3AED6BF4HAEC9GC9H6724EAEAGI4CFBHFCE19HB7DHDAE2GIF3I7BCFD81E
123456789456789132789231546264815397398672451517943628635198274841527963972364815

1 2 . | . . . | 7 . .
. 5 . | . . 9 | . 3 2
. . . | . 3 . | . . 6
------+-------+------
. . 4 | . . . | . 9 .
. 9 . | 6 7 2 | 4 . .
. . . | . 4 . | . . .
------+-------+------
. . . | 1 9 . | . 7 .
. . . | . 2 . | . . 3
. 7 . | . . . | 8 1 .

1 2 3 | 4 5 6 | 7 8 9
4 5 6 | 7 8 9 | 1 3 2
7 8 9 | 2 3 1 | 5 4 6
------+-------+------
2 6 4 | 8 1 5 | 3 9 7
3 9 8 | 6 7 2 | 4 5 1
5 1 7 | 9 4 3 | 6 2 8
------+-------+------
6 3 5 | 1 9 8 | 2 7 4
8 4 1 | 5 2 7 | 9 6 3
9 7 2 | 3 6 4 | 8 1 5

the first command canonicalizes the puzzle
the second command prints the canonical puzzle in different formats

a canonicalization algorithm must produce the same order and labeling
for any valid permutation/relabeling/rotation of a given grid
otherwise its not canonical

the following puzzle (the above rotated pi/2)

Code:

5 . . | . 7 4 | . . .
. . . | 2 . . | 6 . .
. . . | . . 5 | 3 4 .
------+-------+------
. . . | . . . | 8 . .
3 . . | . 8 . | 5 1 6
. 8 . | . . 3 | . . .
------+-------+------
6 . 4 | . 5 . | . . .
. . . | 1 . . | 2 . .
9 . . | 6 . 2 | . . 3

produces the same results

tarek

Joined: 31 Dec 2005

Posts: 153

Location: London, UK

Items

Posted: Tue Jan 31, 2006 10:11 am Post subject:

Thanx gsf, I must have missed something during the previous posts. I'll give it a try using 2 loops (one for columns & one for rows & see how it goes) Tarek

eclark

Joined: 28 Dec 2005

Posts: 70

Items

Posted: Tue Jan 31, 2006 2:54 pm Post subject:

I asked this question over at the sudoku players forum and I got a (what I think anyway) is a very good answer here: http://sudoku.com/forums/viewtopic.php?t=3054

gsf

Joined: 18 Aug 2005

Posts: 411

Location: NJ USA

Items

Posted: Tue Jan 31, 2006 5:52 pm Post subject:

eclark wrote:

I asked this question over at the sudoku players forum and I got a (what I think anyway) is a very good answer

here: http://sudoku.com/forums/viewtopic.php?t=3054

thanks
the upshot is that in this thread I have been describing a canonicalization method,
not the canonicalization method

eclark

Joined: 28 Dec 2005

Posts: 70

Items

Posted: Tue Jan 31, 2006 11:42 pm Post subject:

gsf wrote:

eclark wrote:

I asked this question over at the sudoku players forum and I got a (what I think anyway) is a very good answer

here: http://sudoku.com/forums/viewtopic.php?t=3054

thanks
the upshot is that in this thread I have been describing a canonicalization method,
not the canonicalization method

yep though one that seems pretty ok to me.
I actually think I might use the nauty utility if I can get it working right.

http://www.cs.sunysb.edu/~algorith/implement/nauty/implement.shtml
http://cs.anu.edu.au/people/bdm/

Display posts from previous:

	Sudoku Programmers Forum Index -> Setting sudoku	All times are GMT Goto page Previous 1, 2
Page 2 of 2

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