Sudoku Generation

2019-03-23, post № 213

games, Haskell, programming, #generator, #puzzle

Over two years ago, I wrote a basic 𝟥 ⨉ 𝟥-sudoku solver which uses both fundamental rule-based elimination and guessing to arrive at the solution. Revisiting the topic of computer-aided sudoku manipulation, I wrote a generalized sudoku generator (sudoku-generation.hs).

    | 4  
  3 |    
---------
  2 | 1  
  4 |    

./sudoku 5 2

However, to write a generator I first wrote a sudoku solver, both generalized as well as broader — instead of only finding one solution, it (eventually) discovers every valid solution to a given sudoku. Within this design decision lies the generator’s essence — a fully solved, yet pseudo-randomly picked, sudoku which can later be clue-dropped can be found in the set of all solutions to the empty sudoku (bearing in mind performance to some extend, not the entire set is generated and pseudo-randomly sampled, but rather the solving process itself is pseudo-randomly altered).

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

./sudoku 17 3

Having acquired a fully solved sudoku, the algorithm proceeds to remove clues whilst maintaining the puzzle’s unique solvability. How many clues are attempted to be removed is determined by the given minimum number of clues. One has to note that the above described algorithm cannot always hit as low a clue number as is possible due to the pseudo-randomly chosen path in which clues are dropped. However, clue-dropping does behave monotonically with regards to solvability, in the sense that a sudoku never loses solutions by removing clues.

          3 | 12        7 |  2 10       |    11  6   
       9 13 | 15 14  2    |     8  6 11 |     4      
 5 11  2 12 |          10 |    14  3    |    16  8   
 4 14 10    |             |             |    12      
-----------------------------------------------------
    2 12    |        8  4 |  3     7    |          11
 8          |     2    12 |     1       |    14     3
       7  5 |  6 15       | 10 12     9 |  8    13  2
14  9  3    |    10  7    |  8        2 |            
-----------------------------------------------------
16        9 |       13 11 |           8 |  1    14 12
10  6  4    |  5     1 14 |             |    15  7  8
    8  1    |     3       | 14  9 13  5 |    10     6
12    13 14 | 10  7     8 |        4    | 16  2  5  9
-----------------------------------------------------
          4 |  3 13     1 |  7    16 12 |            
    5 15    |           9 |        2 10 |  6    16   
13     6    |  7        2 |     5  1    | 11       10
    7     2 |    16 10  6 |  9 11  8    | 12 13  1   


./sudoku 125 4