Update

[less_retarded_wiki.git] / sudoku.md

# Sudoku

*Not to be [confused](often_confused.md) with [seppuku](suicide.md).*

Sudoku is a puzzle that's based on filling a grid with numbers that is hugely popular even among [normies](normie.md) such as grandmas and grandpas who find this stuff in magazines for elderly people. The goal is to fill in all squares of a 9x9 grid, prefilled with a few clue digits, with digits 1 to 9 so that no digit repeats in any column, row and 3x3 subgrid. It is like a crosswords puzzle for people who lack general knowledge, but it's also pretty [suckless](suckless.md), pure logic-based puzzle whose generation and solving can be relatively easily automatized (unlike generating crosswords which requires some big databases). The puzzle is a pretty [fun](fun.md) singleplayer [game](game.md), posing opportunities for nice [mathematical](math.md) research and analysis as well as a comfy [programming](programming.md) exercise. Sudokus are a bit similar to [magic squares](magic_square.md). There also exist many similar kinds of puzzles that work on the principle of filling a grid so as to satisfy certain rules given initial clues, many of these are implemented e.g. in [Simon Tatham's Portable Puzzle Collection](stppc.md).

Curiously sudoku has its origins in agricultural designs in which people wanted to lay out fields of different plants in more or less uniform distributions (or something like that, there are some papers about this from 1950s). The puzzle itself became popular in Japan in about 1980s and experienced a boom of popularity in the western world some time after 2000 (similar Asian puzzle boom was historically seen e.g. with [tangram](tangram.md)).

The following is an example of a sudoku puzzle with only the initial clues given:

```
 _________________
|  3 1|  5 7|  6  |
|     |9   8|  4  |
|4_7_8|6_ _2|1_ _5|
|7   5|  6  |4    |
|    6|  8 1|7 2  |
| _ _ |7_ _3|6_5_ |
|5 6  |  9  |    2|
|     |1   5|9   6|
| _ _3|8_2_6| _ _4|

```

The solution to the above is:

```
 _________________
|9 3 1|4 5 7|2 6 8|
|6 5 2|9 1 8|3 4 7|
|4_7_8|6_3_2|1_9_5|
|7 1 5|2 6 9|4 8 3|
|3 4 6|5 8 1|7 2 9|
|2_8_9|7_4_3|6_5_1|
|5 6 7|3 9 4|8 1 2|
|8 2 4|1 7 5|9 3 6|
|1_9_3|8_2_6|5_7_4|
```

We can see neither digit in the solution repeats in any column, row and any of the 9 marked 3x3 subgrids or, in other words, the digits 1 to 9 appear in each column, row and subgrid exactly once. These are basically the whole rules.

**We generally want a sudoku puzzle to have initial clues such that there is exactly one possible (unique) solution.** For this sudoku has to have at least 17 clues (this was proven by a computer). Why do we want this? Probably because in the puzzle world it is simply nice to have a unique solution so that human solvers can check whether they got it right at the back page of the magazine. This constraint is also mathematically more interesting.

**How many possible sudokus are there?** Well, this depends on how we view the problem: let's call one sudoku one grid completely filled according to the rules of sudoku. Now if we consider all possible such grids, there are 6670903752021072936960 of them. However some of these grids are "basically the same" because we can e.g. swap all 3s and 5s in any grid and we get basically the same  thing as digits are nothing more than symbols here. We can also e.g. flip the grid horizontally and it's basically the same. If we take such things into account, there remain "only" 5472730538 essentially different sudokus.

Sudoku puzzles are sometimes assigned a difficulty rating that is based e.g. on the techniques required for its solving.

Of course there exist variants of sudoku, e.g. with different grid sizes, extended to 3D, different constraints on placing the numbers etc.

## Solving Sudoku

There are two topics to address: solving sudoku by people and solving sudoku by computers.

Humans almost exclusively use logical reasoning techniques to solve sudoku, which include:

- **scanning**: We take a look at some frequently appearing number in the grid and see which columns and rows they intersect which implies they cannot be placed in those columns and rows, possibly revealing the only possible location to place such number.
- **single remaining candidate**: When there is only one number left to fill in any column, row or subgrid, it is always clear which one it is and can be safely placed.
- **candidate sets**: A more advanced technique in which we create sets of possible candidate numbers for each square on the grid e.g. by writing tiny numbers in the top corners of the squares. We then apply various reasoning to reduce those sets, i.e. remove candidate numbers, until a single candidate remains for a certain square in which case we can fill in that number with certainty. This will further help us reason about candidates in other squares.
- **[set](set.md) equivalence properties**: Sudoku squares have some nice properties, it can e.g. easily be proven that some set of squares will always contain the same values as another set of squares -- this is quite easy to use, you just have to remember the rules that hold. See below.
- **advanced techniques**: There are quite a lot more advanced and expert level techniques like X Wings, Alternating Inference Chains and many more, described e.g. at http://zitowolf.net/sudoku/strategy.html. { TBH no idea what this is. ~drummyfish }

Relatively recently (sometime in 2020s) there was a quite huge discovery/highlight of so called **Phistomefel ring** -- this is an area on the sudoku board that will always contain the same values as another area, which can greatly help in finding solutions (and also in generating sudokus). Consider the following patterns:

```
 _________________       _________________
|B B .|. . .|. B B|     |. . .|C C C|. . .|
|B B .|. . .|. B B|     |. . .|C C C|. . .|
|._._A|A_A_A|A_._.|     |D_D_D|._._.|D_D_D|
|. . A|. . .|A . .|     |D D D|. . .|D D D|
|. . A|. . .|A . .|     |. . .|C C C|. . .|    ...
|._._A|._._.|A_._.|     |._._.|C_C_C|._._.|
|. . A|A A A|A . .|     |. . .|. . .|. . .|
|B B .|. . .|. B B|     |. . .|. . .|. . .|
|B_B_.|._._.|._B_B|     |._._.|._._.|._._.|
```

On the left we see the Phistomefel ring -- the set of *A* squares (the ring) will always contain the same values as the set of *B* squares! (Check it on our example sudoku above.) That's it, it's pretty simple, and it's simple to prove too (quickly: consider set *S1* = row3 + row7 + 3x3square4 + 3x3square6, and *S2* = column1 + column2 + column8 + column9; it can be seen that *S1* and *S2* contain the same values; now remove from both sets their intersection -- we have removed the same values from both sets so they still contain the same values, set *S1* is now the Phistomefel ring, *S2* are the corners). A nice thing is that you can find more such relationship just using the simple idea of manipulating sets (the other example, values in sets *C* and *D* also have to be the same etc.).

For computers the traditional 9x9 sudoku is nowadays pretty easy to solve, however solving an NxN sudoku is an [NP complete](np_complete.md) problem, i.e. there most likely doesn't exist a "fast" algorithm for solving a generalized NxN sudoku, even though the common 9x9 variant can still be solved pretty quickly with today's computers by using some kind of "smart" [brute force](brute_force.md), for example [backtracking](backtracking.md) (or another state tree search) which [recursively](recursion.md) tries all possibilities and at any violation of the rules gets one step back to change the previous number. Besides this a computer can of course use all the reasoning techniques that humans use such as creating sets of possible values for each square and reducing those sets until only one possibility stays. The approach of reasoning and brute forcing may also be combined: first apply the former and when stuck fall back to the latter.

## Generating Sudoku

{ I haven't personally tested these methods yet, I'm just writing what I've read on some web pages and ideas that come to my mind. ~drummyfish }

Generating sudoku puzzles is non-trivial. There are potentially many different [algorithms](algorithm.md) to do it, here we just foreshadow some common simple approaches.

Note that during generation of the sudoku you may utilize the knowledge of some inherent relationship between squares, e.g. the above mentioned Phistomefel ring.

Firstly we need to have implemented basic code for checking the validity of a grid and also some automatic solver, e.g. based on [backtracking](backtracking.md).

For generating a sudoku we usually start with a completely filled grid and keep removing numbers to leave only a few ones that become the initial clues. For this we have to know how to generate the solved grids. Dumb [brute force](brute_force.md) (i.e. generating completely random grids and testing their validity) won't work here as the probability of finding a valid grid this way is astronomically low (seems around 10^(-56)). What may work is to randomly fill a few squares so that they don't break the rules and then apply our solver to fill in the rest of the squares. Yet a simpler way may be to have a database of a few hand-made grids, then we pick on of them and apply some transformations that keep the validity of the grid which include swapping any two columns, swapping any two rows, [tansposing](transposition.md), flipping the grid, rotating it 90 degrees or swapping any two digits (e.g. swap all 7s with all 9s).

With having a completely filled grid generating a non-unique (more than one solution) sudoku puzzle is trivial -- just take some completely filled grid and remove a few numbers. But as stated, we usually don't want non-unique sudokus.

For a unique solution sudoku we have to check there still exists exactly one solution after removing any numbers from the grid, for which we can again use our solver. Of course we should [optimize](optimization.md) this process by quitting the check after finding more than one solution, we don't need to know the exact count of the solutions, only whether it differs from one.

The matter of generating sudokus is further complicated by taking into account the difficulty rating of the puzzle.

## Code

Here is a [C](c.md) code that solves sudoku with [brute force](brute_force.md) (note that for too many empty squares it won't be usable as it might run for years):

```
#include <stdio.h>

char sudoku[9 * 9] = // 0s for empty squares
{
  9, 3, 1,   0, 5, 7,   2, 6, 0,
  6, 5, 0,   9, 1, 8,   3, 4, 7,
  4, 7, 8,   6, 3, 2,   1, 9, 5,

  7, 1, 5,   2, 6, 0,   4, 8, 3,
  3, 0, 6,   5, 8, 1,   7, 2, 9,
  2, 8, 9,   7, 0, 3,   6, 5, 1,

  5, 6, 7,   3, 9, 0,   8, 1, 2,
  8, 2, 0,   1, 7, 5,   9, 3, 6,
  1, 9, 3,   8, 2, 6,   5, 0, 4
};

void print(void)
{
  puts("-----------------");

  for (int i = 0; i < 9 * 9; ++i)
  {
    putchar('0' + sudoku[i]);
    putchar(i % 9 != 8 ? ' ' : '\n');
  }
}

int isValid(void) // checks if whole sudoku is valid
{
  for (int i = 0; i < 9; ++i)
  {
    unsigned int m1 = 0, m2 = 0, m3 = 0; // bit masks of each group

    char *s1 = sudoku + i,                                   // column
         *s2 = sudoku + i * 9,                               // row
         *s3 = sudoku + (i / 3) * (3 * 3 * 3) + (i % 3) * 3; // square

    for (int j = 0; j < 9; ++j)
    {
      m1 |= (1 << (*s1));
      m2 |= (1 << (*s2));
      m3 |= (1 << (*s3));

      s1 += 9;
      s2 += 1;
      s3 += (j % 3 != 2) ? 1 : 7;
    }

    if ((m1 != m2) || (m1 != m3) || (m1 != 0x03fe)) // all must be 1111111110
      return 0;
  }

  return 1;
}

int printCounter = 0;

int solve(void) // find first empty square and brute forces all values on it
{
  char *square = sudoku;

  printCounter++;

  if (printCounter % 512 == 0) // just to limit printing speed
    print();

  for (int j = 0; j < 9 * 9; ++j, ++square) // find first empty square
    if (!(*square)) // empty square?
    {
      while (1) // try all possible values in the square
      {
        *square = ((*square) + 1) % 10;

        if (!(*square)) // overflow to 0 => we tried all values now
          break;

        if (solve()) // recursively solve the next empty square
          return 1;
      }

      return 0; // no value led to solution => can't be solved
    }

  // no empty square found, the sudoku is filled
  return isValid();
}

int main(void)
{
  /* Here we could do some initial attempts at reasoning and filling in 
  digits by "logic" before getting to brute force -- with too many empty 
  squares brute force will take forever. However this is left as an
  exercise :-) */

  int success = solve();
  print();
  puts(success ? "solved" : "couldn't solve it");

  return 0;
}
```

## See Also

- [nonogram](nonogram.md)
- [sudo](sudo.md)
- [minesweeper](minesweeper.md)
- [Rubik's cube](rubiks_cube.md)
- [sokoban](sokoban.md)
- [autism](autism.md)