| Mathematics desk | ||
|---|---|---|
| < October 17 | << Sep | October | Nov >> | Current desk > |
| Welcome to the Wikipedia Mathematics Reference Desk Archives |
|---|
| The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
October 18 Information
Hi all.
So, given any 2 solved Sudoku boards, will it always be possible to turn the one into the other by only exchanging rows and columns, keeping in mind that such an exchange can only take place between rows and columns in their own sections? (ie 123 can swap, 456 can swap, 789 can swap) Or does the inability to do so mean that solve Sudoku boards are divided into separate groups?
~~~
Duomillia (
talk) 01:00, 18 October 2022 (UTC)
- I'm pretty sure the answer is no. I don't know if it's correct, but if we consider a Sudoku board as a matrix, then since swapping rows and columns only flips signs, one would expect that Sudoku boards that can be formed from swapping rows/columns would have the same determinant magnitude. At the same time, it's pretty easy to find two Sudoku boards with different determinants.
- If this works as a proof of inequivalence, it certainly doesn't say anything at all about the number of equivalence classes under swapping; I'll deign to someone else to answer that. GalacticShoe ( talk) 01:48, 18 October 2022 (UTC)
- These row and column swaps are validity-preserving operations. They number 3!3 × 3!3 = 46,656. There are more validity-preserving operations than these row and column swaps; for example, one can also swap the band of three rows 123 as a whole with the band of rows 456. One can also transpose the grid. And one can relabel the contents of the cells. This gives 46656 × 3! × 3! × 2 × 9! = 1,218,998,108,160 validity-preserving operations. Considering filled grids equivalent if they can be transformed into each other by any of these validity-preserving operations, Ed Russell and Frazer Jarvis have found that the number of equivalence classes is 5,472,730,538; see Mathematics of Sudoku, in particular the section Essentially different solutions. So the number of equivalence classes under only these 46,656 swap operations is certainly larger. It should be possible to compute the exact number using the same techniques as used by Russell and Jarvis. -- Lambiam 07:01, 18 October 2022 (UTC)
| Mathematics desk | ||
|---|---|---|
| < October 17 | << Sep | October | Nov >> | Current desk > |
| Welcome to the Wikipedia Mathematics Reference Desk Archives |
|---|
| The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
October 18 Information
Hi all.
So, given any 2 solved Sudoku boards, will it always be possible to turn the one into the other by only exchanging rows and columns, keeping in mind that such an exchange can only take place between rows and columns in their own sections? (ie 123 can swap, 456 can swap, 789 can swap) Or does the inability to do so mean that solve Sudoku boards are divided into separate groups?
~~~
Duomillia (
talk) 01:00, 18 October 2022 (UTC)
- I'm pretty sure the answer is no. I don't know if it's correct, but if we consider a Sudoku board as a matrix, then since swapping rows and columns only flips signs, one would expect that Sudoku boards that can be formed from swapping rows/columns would have the same determinant magnitude. At the same time, it's pretty easy to find two Sudoku boards with different determinants.
- If this works as a proof of inequivalence, it certainly doesn't say anything at all about the number of equivalence classes under swapping; I'll deign to someone else to answer that. GalacticShoe ( talk) 01:48, 18 October 2022 (UTC)
- These row and column swaps are validity-preserving operations. They number 3!3 × 3!3 = 46,656. There are more validity-preserving operations than these row and column swaps; for example, one can also swap the band of three rows 123 as a whole with the band of rows 456. One can also transpose the grid. And one can relabel the contents of the cells. This gives 46656 × 3! × 3! × 2 × 9! = 1,218,998,108,160 validity-preserving operations. Considering filled grids equivalent if they can be transformed into each other by any of these validity-preserving operations, Ed Russell and Frazer Jarvis have found that the number of equivalence classes is 5,472,730,538; see Mathematics of Sudoku, in particular the section Essentially different solutions. So the number of equivalence classes under only these 46,656 swap operations is certainly larger. It should be possible to compute the exact number using the same techniques as used by Russell and Jarvis. -- Lambiam 07:01, 18 October 2022 (UTC)