Sudoku board generator

Question

A program that randomly generates a Sudoku game board with varying degrees of difficulty (however you decide to measure difficulty). Sudoku requires that there is only one solution, so your program should too. Input and output can be any form or method of your choosing.

Judging

Fastest code. Tested on a quad-code Windows 7 machine with freely or easily available compiler. Provide link if necessary.

Answer 1

Scheme

Why should I be constrained on the platform used? Especially on such a developer-unfriendly platform as Windows! Anyways... doesn't matter since this code compiles on all Scheme implementations that provide the standard libraries srfi-1, srfi-27 and srfi-43 (that means almost all of them), on virtually (pun intended) every platform. The only non-portable-across-all-implementatons construct I use is "import", but I might as well have used "use" or "require" among others. This minor incompatibility between implementations will be fixed this year, don't worry.

Because of the holy wars pertaining to the Lisp family of languages on the matters of minimalism, the last standard in final status (R6RS) was rejected by most implementors, prefering instead to stick to R5RS until the steering comitee broke up. They came up with the idea to split the language in two, the first being a minimalistic core (assigned to working group 1). The second will be a superset of the first which will better suit daily usage. Both will form R7RS, which will be released this year. This will solve many incompatibilities between implementations.

;; Sudoku generator (v0.2)

;; list ops          randomness     vector ops
(import srfi-1) (import srfi-27) (import srfi-43)

(define rand (random-source-make-integers
                 default-random-source))

(define (shuffle! vec)
  (let swap! ([n (vector-length vec)])
    (let* ([i (rand n)] [n (- n 1)])
      (when (> n 1) (vector-swap! vec n i) (swap! n)))))

(define (make-row)
  (let ([row (vector-unfold (lambda (i) (+ i 1)) 9)])
    (shuffle! row) row))

(define (make-rows)
  (let f ([i 8] [r (make-row)])
    (cons r
      (if (zero? i) (list)
          (f (- i 1) (vector-copy r 1 10 (vector-ref r 0)))))))

(define (split-in ls n)
  (let ([n (quotient (length ls) n)])
    (let f ([ls ls])
      (if (null? ls) ls (cons (take ls n) (f (drop ls n)))))))

(define (make-grid)
  (let ([g (list->vector
              (map list->vector
              (zip (split-in (make-rows) 3))))])
    (shuffle! g) (vector-for-each shuffle! g)
    (vector-concatenate (vector->list g))))

Difficulty: none

I felt the code was too complicated so I rewrote it from scratch. For clue pruning, I am currently working on encoding the board in CNF notation. Since I have access to the original grid, testing for uniqueness is easier. Pruning is done by priority (we prefer to prune cells who maximize the number of possibilities in its surroundings).

So far, this only generates a valid complete grid using only a vector of numbers from 1 to 9 that swaps each index with a random index. This random row is used to derive the other rows by successive rotation. This works because there are only 8 other possible rows, given one sudoku row.

Thus, so far we have ensured there are no row or column conflicts possible. As a matter of fact, the sudoku is based on latin squares which are roman grids of size n*n (a square) which must have unique numbers on every row and column in the range 1 to n. A sudoku is a latin square of size 9*9, with an added constraint: regions.

The next step is to split the list of rows in 3, which now looks like this, given an initial row of (1 2 3 4 5 6 7 8 9):

;; this is a latin square
(((1 2 3 4 5 6 7 8 9)
  (2 3 4 5 6 7 8 9 1)
  (3 4 5 6 7 8 9 1 2))
 ((4 5 6 7 8 9 1 2 3)
  (5 6 7 8 9 1 2 3 4)
  (6 7 8 9 1 2 3 4 5))
 ((7 8 9 1 2 3 4 5 6)
  (8 9 1 2 3 4 5 6 7)
  (9 1 2 3 4 5 6 7 8)))

Given a grid like that, I can "zip" the lists (perform matrix transposition) so that it now looks like this:

;; this is now a sudoku
(((1 2 3 4 5 6 7 8 9)
  (4 5 6 7 8 9 1 2 3)
  (7 8 9 1 2 3 4 5 6))
 ((2 3 4 5 6 7 8 9 1)
  (5 6 7 8 9 1 2 3 4)
  (8 9 1 2 3 4 5 6 7))
 ((3 4 5 6 7 8 9 1 2)
  (6 7 8 9 1 2 3 4 5)
  (9 1 2 3 4 5 6 7 8)))

Magic! No row, column or region conflicts! What needs to be done next is to shuffle the three lists of rows, and the three rows within them. To do that, we convert all lists to vectors, then reuse the same shuffle procedure used with the first row. The last step is to collapse everything back to a grid of 9 rows.

I will post updates later. I am currently more advanced than this, but the rest is still in development (I promise you the cleverness and simplicity of my algorithms will surprise you). This was not done in one day, but with great amounts of research for optimal algorithms.