|
| 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 P-bands will be P boxes stacked to PxN in size, and the Q-bands 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 Q-bands 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 P-bands will be P boxes stacked to PxN in size, and the Q-bands 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 Q-bands 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 P-bands will be P boxes stacked to PxN in size, and the Q-bands 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 Q-bands 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 P-bands will be P boxes stacked to PxN in size, and the Q-bands 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 Q-bands 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: 411 | | : | | 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 box-by-box alg could be modified to row-by-row without loss of efficiency
row-by-row 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: |
===*===*====
000|000|000
000|000|001
000|001|000
---+---+---
000|000|000
000|000|002
001|000|000
---+---+---
000|000|000
000|002|134
123|456|789
===+===+===
|
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 P-bands will be P boxes stacked to PxN in size, and the Q-bands 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 Q-bands 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: 411 | | : | | 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: | *-----------*
|123|456|789|
|456|789|123|
|789|123|456|
|---+---+---|
|231|564|897|
|564|897|231|
|897|231|564|
|---+---+---|
|312|645|978|
|645|978|312|
|978|312|645|
*-----------* |
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 |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
