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   

Canonical sudoku algorithm?
Goto page Previous  1, 2, 3, 4, 5, 6
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
ChPicard

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

Items
PostPosted: Sat Jan 17, 2009 3:07 pm    Post subject: Canonicalize again and again! Reply with quote

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
View user's profile Send private message
ChPicard

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

Items
PostPosted: Sat Jan 17, 2009 3:10 pm    Post subject: Canonization again and again! Reply with quote

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
View user's profile Send private message
ChPicard

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

Items
PostPosted: Sat Jan 17, 2009 3:12 pm    Post subject: Canonization again and again! Reply with quote

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
View user's profile Send private message
ChPicard

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

Items
PostPosted: Sat Jan 17, 2009 5:13 pm    Post subject: Canonicalization again and again! Reply with quote

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
View user's profile Send private message
gsf

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

Items
PostPosted: Sat Jan 17, 2009 11:45 pm    Post subject: Re: Canonicalization again and again! Reply with quote

[ 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
View user's profile Send private message Visit poster's website
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Sun Jan 18, 2009 7:02 am    Post subject: Reply with quote

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
View user's profile Send private message
m_b_metcalf

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

Items
PostPosted: Mon Jan 19, 2009 8:35 am    Post subject: Reply with quote

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
View user's profile Send private message
ChPicard

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

Items
PostPosted: Mon Jan 19, 2009 7:02 pm    Post subject: Canonicalization again and again! Reply with quote

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
View user's profile Send private message
tarek

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

Items
PostPosted: Mon Jan 19, 2009 9:01 pm    Post subject: Reply with quote

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
View user's profile Send private message
ChPicard

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

Items
PostPosted: Tue Jan 20, 2009 12:59 pm    Post subject: Sorry but I was told ERROR Reply with quote

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
View user's profile Send private message
ChPicard

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

Items
PostPosted: Fri Jan 23, 2009 11:37 pm    Post subject: Find the smallest digit in row 1 that is not in box 1 !!! Reply with quote

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
View user's profile Send private message
gsf

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

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

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
View user's profile Send private message Visit poster's website
ThemePark

Joined: 22 Mar 2009
Posts: 17
:

Items
PostPosted: Sun Mar 22, 2009 2:03 pm    Post subject: Reply with quote

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
View user's profile Send private message
JPF

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

Items
PostPosted: Tue Mar 24, 2009 5:47 pm    Post subject: Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Goto page Previous  1, 2, 3, 4, 5, 6
Page 6 of 6

 
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