Mirrored from Sudopedia, the Free Sudoku Reference Guide

# Shi Doku

## Basic Description

Shi Doku is a variant of NxN Sudoku variant 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.

• 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_22218 post by sg / Mar 03, 2006 now in The New Sudoku Players' Forum
• fran_2005 Frank, Richard. Mathematics in Sudoku, Fall 2005
• taal_2007 Taalman, Laura. Taking Sudoku Seriously, Math Horizons, September 2007, The Mathematical Association of America
• jpf_9355 post by jpf Sudoku Programmers Forum.