What

This is a python module for generating Sudoku puzzles. It can be used to generate puzzles of different sizes (4x4, 9x9, and 16x16) and different difficulty levels (easy, medium, hard, extreme, insane). It works by taking a "starter puzzle", applying a bunch of random (Sudoku-preserving) transformations to it, and then removing values from squares (while still maintaining a unique solution).œ

Because puzzle generators must also have puzzle solvers, this module also has very simple brute-force solver that works by trying every possible value in every empty square. You can use the solver independently of the generator, but there is no command-line interface to do so.

Why

This started as one of Paul's projects for a math modeling class in college. It was picked up and extended by Dan for use in a programming project of his that needed a supply of 4x4 Sudoku puzzles.

As to why you might be interested in this generator: it is based on an interesting hypothesis of Paul's about how "board density" relates to difficulty. The basic idea is that the more disjoint the set of starting cells is, the more difficult the puzzle will be to can_solve. This goes beyond the normal measure of "less starting cells is more difficult" and begins to consider what particular configurations of those starting cells makes for the most difficult puzzle.

The generator tries to implement this hypothesis by always choosing cells to try and remove that are in areas of "highest density", that is, cells that are constrained by the greatest number of cells in their row, column, and tile. As a result, it tends to produce puzzles where there as few constraints on any given cell as there can be without sacrificing uniqueness of the solution.

Status

Paul originally wrote this in Python 2. Dan has upgraded it to Python 3.7, and provided a lot of code cleanup and documentation. (Due to the use of 3.8-style type annotations, it's unlikely to work in Python 3.6 or below.) There's likely not to be much more development done at this point, unless Dan needs functional extensions for use in other projects.

How do I use it?

The top-level file, sudoku_generator.py, is a Click-based command-line tool. It is self-documenting if you give it the single argument --help, producing this documentation:

$ python sudoku_generator.py --help
Usage: sudoku_generator.py [OPTIONS]

Options:
  -r, --rank INTEGER RANGE        square root of side length (2, 3, or 4)
                                  [default: 3]
  -d, --difficulty [easy|medium|hard|extreme|insane]
                                  desired difficulty of the generated puzzle
                                  [default: easy]
  -c, --count INTEGER             how many puzzles to generate  [default: 1]
  -o, --output [json|html|none]   Whether to produce json, html, or no output
                                  [default: json]
  -v, --verbose                   show generation details and final puzzle
  --starter FILE                  Start from complete puzzle found in FILE
                                  (format is space-separated cell values, one
                                  row per line)
  --help                          Show this message and exit.

All of the options have sensible defaults, so you can invoke it with no arguments and get a puzzle:

$ python sudoku_generator.py
{"rank": 3, "values": [7, 0, 0, 5, 0, 6, 4, 0, 2, 0, 3, 0, 4, 0, 0, 7, 9, 0, 0, 0, 1, 7, 8, 0, 5, 0, 0, 9, 0, 0, 6, 4, 5, 0, 2, 1, 0, 1, 2, 9, 0, 0, 6, 0, 4, 6, 4, 5, 3, 0, 2, 0, 0, 7, 1, 0, 3, 0, 9, 7, 0, 0, 6, 0, 9, 7, 2, 6, 4, 0, 3, 0, 2, 6, 0, 0, 0, 3, 8, 7, 0]}

But when starting off you will probably want to use the -v option to see a printed version both of the generated puzzle and the solution it was generated from:

$ python sudoku_generator.py -v
Solution 1 before removals was:

5 6 4 | 3 2 1 | 8 7 9 
2 3 1 | 9 8 7 | 5 4 6 
8 9 7 | 6 5 4 | 2 1 3 
------+-------+-------
6 5 3 | 4 1 2 | 9 8 7 
9 7 8 | 5 6 3 | 1 2 4 
1 4 2 | 7 9 8 | 6 3 5 
------+-------+-------
4 2 6 | 1 3 5 | 7 9 8 
3 1 5 | 8 7 9 | 4 6 2 
7 8 9 | 2 4 6 | 3 5 1 

Solution 1 after removals is:

5 - - | 3 2 1 | 8 - 9 
2 3 - | 9 - - | 5 4 - 
- 9 7 | - 5 4 | 2 - 3 
------+-------+-------
- 5 - | - - 2 | 9 - 7 
9 7 8 | - - 3 | - - 4 
- - - | 7 9 - | 6 3 - 
------+-------+-------
- 2 6 | - 3 - | - 9 8 
- 1 5 | - - 9 | 4 6 - 
7 - - | 2 4 6 | 3 5 - 

{"rank": 3, "values": [5, 0, 0, 3, 2, 1, 8, 0, 9, 2, 3, 0, 9, 0, 0, 5, 4, 0, 0, 9, 7, 0, 5, 4, 2, 0, 3, 0, 5, 0, 0, 0, 2, 9, 0, 7, 9, 7, 8, 0, 0, 3, 0, 0, 4, 0, 0, 0, 7, 9, 0, 6, 3, 0, 0, 2, 6, 0, 3, 0, 0, 9, 8, 0, 1, 5, 0, 0, 9, 4, 6, 0, 7, 0, 0, 2, 4, 6, 3, 5, 0]}

And you can use the HTML output option to produce results suitable for use on web pages, such as those shown below.

Difficulties & Sample Results

Each of the difficulties is characterized by two threshold percentages:

• the percentage of squares to remove that have only one possible value; and
• the percentage of squares to remove from the remaining highest-density areas.

In the easy puzzles, the first percentage is 44%, and the second percentage is 0%, meaning that all of the easy puzzles are missing fewer than half their squares, and they can all be solved by repeatedly finding a square that can only have one possible value. But starting with the medium level, there are always some empty squares picked at random from areas of higher density, so the puzzles get harder to solve.

Below are samples of the puzzles produced at each of the difficulty levels, to give a sense of how the algorithm works.

easy

-	5	4	-	-	-	3	2	1
9	-	7	-	2	3	6	-	-
3	-	-	4	5	6	-	8	7
4	1	-	3	6	-	7	-	-
-	-	3	-	9	7	4	-	2
7	-	8	2	-	4	-	6	-
-	3	5	6	-	-	8	7	-
-	7	-	5	-	-	2	4	6
2	4	-	9	7	8	-	-	5

medium

-	-	-	-	-	-	-	-	-
5	-	1	-	8	7	4	-	-
6	4	2	-	1	-	7	9	-
1	2	-	7	-	8	-	-	6
7	-	9	-	6	5	2	-	3
4	5	6	-	-	-	-	7	9
-	9	7	3	5	6	-	2	-
-	6	-	2	-	-	9	8	7
-	-	-	8	7	-	-	3	-

hard

-	6	-	-	-	-	-	-	-
-	-	-	-	-	-	-	-	-
-	-	-	-	-	-	-	5	-
-	-	7	3	6	5	1	2	-
6	-	5	2	1	-	9	8	7
1	2	-	8	-	7	6	-	-
-	4	-	-	2	-	-	7	9
2	-	3	7	8	-	5	-	6
8	-	-	-	-	6	2	1	-

extreme

-	-	-	-	-	-	-	-	-
-	-	-	-	-	-	-	-	-
-	-	-	-	9	7	-	-	-
1	4	-	-	8	-	5	-	-
6	5	-	-	-	1	7	-	-
-	-	-	5	-	6	4	2	-
-	-	-	3	-	2	-	7	8
-	9	7	-	4	-	3	-	2
-	-	-	-	7	8	6	4	5

insane

-	-	-	-	-	-	-	-	-
-	-	-	-	-	-	-	-	-
-	-	-	-	-	-	-	-	-
-	-	-	-	-	-	-	-	-
-	-	-	-	-	-	-	-	4
8	9	7	-	-	2	-	-	5
9	7	-	1	-	-	-	-	2
5	-	-	2	4	6	-	9	-
-	-	-	8	-	-	3	-	-