The New Sudoku Players' Forum

by **P.O.** » Mon Nov 11, 2024 6:24 am

i don't know if this has been noticed

a template can be considered as a permutation matrix of size 9 operating on (1 2 3 4 5 6 7 8 9) and as all templates are distinct it follows that there is a bijection between the set of templates and the set of induced permutations: the template permutations

template permutations are compatible if they do not have the same digit in the same position
a puzzle solution is a set of 9 compatible template permutations

it is possible to develop a resolution technique using only permutations very similar to that of the templates
initialization:
- construct the set of possible permutations
- trim the set by removing all permutations that are not template permutations, from there only template permutations remain
- update the resolution state

then:
- build the set of compatible template permutations of size 2
- retrieve from the combinations the set of permutations
- update the resolution state

...build the set of compatible template permutations of size n+1
etc.

an example:

Code: Select all: . . . . . 4 8 1 . . 5 . . 9 . . . 3 . . . . . 2 . . 6 . . . . . . 2 . 8 . 4 . . 5 . . 7 . 3 . 1 . . . . . . 6 . . 7 . . . . . 9 . . . 1 . . 2 . . 1 4 3 . . . . . .....481..5..9...3.....2..6......2.8.4..5..7.3.1......6..7.....9...1..2..143..... after singles: 7 69 69 5 3 4 8 1 2 1 5 2 68 9 68 7 4 3 4 389 389 1 7 2 59 59 6 5 679 679 469 46 1 2 3 8 28 4 689 2689 5 3 169 7 19 3 2689 1 24689 2468 7 4569 569 459 6 238 358 7 248 589 13459 589 1459 9 378 3578 468 1 568 3456 2 45 28 1 4 3 268 5689 569 5689 7 125 candidates.

the permutation table
the figures in the table represent the columns

Code: Select all: r1 r2 r3 r4 r5 r6 r7 r8 r9 n1 8 1 4 6 79 3 79 5 2 n2 9 3 6 7 14 245 25 8 15 n3 5 9 23 8 6 1 237 237 4 n4 6 8 1 45 2 4579 579 479 3 n5 4 2 78 1 5 789 36789 3679 678 n6 23 46 9 2345 347 24578 1 467 5678 n7 1 7 5 23 8 6 4 23 9 n8 7 46 23 9 134 245 23568 2346 1568 n9 23 5 2378 234 3479 24789 6789 1 678

and here all the permutations:

Hidden Text: Show

Code: Select all: 1: 2: ((8 1 4 6 7 3 9 5 2) (8 1 4 6 9 3 7 5 2)) 2: 3: ((9 3 6 7 1 4 2 8 5) (9 3 6 7 4 2 5 8 1) (9 3 6 7 4 5 2 8 1)) 3: 4: ((5 9 2 8 6 1 3 7 4) (5 9 3 8 6 1 2 7 4) (5 9 2 8 6 1 7 3 4) (5 9 3 8 6 1 7 2 4)) 4: 8: ((6 8 1 4 2 5 7 9 3) (6 8 1 5 2 4 7 9 3) (6 8 1 4 2 7 5 9 3) (6 8 1 4 2 5 9 7 3) (6 8 1 5 2 4 9 7 3) (6 8 1 4 2 9 5 7 3) (6 8 1 5 2 7 9 4 3) (6 8 1 5 2 9 7 4 3)) 5: 11: ((4 2 7 1 5 9 3 6 8) (4 2 7 1 5 9 6 3 8) (4 2 8 1 5 9 3 6 7) (4 2 8 1 5 9 6 3 7) (4 2 7 1 5 8 3 9 6) (4 2 8 1 5 7 3 9 6) (4 2 8 1 5 9 3 7 6) (4 2 7 1 5 8 9 3 6) (4 2 8 1 5 7 9 3 6) (4 2 7 1 5 9 8 3 6) (4 2 8 1 5 9 7 3 6)) 6: 23: ((2 6 9 3 4 5 1 7 8) (3 6 9 2 4 5 1 7 8) (2 6 9 4 3 5 1 7 8) (2 6 9 5 3 4 1 7 8) (3 6 9 5 4 2 1 7 8) (2 4 9 5 3 7 1 6 8) (2 4 9 3 7 5 1 6 8) (3 4 9 2 7 5 1 6 8) (3 4 9 5 7 2 1 6 8) (2 6 9 5 3 7 1 4 8) (2 6 9 3 7 5 1 4 8) (3 6 9 2 7 5 1 4 8) (3 6 9 5 7 2 1 4 8) (2 4 9 5 3 8 1 6 7) (2 6 9 5 3 8 1 4 7) (2 4 9 5 3 8 1 7 6) (2 6 9 3 4 8 1 7 5) (3 6 9 2 4 8 1 7 5) (2 6 9 4 3 8 1 7 5) (2 4 9 3 7 8 1 6 5) (3 4 9 2 7 8 1 6 5) (2 6 9 3 7 8 1 4 5) (3 6 9 2 7 8 1 4 5)) 7: 2: ((1 7 5 2 8 6 4 3 9) (1 7 5 3 8 6 4 2 9)) 8: 20: ((7 4 3 9 1 2 5 6 8) (7 4 2 9 1 5 3 6 8) (7 4 3 9 1 5 2 6 8) (7 6 3 9 1 2 5 4 8) (7 6 2 9 1 5 3 4 8) (7 6 3 9 1 5 2 4 8) (7 4 2 9 1 5 6 3 8) (7 6 2 9 1 4 5 3 8) (7 4 3 9 1 5 6 2 8) (7 6 3 9 1 4 5 2 8) (7 4 2 9 1 5 8 3 6) (7 4 3 9 1 5 8 2 6) (7 4 3 9 1 2 8 6 5) (7 6 3 9 1 2 8 4 5) (7 6 2 9 1 4 8 3 5) (7 6 3 9 1 4 8 2 5) (7 4 2 9 3 5 8 6 1) (7 6 2 9 3 5 8 4 1) (7 6 2 9 4 5 8 3 1) (7 6 3 9 4 5 8 2 1)) 9: 47: ((2 5 3 4 7 9 6 1 8) (3 5 2 4 7 9 6 1 8) (2 5 7 3 4 9 6 1 8) (3 5 7 2 4 9 6 1 8) (2 5 7 4 3 9 6 1 8) (2 5 3 4 9 7 6 1 8) (3 5 2 4 9 7 6 1 8) (2 5 7 3 9 4 6 1 8) (3 5 7 2 9 4 6 1 8) (3 5 7 4 9 2 6 1 8) (2 5 8 3 4 9 6 1 7) (3 5 8 2 4 9 6 1 7) (2 5 8 4 3 9 6 1 7) (2 5 3 4 9 8 6 1 7) (3 5 2 4 9 8 6 1 7) (2 5 8 3 9 4 6 1 7) (3 5 8 2 9 4 6 1 7) (3 5 8 4 9 2 6 1 7) (2 5 3 4 7 8 9 1 6) (3 5 2 4 7 8 9 1 6) (2 5 7 3 4 8 9 1 6) (3 5 7 2 4 8 9 1 6) (2 5 7 4 3 8 9 1 6) (2 5 8 3 4 7 9 1 6) (3 5 8 2 4 7 9 1 6) (2 5 8 4 3 7 9 1 6) (2 5 8 3 7 4 9 1 6) (3 5 8 2 7 4 9 1 6) (3 5 8 4 7 2 9 1 6) (2 5 3 4 7 9 8 1 6) (3 5 2 4 7 9 8 1 6) (2 5 7 3 4 9 8 1 6) (3 5 7 2 4 9 8 1 6) (2 5 7 4 3 9 8 1 6) (2 5 3 4 9 7 8 1 6) (3 5 2 4 9 7 8 1 6) (2 5 7 3 9 4 8 1 6) (3 5 7 2 9 4 8 1 6) (3 5 7 4 9 2 8 1 6) (2 5 8 3 4 9 7 1 6) (3 5 8 2 4 9 7 1 6) (2 5 8 4 3 9 7 1 6) (2 5 3 4 9 8 7 1 6) (3 5 2 4 9 8 7 1 6) (2 5 8 3 9 4 7 1 6) (3 5 8 2 9 4 7 1 6) (3 5 8 4 9 2 7 1 6))

resolution state after removing the permutations that are not template permutations

Code: Select all: 7 69 69 5 3 4 8 1 2 1 5 2 68 9 68 7 4 3 4 38 38 1 7 2 59 59 6 5 679 679 469 46 1 2 3 8 28 4 689 269 5 3 169 7 19 3 269 1 289 68 7 4569 569 459 6 238 358 7 248 589 13459 589 1459 9 378 3578 468 1 568 3456 2 45 28 1 4 3 268 5689 569 5689 7 117 candidates.

the new permutation set:

Hidden Text: Show

Code: Select all: 1: 2: ((8 1 4 6 7 3 9 5 2) (8 1 4 6 9 3 7 5 2)) 2: 2: ((9 3 6 7 1 4 2 8 5) (9 3 6 7 4 2 5 8 1)) 3: 4: ((5 9 2 8 6 1 3 7 4) (5 9 3 8 6 1 2 7 4) (5 9 2 8 6 1 7 3 4) (5 9 3 8 6 1 7 2 4)) 4: 4: ((6 8 1 4 2 7 5 9 3) (6 8 1 4 2 9 5 7 3) (6 8 1 5 2 7 9 4 3) (6 8 1 5 2 9 7 4 3)) 5: 11: ((4 2 7 1 5 9 3 6 8) (4 2 7 1 5 9 6 3 8) (4 2 8 1 5 9 3 6 7) (4 2 8 1 5 9 6 3 7) (4 2 7 1 5 8 3 9 6) (4 2 8 1 5 7 3 9 6) (4 2 8 1 5 9 3 7 6) (4 2 7 1 5 8 9 3 6) (4 2 8 1 5 7 9 3 6) (4 2 7 1 5 9 8 3 6) (4 2 8 1 5 9 7 3 6)) 6: 14: ((2 4 9 5 3 7 1 6 8) (2 4 9 3 7 5 1 6 8) (3 4 9 2 7 5 1 6 8) (3 4 9 5 7 2 1 6 8) (2 6 9 5 3 7 1 4 8) (2 6 9 3 7 5 1 4 8) (3 6 9 2 7 5 1 4 8) (3 6 9 5 7 2 1 4 8) (2 4 9 5 3 8 1 6 7) (2 6 9 5 3 8 1 4 7) (2 4 9 5 3 8 1 7 6) (2 6 9 3 4 8 1 7 5) (3 6 9 2 4 8 1 7 5) (2 6 9 4 3 8 1 7 5)) 7: 2: ((1 7 5 2 8 6 4 3 9) (1 7 5 3 8 6 4 2 9)) 8: 14: ((7 4 2 9 1 5 3 6 8) (7 4 3 9 1 5 2 6 8) (7 6 2 9 1 5 3 4 8) (7 6 3 9 1 5 2 4 8) (7 4 2 9 1 5 6 3 8) (7 6 2 9 1 4 5 3 8) (7 4 3 9 1 5 6 2 8) (7 6 3 9 1 4 5 2 8) (7 4 2 9 1 5 8 3 6) (7 4 3 9 1 5 8 2 6) (7 6 2 9 1 4 8 3 5) (7 6 3 9 1 4 8 2 5) (7 4 2 9 3 5 8 6 1) (7 6 2 9 3 5 8 4 1)) 9: 33: ((2 5 7 3 4 9 6 1 8) (3 5 7 2 4 9 6 1 8) (2 5 7 4 3 9 6 1 8) (2 5 7 3 9 4 6 1 8) (3 5 7 2 9 4 6 1 8) (3 5 7 4 9 2 6 1 8) (2 5 8 3 4 9 6 1 7) (3 5 8 2 4 9 6 1 7) (2 5 8 4 3 9 6 1 7) (2 5 8 3 9 4 6 1 7) (3 5 8 2 9 4 6 1 7) (3 5 8 4 9 2 6 1 7) (2 5 7 3 4 8 9 1 6) (3 5 7 2 4 8 9 1 6) (2 5 7 4 3 8 9 1 6) (2 5 8 3 4 7 9 1 6) (3 5 8 2 4 7 9 1 6) (2 5 8 4 3 7 9 1 6) (2 5 8 3 7 4 9 1 6) (3 5 8 2 7 4 9 1 6) (3 5 8 4 7 2 9 1 6) (2 5 7 3 4 9 8 1 6) (3 5 7 2 4 9 8 1 6) (2 5 7 4 3 9 8 1 6) (2 5 7 3 9 4 8 1 6) (3 5 7 2 9 4 8 1 6) (3 5 7 4 9 2 8 1 6) (2 5 8 3 4 9 7 1 6) (3 5 8 2 4 9 7 1 6) (2 5 8 4 3 9 7 1 6) (2 5 8 3 9 4 7 1 6) (3 5 8 2 9 4 7 1 6) (3 5 8 4 9 2 7 1 6))

the resolution path:

Code: Select all: Initialization #Perms: (2 3 4 8 11 23 2 20 47) 7 69 69 5 3 4 8 1 2 1 5 2 68 9 68 7 4 3 4 389 389 1 7 2 59 59 6 5 679 679 469 46 1 2 3 8 28 4 689 2689 5 3 169 7 19 3 2689 1 24689 2468 7 4569 569 459 6 238 358 7 248 589 13459 589 1459 9 378 3578 468 1 568 3456 2 45 28 1 4 3 268 5689 569 5689 7 125 candidates. Trim permutations #Perms: (2 2 4 4 11 14 2 14 33) 7 69 69 5 3 4 8 1 2 1 5 2 68 9 68 7 4 3 4 38 38 1 7 2 59 59 6 5 679 679 469 46 1 2 3 8 28 4 689 269 5 3 169 7 19 3 269 1 289 68 7 4569 569 459 6 238 358 7 248 589 13459 589 1459 9 378 3578 468 1 568 3456 2 45 28 1 4 3 268 5689 569 5689 7 117 candidates.

2Perms

Hidden Text: Show

Code: Select all: #Perms: (2 2 4 4 11 10 2 12 26) 7 69 69 5 3 4 8 1 2 1 5 2 68 9 68 7 4 3 4 38 38 1 7 2 59 59 6 5 679 679 469 46 1 2 3 8 28 4 689 29 5 3 169 7 19 3 269 1 289 68 7 4569 569 459 6 238 358 7 24 589 13459 589 1459 9 378 3578 468 1 568 3456 2 45 28 1 4 3 268 5689 569 5689 7 115 candidates.

2Perms

Hidden Text: Show

Code: Select all: #Perms: (2 2 4 4 11 10 2 12 23) 7 69 69 5 3 4 8 1 2 1 5 2 68 9 68 7 4 3 4 38 38 1 7 2 59 59 6 5 679 679 469 46 1 2 3 8 28 4 689 29 5 3 169 7 19 3 269 1 289 68 7 4569 569 459 6 238 358 7 24 589 13459 589 1459 9 378 3578 468 1 568 3456 2 45 28 1 4 3 268 5689 569 5689 7 115 candidates.

3Perms

Hidden Text: Show

Code: Select all: #Perms: (2 2 4 4 11 10 2 10 11) 7 69 69 5 3 4 8 1 2 1 5 2 68 9 68 7 4 3 4 38 38 1 7 2 59 59 6 5 679 679 469 46 1 2 3 8 28 4 689 29 5 3 169 7 19 3 269 1 289 68 7 456 569 459 6 238 358 7 24 589 13459 589 1459 9 378 3578 468 1 568 3456 2 45 28 1 4 3 268 5689 569 5689 7 114 candidates.

3Perms

Hidden Text: Show

Code: Select all: #Perms: (2 2 4 4 10 9 2 10 11) 7 69 69 5 3 4 8 1 2 1 5 2 68 9 68 7 4 3 4 38 38 1 7 2 59 59 6 5 679 679 469 46 1 2 3 8 28 4 689 29 5 3 169 7 19 3 269 1 289 68 7 456 569 459 6 238 358 7 24 589 13459 589 1459 9 378 3578 468 1 568 3456 2 45 28 1 4 3 268 5689 569 5689 7 114 candidates.

4Perms

Hidden Text: Show

Code: Select all: #Perms: (2 2 4 2 6 3 2 7 6) 7 9 6 5 3 4 8 1 2 1 5 2 6 9 8 7 4 3 4 8 3 1 7 2 5 9 6 5 6 7 9 4 1 2 3 8 8 4 9 2 5 3 6 7 1 3 2 1 8 6 7 4 5 9 6 3 5 7 2 9 1 8 4 9 7 8 4 1 6 3 2 5 2 1 4 3 8 5 9 6 7 (2 2 3 3 4) puzzle in 4(1)-perms

its solution:

Code: Select all: templates permutations ((8 10 22 33 45 48 61 68 74) (8 1 4 6 9 3 7 5 2)) n1 ((9 12 24 34 40 47 59 71 73) (9 3 6 7 4 2 5 8 1)) n2 ((5 18 21 35 42 46 56 70 76) (5 9 3 8 6 1 2 7 4)) n3 ((6 17 19 32 38 52 63 67 75) (6 8 1 5 2 7 9 4 3)) n4 ((4 11 25 28 41 53 57 72 78) (4 2 7 1 5 8 3 9 6)) n5 ((3 13 27 29 43 50 55 69 80) (3 4 9 2 7 5 1 6 8)) n6 ((1 16 23 30 44 51 58 65 81) (1 7 5 3 8 6 4 2 9)) n7 ((7 15 20 36 37 49 62 66 77) (7 6 2 9 1 4 8 3 5)) n8 ((2 14 26 31 39 54 60 64 79) (2 5 8 4 3 9 6 1 7)) n9

The New Sudoku Players' Forum

from Templates to Permutations

from Templates to Permutations