
View previous topic :: View next topic 
Author 
Message 
 ChPicard
 Joined: 12 Mar 2008  Posts: 82  :  Location: Montreal, Canada  Items 

Posted: Sat Jan 17, 2009 3:07 pm Post subject: Canonicalize again and again! 


Lummox JR wrote:  I think I understand gsf's algorithm from the source code, now, well enough to explain it here.
Let's start with terminology. The sudoku is NxN in size, and PQ=N, where P>=Q, but P and Q are as close to each other as possible. If N is a square number, like in a standard 9x9 sudoku, P=Q. The boxes are arranged such that each is P columns by Q rows.
Each column or row of entire boxes we'll call a band. The Pbands will be P boxes stacked to PxN in size, and the Qbands are Q boxes stacked to QxN in size. If you prefer, think of these as towers and slabs, respectively.
Step 1: "Loop A". Loop through each box, and each orientation (original or transposed). 
Loop A: What for and how?
Lummox JR wrote:  This is 2N iterations if P=Q (that is, 18 for a 9x9 puzzle), or N iterations otherwise; ignore transposition if P=Q. Move the chosen box to the box 1 position by transposing the puzzle if necessary, then swapping P and Qbands till they reach the desired position. 
How to choose the good box?
Lummox JR wrote:  Step 2: "Loop B". Loop through each permutation of the columns and rows in box 1. This is P!Q! iterations, which in a 9x9 puzzle is 3!3!=36. 
Loop B: What for?
Thank you very much for explanations. 

Back to top 


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

Posted: Sat Jan 17, 2009 3:10 pm Post subject: Canonization again and again! 


Lummox JR wrote:  I think I understand gsf's algorithm from the source code, now, well enough to explain it here.
Let's start with terminology. The sudoku is NxN in size, and PQ=N, where P>=Q, but P and Q are as close to each other as possible. If N is a square number, like in a standard 9x9 sudoku, P=Q. The boxes are arranged such that each is P columns by Q rows.
Each column or row of entire boxes we'll call a band. The Pbands will be P boxes stacked to PxN in size, and the Qbands are Q boxes stacked to QxN in size. If you prefer, think of these as towers and slabs, respectively.
Step 1: "Loop A". Loop through each box, and each orientation (original or transposed). 
Loop A: What for and how?
Lummox JR wrote:  This is 2N iterations if P=Q (that is, 18 for a 9x9 puzzle), or N iterations otherwise; ignore transposition if P=Q. Move the chosen box to the box 1 position by transposing the puzzle if necessary, then swapping P and Qbands till they reach the desired position. 
How to choose the good box?
Lummox JR wrote:  Step 2: "Loop B". Loop through each permutation of the columns and rows in box 1. This is P!Q! iterations, which in a 9x9 puzzle is 3!3!=36. 
Loop B: What for?
Thank you very much for explanations. 

Back to top 


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

Posted: Sat Jan 17, 2009 3:12 pm Post subject: Canonization again and again! 


Lummox JR wrote:  I think I understand gsf's algorithm from the source code, now, well enough to explain it here.
Let's start with terminology. The sudoku is NxN in size, and PQ=N, where P>=Q, but P and Q are as close to each other as possible. If N is a square number, like in a standard 9x9 sudoku, P=Q. The boxes are arranged such that each is P columns by Q rows.
Each column or row of entire boxes we'll call a band. The Pbands will be P boxes stacked to PxN in size, and the Qbands are Q boxes stacked to QxN in size. If you prefer, think of these as towers and slabs, respectively.
Step 1: "Loop A". Loop through each box, and each orientation (original or transposed). 
Loop A: What for and how?
Lummox JR wrote:  This is 2N iterations if P=Q (that is, 18 for a 9x9 puzzle), or N iterations otherwise; ignore transposition if P=Q. Move the chosen box to the box 1 position by transposing the puzzle if necessary, then swapping P and Qbands till they reach the desired position. 
How to choose the good box?
Lummox JR wrote:  Step 2: "Loop B". Loop through each permutation of the columns and rows in box 1. This is P!Q! iterations, which in a 9x9 puzzle is 3!3!=36. 
Loop B: What for?
Thank you very much for explanations. 

Back to top 


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

Posted: Sat Jan 17, 2009 5:13 pm Post subject: Canonicalization again and again! 


Lummox JR wrote:  I think I understand gsf's algorithm from the source code, now, well enough to explain it here.
Let's start with terminology. The sudoku is NxN in size, and PQ=N, where P>=Q, but P and Q are as close to each other as possible. If N is a square number, like in a standard 9x9 sudoku, P=Q. The boxes are arranged such that each is P columns by Q rows.
Each column or row of entire boxes we'll call a band. The Pbands will be P boxes stacked to PxN in size, and the Qbands are Q boxes stacked to QxN in size. If you prefer, think of these as towers and slabs, respectively.
Step 1: "Loop A". Loop through each box, and each orientation (original or transposed). 
Loop A: What for and how?
Lummox JR wrote:  This is 2N iterations if P=Q (that is, 18 for a 9x9 puzzle), or N iterations otherwise; ignore transposition if P=Q. Move the chosen box to the box 1 position by transposing the puzzle if necessary, then swapping P and Qbands till they reach the desired position. 
How to choose the good box?
Lummox JR wrote:  Step 2: "Loop B". Loop through each permutation of the columns and rows in box 1. This is P!Q! iterations, which in a 9x9 puzzle is 3!3!=36. 
Loop B: What for?
Thank you very much for explanations. 

Back to top 


 gsf
 Joined: 18 Aug 2005  Posts: 408  :  Location: NJ USA  Items 

Posted: Sat Jan 17, 2009 11:45 pm Post subject: Re: Canonicalization again and again! 


[ flurry of multiple duplicate posts across the forum ]
recently when I submit a post I get a debug screen that says the post failed
when in fact the post worked
I suspect others have experienced the same
re lummoxjr's comments
read further on in the thread
we determined that the boxbybox alg could be modified to rowbyrow without loss of efficiency
rowbyrow has the benefit of producing an easy to describe and easy
to understand canonical form: row order minlex w.r.t the solution grid 

Back to top 


 Adak
 Joined: 27 Feb 2008  Posts: 87  :   Items 

Posted: Sun Jan 18, 2009 7:02 am Post subject: 


Code: 
===*===*====
000000000
000000001
000001000
++
000000000
000000002
001000000
++
000000000
000002134
123456789
===+===+===

Is this the lowest row min grid possible for 17 givens that could be listed, before any solution testing was done?
Taking into account the requirements for a valid Sudoku grid:
1) No stack or band with 2 empty boxes
2) No two empty columns or rows within any stack/band
3) A valid grid must have at least 8 of the 9 digits as givens
I've read that up to 4 empty boxes (houses), can be allowed and still have a valid Sudoku puzzle. If so, that violates #1, above. 

Back to top 


 m_b_metcalf
 Joined: 13 Mar 2006  Posts: 210  :  Location: Berlin  Items 

Posted: Mon Jan 19, 2009 8:35 am Post subject: 


Adak wrote: 
1) No stack or band with 2 empty boxes
...
I've read that up to 4 empty boxes (houses), can be allowed and still have a valid Sudoku puzzle. If so, that violates #1, above. 
A discussion on empty boxes can be found here. That allows 4 empty boxes altogether, and such beasts exist.
Regards,
Mike Metcalf 

Back to top 


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

Posted: Mon Jan 19, 2009 7:02 pm Post subject: Canonicalization again and again! 


Lummox JR wrote:  I think I understand gsf's algorithm from the source code, now, well enough to explain it here.
Let's start with terminology. The sudoku is NxN in size, and PQ=N, where P>=Q, but P and Q are as close to each other as possible. If N is a square number, like in a standard 9x9 sudoku, P=Q. The boxes are arranged such that each is P columns by Q rows.
Each column or row of entire boxes we'll call a band. The Pbands will be P boxes stacked to PxN in size, and the Qbands are Q boxes stacked to QxN in size. If you prefer, think of these as towers and slabs, respectively.
Step 1: "Loop A". Loop through each box, and each orientation (original or transposed). 
What is it done in Loop A and how?
Lummox JR wrote:  This is 2N iterations if P=Q (that is, 18 for a 9x9 puzzle), or N iterations otherwise; ignore transposition if P=Q. Move the chosen box to the box 1 position by transposing the puzzle if necessary, then swapping P and Qbands till they reach the desired position. 
How to choose the good box?
Lummox JR wrote:  Step 2: "Loop B". Loop through each permutation of the columns and rows in box 1. This is P!Q! iterations, which in a 9x9 puzzle is 3!3!=36. 
Loop B: What for?
Thank you very much for explanations. 

Back to top 


 tarek
 Joined: 31 Dec 2005  Posts: 153  :  Location: London, UK  Items 

Posted: Mon Jan 19, 2009 9:01 pm Post subject: 


ChPicard,
Why are you repeating the same post again & again, you don't need to shout out loud to get noticed.
If somebody ignored you the 1st time, the constant shouting will not get you anywhere. Be patient.
tarek 

Back to top 


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

Posted: Tue Jan 20, 2009 12:59 pm Post subject: Sorry but I was told ERROR 


tarek wrote:  ChPicard,
Why are you repeating the same post again & again, you don't need to shout out loud to get noticed.
If somebody ignored you the 1st time, the constant shouting will not get you anywhere. Be patient.
tarek 
Sorry but I was told ERROR 

Back to top 


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

Posted: Fri Jan 23, 2009 11:37 pm Post subject: Find the smallest digit in row 1 that is not in box 1 !!! 


Lummox Jr wrote:
Quote:  Step 4: Find the smallest digit in row 1 that is not in box 1. 
Think about it one minute.
How could it be possible? Because in each box, there are all digits from 1 to 9.
Thanks Lummox Jr for the effort but it is impossible to understand your explanation. The word LOOP has many meanings, the word ITERATE too. 

Back to top 


 gsf
 Joined: 18 Aug 2005  Posts: 408  :  Location: NJ USA  Items 

Posted: Sat Jan 24, 2009 4:51 pm Post subject: Re: Find the smallest digit in row 1 that is not in box 1 !! 


ChPicard wrote:  Lummox Jr wrote:
Quote:  Step 4: Find the smallest digit in row 1 that is not in box 1. 
Think about it one minute.
How could it be possible? Because in each box, there are all digits from 1 to 9.
Thanks Lummox Jr for the effort but it is impossible to understand your explanation. The word LOOP has many meanings, the word ITERATE too. 
lummoxjr is referring to source code that I either posted on the forum or on a web site
if you find the reference to that code I will help decipher 

Back to top 


 ThemePark
 Joined: 22 Mar 2009  Posts: 17  :   Items 

Posted: Sun Mar 22, 2009 2:03 pm Post subject: 


Since this thread has been brought back from the dead by someone else, I suppose there is no harm in posting here to ask some questions.
Specifically, I am curious about this algorithm that Red Ed mentions. How can it be possible that there are at most 648 transformations of a solution grid, when I've read elsewhere that there are 9!*3!*3!*3*3!*3!*3*2 transformation. Or does the number 648 only refer to the automorphic solution grids? 

Back to top 


 JPF
 Joined: 05 Dec 2005  Posts: 29  :  Location: Paris  Items 

Posted: Tue Mar 24, 2009 5:47 pm Post subject: 


648 is the maximum number of automorphisms of a solution grid.
There is only one grid (up to isomorphism) having this property, named the Most Canonical grid (MC)
Here is the MC grid :
Code:  **
123456789
456789123
789123456
++
231564897
564897231
897231564
++
312645978
645978312
978312645
** 
For more informations on automorphisms, you may have a look at :
JPF 

Back to top 




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

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
