Sudoku Generation

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 generator (sudoku.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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.