Sudoku Generation (#213)

Over two years ago, I wrote a basic 3 ⨉ 3-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 gen­er­a­tor (sudoku-generation.hs).

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

./sudoku 5 2

-=-

However, to write a gen­er­a­tor I first wrote a sudoku solver, both generalized as well as broader — instead of on­ly finding one solution, it (eventually) discovers every valid solution to a given sudoku. Within this de­sign decision lies the gen­er­a­tor’s essence — a fully solved, yet pseudo-ran­dom­ly picked, sudoku which can later be clue-dropped can be found in the set of all solutions to the empty sudoku (bearing in mind per­for­mance to some extend, not the en­tire set is gen­er­ated and pseudo-ran­dom­ly sampled, but rather the solving process itself is pseudo-ran­dom­ly 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 puz­zle’s unique solvability. How many clues are attempted to be removed is determined by the given minimum num­ber of clues. One has to note that the above described algorithm cannot always hit as low a clue num­ber as is possible due to the pseudo-ran­dom­ly 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