|
| View previous topic :: View next topic |
| Author |
Message |
| Ruud
Site Admin
 | | Joined: 17 Sep 2005 | | Posts: 708 | | : | | Location: Netherlands |
Items |
|
|
| Back to top |
|
 |
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
 Posted: Wed Mar 29, 2006 4:57 pm Post subject: |
 |
|
| Soultaker wrote: |
Didn't you forget to include swapping bands as permissable permutations?
|
yes
edited in
thanks |
|
| Back to top |
|
|
| Moschopulus
| | Joined: 12 Aug 2005 | | Posts: 39 | | : | |
Items |
|
| Posted: Wed Mar 29, 2006 7:30 pm Post subject: |
|
|
Have the questions been answered?
As I understand it,
To find the canonical form of a puzzle P, we do the following.
1. find the completion S of the puzzle P
2. find the canonical form C of S
3. perform the same operations on P that transform S to C
The result is the canonical form of P.
This reduces the problem to finding the canonical form of a completed grid, which can be done in different ways as mentioned in other posts. |
|
| Back to top |
|
|
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Wed Mar 29, 2006 8:13 pm Post subject: |
|
|
| gsf wrote: | | Lummox JR wrote: | | Step 7: At this point, compare N^2-digit number like in step 5. If this is lower, it is the new minimum and the best candidate so far for canonical form. If it is equal, then two different transforms have resulted in the same candidate canonical form, and this algorithm cannot be used to canonicalize a set of givens. |
good observation, wrong conclusion
if two different permutations of the same solution grid yield the same canonical grid
then an automorphism has been uncovered
the canonical form is not invalid
instead a special property of the grid has been uncovered
this is related to a key part of counting the number of essentially different sudoku solutions
the algorithm would have to change substantially to count all non-trivial automorphisms,
but a simple change (counter clear/increment at the end of the inner loop)
allows it to count the number of non-trivial automorphisms of the canonical solution grid
|
See, here's where you lose me. Moschopulus posted a puzzle that can be converted to an equivalent puzzle with the exact same solution. This is, as you say, an automorphism.
If your algorithm is used to find a canonical form for the solution grid, it will generate a particular sequence of permutations that can be applied to the original puzzle. The problem is, that exact same sequence would apply to the second puzzle which has different givens. Therefore, the two results would not be the same puzzle (merely equivalent forms), and though their solutions would be in canonical form, the givens would not. If you're counting automorphisms, do you also have some means of selecting between automorphic forms? How, in other words, can you find a canonical form which is valid for both of these:
| Code: | +-------+-------+-------+
| 1 . 4 | . . . | 8 9 . |
| 3 7 8 | 2 . . | . 1 . |
| . 5 . | 8 3 . | 7 . . |
+-------+-------+-------+
| 9 8 7 | . . . | . . . |
| . . . | . 5 . | . 7 . |
| . . . | . . 9 | 3 . . |
+-------+-------+-------+
| . 6 3 | . 7 . | . . . |
| 4 . . | . . 8 | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
+-------+-------+-------+
| . 2 . | . . 7 | . 9 3 |
| . . 8 | . . 4 | 5 1 . |
| . . 9 | . . 1 | . 4 2 |
+-------+-------+-------+
| . . . | . . . | 4 6 . |
| . . 1 | . 5 . | 9 . . |
| . 4 . | 7 . . | . . . |
+-------+-------+-------+
| . . . | 9 . . | 1 . 4 |
| . . . | . 1 . | . 3 7 |
| . . . | . . . | . . . |
+-------+-------+-------+ |
The two puzzles are equivalent, and have an identical solution. Therefore any method to find a canonical puzzle would have to take this into account. |
|
| Back to top |
|
|
| daj95376
| | Joined: 05 Feb 2006 | | Posts: 349 | | : | |
Items |
|
| Posted: Wed Mar 29, 2006 9:47 pm Post subject: |
|
|
| Moschopulus wrote: | Have the questions been answered?
As I understand it,
To find the canonical form of a puzzle P, we do the following.
1. find the completion S of the puzzle P
2. find the canonical form C of S
3. perform the same operations on P that transform S to C
The result is the canonical form of P.
This reduces the problem to finding the canonical form of a completed grid, which can be done in different ways as mentioned in other posts. |
I tried this and the results were questionable.
I randomly selected a puzzle from the top1465 and ran it through gsf's solver to perform the steps you listed above. I then ran QQwing -- with stats turned on -- to solve the original puzzle and the CNF puzzle.
Other than the number of givens matching and a zero value for Naked Pairs, none of the other counts (for techniques employed in solving the puzzles) matched. |
|
| Back to top |
|
|
| vidarino
| | Joined: 10 Feb 2006 | | Posts: 38 | | : | | Location: Haugesund, Norway |
Items |
|
| Posted: Wed Mar 29, 2006 9:57 pm Post subject: |
|
|
| daj95376 wrote: |
I tried this and the results were questionable.
I randomly selected a puzzle from the top1465 and ran it through gsf's solver to perform the steps you listed above. I then ran QQwing -- with stats turned on -- to solve the original puzzle and the CNF puzzle.
Other than the number of givens matching and a zero value for Naked Pairs, none of the other counts matched. |
That doesn't mean they're not equivalent. Pick a random puzzle and turn it upside down and compare the stats. Chances are that their stats will also differ, despite them obviously being equivalent.
The problem is that solvers start in one end of the puzzle (typically upper-left corner, I bet) when looking for whatever it is they look for (singles, pairs, etc.), and stop and act as soon as they find one. So when the puzzle is rotated or mirrored, other candidates are solved first, which makes the solver take another solution path.
To avoid this, a solver needs to process the grid in steps;
1. Look through the whole current grid for singles, but don't fix any numbers yet, only store them.
2. If any, fix all singles in one batch, then go back to 1.
3. Look for naked pairs. Don't eliminate anything yet, just store eliminations for later.
4. If any, do all eliminations, and go back to 1.
5. etc.
Then it won't matter how the puzzle is permuted; all available fixes and eliminations will be seen and solved in one go, regardless of orientation and labels. |
|
| Back to top |
|
|
| Moschopulus
| | Joined: 12 Aug 2005 | | Posts: 39 | | : | |
Items |
|
| Posted: Wed Mar 29, 2006 11:59 pm Post subject: |
|
|
| Lummox JR wrote: |
If your algorithm is used to find a canonical form for the solution grid, it will generate a particular sequence of permutations that can be applied to the original puzzle. The problem is, that exact same sequence would apply to the second puzzle which has different givens. Therefore, the two results would not be the same puzzle (merely equivalent forms), and though their solutions would be in canonical form, the givens would not.
|
I see your point, which is a good one. Firstly, the problem doesn't arise for the vast majority of grids, which have no automorphisms. It's only if a grid has a (nontrivial) automorphism that your question arises.
Secondly, I think you are onto the solution. I think we have to allow automorphisms. Let me re-post
To find the canonical form of a puzzle P, we do the following.
1. find the completion S of the puzzle P.
2. find the canonical form C of S.
3. let x be the sequence of operations taking S to C
4. perform the same operations x on P
5. The result is the canonical form of P. (well, this is the proposed definition)
When S has an automorphism f, the operations x in step 3 are not unique. We could perform f before or after x, and we would still get from S to C. So in step 4 we could do x or xf or fx. On the completed grids, these all transform S to the same grid C. But on the puzzle P, they may transform P to three different puzzles.
Your question is (I think): which one of these three is the canonical form of P?
In fact there could be more than three, depending on how many automorphisms P has. I agree that we need to modify the definition given in 5. That definition works fine for grids with no automorphisms.
Last edited by Moschopulus on Thu Mar 30, 2006 12:35 am; edited 1 time in total |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Thu Mar 30, 2006 12:11 am Post subject: |
|
|
| Lummox JR wrote: |
See, here's where you lose me. Moschopulus posted a puzzle that can be converted to an equivalent puzzle with the exact same solution. This is, as you say, an automorphism.
|
ha, I lost myself here by focusing on solution grids and ignoring the automorphisms that come into play when referring back to the original puzzle
if there are no automorphisms on the solution grid then there is no problem
since there is only one set of transformations to produce the canonical
solution grid, and that same set of transformations can be used on the
puzzle (clues and empty cells) to produce the canonical puzzle
(the following fixes canonicalization w.r.t automorphism)
when an automorphism is detected during canonicalization, chose the set
of transformations that forms the smallest row order lexicographic value
with empty cells set to 0 (and clue cells 1-9)
the two M puzzles now both produce the following canonical solution and puzzle grids
| Code: |
+-------+-------+-------+
| 1 2 3 | 4 5 6 | 7 8 9 |
| 4 5 6 | 7 9 8 | 2 1 3 |
| 7 8 9 | 2 1 3 | 6 5 4 |
|-------+-------+-------|
| 2 4 5 | 8 3 7 | 1 9 6 |
| 6 1 7 | 9 4 5 | 8 3 2 |
| 9 3 8 | 6 2 1 | 5 4 7 |
|-------+-------+-------|
| 3 7 1 | 5 6 9 | 4 2 8 |
| 5 6 2 | 3 8 4 | 9 7 1 |
| 8 9 4 | 1 7 2 | 3 6 5 |
+-------+-------+-------+
+-------+-------+-------+
| . . . | . . 6 | 7 . . |
| 4 . 6 | . . . | . . . |
| . . 9 | 2 . . | . 5 . |
|-------+-------+-------|
| 2 . 5 | 8 . . | . . 6 |
| 6 1 . | 9 . . | . . 2 |
| 9 3 . | . . 1 | . . 7 |
|-------+-------+-------|
| 3 7 . | . . . | . 2 . |
| . 6 2 | . . . | 9 . . |
| . . . | . . . | . . . |
+-------+-------+-------+
|
thanks for catching this |
|
| Back to top |
|
|
| Moschopulus
| | Joined: 12 Aug 2005 | | Posts: 39 | | : | |
Items |
|
| Posted: Thu Mar 30, 2006 12:14 am Post subject: |
|
|
| daj95376 wrote: |
I tried this and the results were questionable.
I randomly selected a puzzle from the top1465 and ran it through gsf's solver to perform the steps you listed above. I then ran QQwing -- with stats turned on -- to solve the original puzzle and the CNF puzzle.
Other than the number of givens matching and a zero value for Naked Pairs, none of the other counts (for techniques employed in solving the puzzles) matched. |
Perhaps you are thinking of equivalence in terms of the solving path. That's not what equivalent means. Equivalence is defined in terms of permutations:
Two grids/puzzles are equivalent if one can be obtained from the other by a sequence of the following operations:
(a) permute the bands of rows
(b) permute rows within a band
(c) permute the bands of columns
(d) permute columns within a band
(e) rotate the grid 90 degrees
(f) permute digits
You also said:
| daj95376 wrote: |
Now, none of the transformations you describe will ever make these two puzzles identical. Similarly, the distinction of two cells being 'given' vs. 'candidate cells' will prevent any solver from ever generating identical steps for their solutions.
Thus, I deduce from your rules that these two puzzles are not equivalent. Okay! |
You *cannot* deduce that the puzzles are not equivalent because no solver will generate identical steps for their solutions.
You *can* deduce that they are not equivalent because no sequence of the transformations will take one puzzle to the other (since the transformations do not change the numbers of givens). |
|
| Back to top |
|
|
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Thu Mar 30, 2006 3:59 am Post subject: |
|
|
So in other words, to modify the original algorithm you'd just have to add an extra step when the newest canonical candidate is found, or when a tie for it is found. Convert the positions of the translated givens to an 81-bit number. If the canonical solution candidate being tested is tied with the previous best choice, compare the 81-bit numbers of the current and best choices. If the new one is lower, it is the new best choice.
Okay, I think I get it. It's a lot simpler than I thought it might be. 1) Find the canonical form of the solution. 2) Translate positions of givens for each possible transformation of the orginal grid into the canonical form. 3) The "lowest" set of given positions combined with the canonical solution grid make up the complete canonical form. |
|
| Back to top |
|
|
| Soultaker
| | Joined: 28 Feb 2006 | | Posts: 49 | | : | |
Items |
|
| Posted: Thu Mar 30, 2006 6:27 pm Post subject: |
|
|
| Why do you want to repeat step 2 for each possible transformation? If two transformations of the solution grid result in the same canonical grid, then their effects on the puzzle will be the same as well, so you can pick any one of them. It follows that step 3 is obsolete as well: there are no differences in puzzles obtained so you picking the 'lowest' doesn't make sense. |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Thu Mar 30, 2006 6:55 pm Post subject: |
|
|
| Soultaker wrote: | | Why do you want to repeat step 2 for each possible transformation? If two transformations of the solution grid result in the same canonical grid, then their effects on the puzzle will be the same as well, so you can pick any one of them. It follows that step 3 is obsolete as well: there are no differences in puzzles obtained so you picking the 'lowest' doesn't make sense. |
the key observation is that all automorphic transformations on the solution
grid produce the same grid, but different automorphic transformations
on the puzzle grid (the one with empty cells) may produce different grids:
let P be the original valid puzzle (with givens and empty cells),
let S be the solution grid for P (no empty cells),
and let C be the canonical solution grid determined by the algorithm
if there are automorphisms on C then there exists at least two
transformations x and y such that x!=y and x(S)=y(S)=C
but with the possibility that x(P)!=y(P)
the additional test resolves the last part (and produces the canonical puzzle)
by looking at all transformations x that satisfy x(S)=C and
selecting transformation c such that c(P) <= x(P) (where <= is
lexicographic on the row order cells of P, with empty cells set to 0) |
|
| Back to top |
|
|
| Soultaker
| | Joined: 28 Feb 2006 | | Posts: 49 | | : | |
Items |
|
| Posted: Thu Mar 30, 2006 7:02 pm Post subject: |
|
|
| Ah, you're right. My mistake. |
|
| Back to top |
|
|
| Moschopulus
| | Joined: 12 Aug 2005 | | Posts: 39 | | : | |
Items |
|
| Posted: Fri Mar 31, 2006 12:51 am Post subject: |
|
|
| Lummox JR wrote: |
Okay, I think I get it. It's a lot simpler than I thought it might be. 1) Find the canonical form of the solution. 2) Translate positions of givens for each possible transformation of the orginal grid into the canonical form. 3) The "lowest" set of given positions combined with the canonical solution grid make up the complete canonical form. |
Just to note:
What gsf is proposing is one canonical form. There are other possible canonical forms. |
|
| Back to top |
|
|
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Fri Mar 31, 2006 2:00 am Post subject: |
|
|
| Aye, naturally there are other canonical forms. The main thing to my mind is just to find which ones really work, and how. The new modification to gsf's algorithm makes it the first, to my knowledge, to fully canonize a puzzle. |
|
| 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
