Shi Doku
Basic Description
- Shi Doku is a Sudoku Variant of NxN Sudoku played with a 2x2 box. Thus the overall grid is 4x4 and the digits 1-4 are used.
Magic Numbers for Shi Doku
4,294,967,296 ways to inserting digits 1 to 4 randomly
in a 4x4 grid (4^16)
63,063,000 ways to arrange four 1s, four 2s, four 3s, and four 4s
in a 4x4 grid - 16!/(4!)^4
13,581,312 valid puzzles of which 85632 are minimal.
331,776 combinations of 4 digits in four 2x2 grids
85,632 total number of minimal puzzles (ie no permutations)
1,536 6-clue,
58,368 5-clue
25,728 4-clue puzzles
-----
85,632
4800 essentially different puzzles
576 4x4 Latin Squares using digits 1-4 (ref A002860)
288 Solution Grids of which 2 are essentially different
(ref A107739)
36 Puzzles with different canonical forms
13 4-clues
22 5-clues
1 6-clue
--
36 total
2 essentially different solution grids
Solution Grids
Below two methods will be given to count the 288 unique solution grids. However there are other variations on these techniques. For example see references (arn2010) and (fran_2005).
Method 1 There are 4! = 24 ways to arrange the digits 1 to 4 in Box 1. The digits in box 1 have been marked with an X.
X X * * X X * * * * * * * * * *
There are 4! = 24 ways to arrange the digits 1 to 4 in Box 4. The digits in box 4 have been marked with an Y.
X X * * X X * * * * Y Y * * Y Y
Since the choices for Box 1 and Box 4 are independent, there are 4!^2 = 576 ways to arrange two sets of the digits 1 to 4 in the two boxes. Since the arrangements in Box 1 and 4 completely determine the placement of the other digits. However considering the One Rule for Sudoku, trial and error will show that only 12 of the 24 choices for box 4 are valid Shi Duko solutions. Thus there are 24*12=288 unique solution grids.
Method 2
Following reference (taal_2007) considered a somewhat ordered Shi Doku board. This isn't the minlex form for Shi Doku so this shouldn't be considered to be the template for ordering. However given any Shi Doku board, that board can be easily renumbered to conform to the following pattern. Note that there are 4! ways to renumber the board below.
1 2 * * 3 4 * * * * * * * * * *
Now let's finish numbering the first row and the first column as shown in he pattern below. But columns 3 and 4 can be swapped, and rows 3 and 4 can be swapped. So using 4! from above, that gives:
4! x 4 = 96 ways that the following pattern can be created.
1 2 3 4 3 4 * * 2 * * * 4 * * *
There are three solutions as shown below. Since each solution can be rearranged 96 ways, there are:
3 x 96 = 288 total solution grids.
1 2 3 4 1 2 3 4 1 2 3 4 3 4 1 2 3 4 1 2 3 4 2 1 2 1 4 3 2 3 4 1 2 1 4 3 4 3 2 1 4 1 2 3 4 3 1 2
This is fine for the total count of the possible solution grids, but it leaves an awkward situation where there are three unique grids not 2. But rotate grid 3 out of the plane about a diagonal line running from the upper left corner to the lower right.
1 3 2 4 2 4 1 3 3 2 4 1 4 1 3 2
now renumber, with 1=1, 2=3, 3=2, 4=4. So there are only 2 unique grids!
1 2 3 4 3 4 1 2 2 3 4 1 4 1 2 3
First Solution Grid - 96 isomorphic forms
1 2 3 4 3 4 1 2 2 1 4 3 4 3 2 1
Second Solution Grid - 192 isomorphic forms
1 2 3 4 3 4 1 2 2 3 4 1 4 1 2 3
Minlex pattern for 4x4 grid
The two row (or box) minlex solutions have the following pattern in common.
1 2 3 4 3 4 1 2 2 * 4 * 4 * 2 *
Puzzles
The earliest analysis of the 2x2 grid was done by Sourendu Gupta. He started in The Sudoku Players' Forum which was resurrected after a hard disk failure as The New Sudoku Players' Forum (reference gup_22531). After an error was pointed out he posted corrections (reference gup_22218).
The 36 puzzles were taken from a post by red ed on Mar 03, 2006. (Reference RedEd_22214).
Counts for All Puzzles
For the 288 possible solution grids, the number of puzzles is small enough so that an exhaustive computer analysis is possible. This analysis is simple combinatorics. Any numbering and any geometric permutation is allowed. In other words if two boards don't directly overlay, then they are different. A summary of the results is shown in the table below.
Valid
N C(16,N) 288*C(16,N) Puzzles %Valid
16 1 288 288 100.00%
15 16 4608 4608 100.00%
14 120 34560 34560 100.00%
13 560 161280 161280 100.00%
12 1820 524160 522624 99.71%
11 4368 1257984 1239552 98.53%
10 8008 2306304 2204928 95.60%
9 11440 3294720 2958336 89.79%
8 12870 3706560 2961024 79.89%
7 11440 3294720 2141184 64.99%
6 8008 2306304 1041504 45.16%
5 4368 1257984 285696 22.71%
4 1820 524160 25728 4.91%
Now let's refine the analysis a little bit. Let's renumber the solution grid for the puzzle being worked to be 1234. So the solution to the puzzle being worked will have to be one of the three possibilities shown below. Each possibilities will have a multiplicity of 4! (96 ways to renumber).
1 2 3 4 1 2 3 4 1 2 3 4
3 4 1 2 3 4 1 2 3 4 2 1
2 1 4 3 2 3 4 1 2 1 4 3
4 3 2 1 4 1 2 3 4 3 1 2
------- ------- -------
Type 1 2A 2B
All Valid || || All ||Minimal |Minimal |Minimal ||
Puzzles || Type 1 | Type 2A | Type 2B ||Minimal || Type 1 |Type 2A |Type 2B ||
---------||---------|----------|----------||--------||--------|--------|--------||
16 288 || 96 | 96 | 96 || 0 || 0 | 0 | 0 ||
15 4608 || 1536 | 1536 | 1536 || 0 || 0 | 0 | 0 ||
14 34560 || 11520 | 11520 | 11520 || 0 || 0 | 0 | 0 ||
13 161280 || 53760 | 53760 | 53760 || 0 || 0 | 0 | 0 ||
12 522624 || 173952 | 174336 | 174336 || 0 || 0 | 0 | 0 ||
11 1239552 || 410112 | 414720 | 414720 || 0 || 0 | 0 | 0 ||
10 2204928 || 718080 | 743424 | 743424 || 0 || 0 | 0 | 0 ||
9 2958336 || 930816 | 1013760 | 1013760 || 0 || 0 | 0 | 0 ||
8 2961024 || 870144 | 1013760 | 1013760 || 0 || 0 | 0 | 0 ||
7 2141184 || 552960 | 794112 | 794112 || 0 || 0 | 0 | 0 ||
6 1041504 || 212064 | 414720 | 414720 || 1536 || 1536 | 0 | 0 ||
5 285696 || 39936 | 122880 | 122880 || 58368 || 24576 | 16896 | 16896 ||
4 25728 || 1152 | 12288 | 12288 || 25728 || 1152 | 12288 | 12288 ||
-------- || ------ | ------- | ------- || ------ || ------ | ------ |--------||
13581312 || 3976128 4802592 4802592 || 85632 || 27264 29184 29184 ||
Counts with Orienting and Renumbering
For the three given forms of the puzzles shown above, any numbering and any geometric permutation was allowed. In other words if two boards didn't directly overlay, then they were considered different.
Now let's take a different approach. Let's consolidate all the minimal puzzles using the template below. Now for block 1 there are 24 ways to renumber and 2 ways to orient the pair of columns 3&4, and two ways to orient the pair of rows 3&4. So 96 ways for this pattern.
1 2 3 4 3 4 * * 2 * * * 4 * * *
Type 1 is symmetric with respect to translation, so type 1 has 96 permutations.
Type 2 however has two forms, 2A and 2B above, which can be merged into a single column with a 192 permutations.
1 2 3 4 1 2 3 4
3 4 1 2 3 4 1 2
2 1 4 3 2 3 4 1
4 3 2 1 4 1 2 3
Type 1 Type 2
Ordered
Ordered | & Minimal |
Clues All Puzzles | Puzzles |
------------ | ----------- |
#1 #2 | #1 #2 |
16 1 1 | 0 0 |
15 16 16 | 0 0 |
14 120 120 | 0 0 |
13 560 560 | 0 0 |
12 1812 1816 | 0 0 |
11 4272 4320 | 0 0 |
10 7480 7744 | 0 0 |
9 9696 10560 | 0 0 |
8 9064 10890 | 0 0 |
7 5760 8272 | 0 0 |
6 2209 4320 | 16 0 |
5 416 1280 | 256 176 |
4 12 128 | 12 128 |
---- ----- | --- --- |
Total 41418 50027 | 284 304 |
Canonical Results
The table below shoes the results of canonicalizing the minimal puzzles. So there are 36 essentially different puzzles.
Clues | All | Type 1 | Type 2
6 | 1 | 1 | 0
5 | 22 | 11 | 11
4 | 13 | 2 | 11
| --- | --- | ---
Total | 36 | 14 | 22
Minimum and Maximum clues
4 clues Minimum
- A minimal Shi Doku puzzle will have between 4 and 6 clues. For a proof that 3 clues are insufficient see Gupta's work Shi Doku - Exploring the Mathematics of Su Doku (reference gup_web2). Gupta's proof involves solving cases, and it would seem likely that a proof that 17 clues are needed for 3x3 Sudoku would have to do the same.
6 Clues Maximum
- Using the minlex puzzle above it is easy to show that a maximum of six clues are needed. By removing the clues marked with a X, the clues in the minlex pattern has been reduced to 5 which is minimal for the pattern. Adding a clue at the position of one of the asterisks would be six clues.
X 2 3 X 3 X 1 X 2 * * * X * * *
13 Minimal puzzle with 4 clues
+-----------+ +-----------+ +-----------+ +-----------+ | . . | . . | | . . | . . | | . . | . . | | . . | . . | | . . | . 1 | | . . | . 1 | | . . | . 1 | | . . | . 1 | +-----+---- | +-----+-----+ +-----+-----| |-----+-----+ | . 1 | . 2 | | . 1 | 2 . | | . 2 | . . | | . 2 | . . | | 3 . | . . | | . 3 | . . | | . 3 | . 4 | | . 3 | 2 . | +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ | . . | . . | | . . | . . | | . . | . . | | . . | . . | | . . | . 1 | | . . | 1 2 | | . 1 | . 2 | | . 1 | . 2 | +-----+-----| +-----+---- | +-----+---- | +-----+-----+ | . 2 | . . | | . . | . . | | . . | . . | | . . | . . | | 3 . | 4 . | | 1 3 | . . | | . 3 | 4 . | | 1 . | 3 . | +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ | . . | . . | | . . | . . | | . . | . . | | . . | . 1 | | . 1 | . 2 | | . 1 | . 2 | | . 1 | . 2 | | . 1 | . . | +-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+ | . . | . . | | . . | . . | | . . | 3 . | | . . | 2 . | | 2 . | 3 . | | 3 . | 4 . | | 4 . | . . | | 3 . | . . | +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ | . . | . 1 | | . 2 | . . | +---- +-----+ | . . | 3 . | | 4 . | . . | +-----------+
22 Minimal puzzles with 5 clues
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+ | . . | . . | | . . | . . | | . . | . . | | . . | . . | | . . | . . | | . . | . 1 | | . . | . 1 | | . . | . 1 | | . . | . 1 | | . . | 1 2 | +-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+ +-----+-----| | . 1 | . 2 | | . 1 | 2 . | | . 2 | . . | | . 2 | . 3 | | . 1 | . 3 | | . 2 | . 3 | | 2 . | . 3 | | 3 1 | . 2 | | 3 . | 1 . | | 3 . | . . | +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ | . . | . . | | . . | . . | | . . | . . | | . . | . . | | . . | . . | | . . | 1 2 | | . . | 1 2 | | . . | 1 2 | | . 1 | . 2 | | . 1 | . 2 | +-----+-----| +-----+-----| +-----+-----| +-----+-----| +-----+-----| | . 1 | . 3 | | . 1 | 3 . | | . 1 | 3 . | | . . | . . | | . . | . . | | 4 . | . . | | . 4 | . . | | 3 . | . . | | . 2 | 1 3 | | . 2 | 3 1 | +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ | . . | . . | | . . | . . | | . . | . . | | . . | . . | | . . | . 1 | | . 1 | . 2 | | . 1 | . 2 | | . 1 | . 2 | | . 1 | . 2 | | . . | 2 . | +-----+-----| +-----+-----| +-----+-----| +-----+-----| +-----+-----| | . . | . . | | . . | . 3 | | . . | 2 . | | . . | 2 . | | . 1 | . . | | . 3 | 2 1 | | . 2 | 4 . | | 1 . | . 3 | | 3 . | . 1 | | 2 . | . 3 | +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ | . . | . 1 | | . . | . 1 | | . . | . 1 | | . . | . 1 | | . . | . 1 | | . . | 2 . | | . . | 2 . | | . . | 2 . | | . . | 2 . | | . . | 2 . | +-----+-----| +-----+-----| +-----+-----| +-----+-----| +-----+-----| | . 1 | . . | | . 1 | . . | | . 1 | . . | | . 1 | . . | | . 3 | . . | | 2 3 | . . | | 3 . | . 2 | | 3 2 | . . | | 3 4 | . . | | 4 . | . 2 | +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ +-----------+ | . . | . 1 | | . . | . 1 | | . . | 2 . | | . 1 | 2 . | +-----+-----| +-----+-----| | . 3 | . . | | . . | . 2 | | 4 1 | . . | | 3 . | . . | +-----------+ +-----------+
1 Minimal puzzle with 6 clues
+-----------+ | . . | . . | | . . | 1 2 | |-----+-----+ | . 1 | . 3 | | . 3 | 2 . | +-----------+
Solution Techniques For All Puzzles
All 36 of the above puzzles were solved manually using pencil marks. In each puzzle, after the elementary elimination within rows, columns and boxes, a chain of naked singles was produced leading to a solution. No more heuristic was needed.
External Links
- A002860 The On-Line Encyclopedia of Integer Sequences - Number of Latin squares of order n; or labeled quasigroups (Formerly M2051 N0812)
- A107739 The On-Line Encyclopedia of Integer Sequences - Number of (completed) sudokus (or Sudokus) of size n^2 X n^2.
- arn2010 Arnold, Elizabeth; Lucas, Stephen and Taalman, Laura. Grobner Basis Representations of Sudoku. The College Mathematics Journal, Vol. 41, No. 2, March 2010, pp 101-111
- fon_2010 Fontana,R. ; Rapallo, F. and Rogantin, M. P. Markov bases for sudoku grids Rapporto interno n. 4/2010 Dipartimento di Matematica, Politecnico di Torino.
- 22085 thread now on The New Soduko Players' Forum by sg /Mar 02, 2006. Sudoclues: max, min, forest, leaves
- Gup_web1 Gupta, Sourendu. Some results on Su Doku
- Has proof that 3 clues are not sufficient
- Gup_web2 Gupta, Sourendu. Shi Doku - Exploring the Mathematics of Su Doku
- gup_22531 started by sg Mar 02, 2006
- gup_22218 post by sg / Mar 03, 2006 now in The New Sudoku Players' Forum
- fran_2005 Frank, Richard. Mathematics in Sudoku, Fall 2005
- RedEd_22214 post by Red Ed Mar 03, 2006.
- taal_2007 Taalman, Laura. Taking Sudoku Seriously, Math Horizons, September 2007, The Mathematical Association of America
- jpf_9355 post by jpf Sudoku Programmers Forum.
|
This article is incomplete. You can help Sudopedia by expanding it. |
