6
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Actually, it's not really sudoku if there is more than one possible solution. Many solving strategies rely on the fact that there cannot be multiple solutions. \$\endgroup\$ – Steven Rumbalski Jan 27 '12 at 0:15
  • \$\begingroup\$ @StevenRumbalski: So should a single solution be required? \$\endgroup\$ – Jim McKeeth Jan 27 '12 at 0:17
  • 2
    \$\begingroup\$ Yes, otherwise an empty grid would be a valid puzzle. See technologyreview.com/blog/arxiv/27469. \$\endgroup\$ – Steven Rumbalski Jan 27 '12 at 0:30
  • \$\begingroup\$ @StevenRumbalski: That is what I thought. Updated listing. \$\endgroup\$ – Jim McKeeth Jan 27 '12 at 0:50
  • 1
    \$\begingroup\$ I don't think the number of blank cells is strongly (if at all) correlated with difficulty. \$\endgroup\$ – Peter Taylor Jan 27 '12 at 9:51
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Did anyone ever win a code golf challenge (or a performance challenge) with Scheme? Or are you on your way to be the first? \$\endgroup\$ – ugoren Feb 1 '12 at 21:35
  • \$\begingroup\$ Well, Scheme's focus is on algorithmic performance. While probably being the most minimalist non-toy language. It is a do-it-yourself which requires you to design in a top-down fashion. While having fonctions like call-with-current-continuation and so many parentheses will scare away most, these concepts allow you to travel back and forth in time, have fine-grained control over fonctions, their scoping etc. It's impossible not to choose optimal algorithms in Scheme because you clearly see the nesting (recursion) involved. Why not Scheme? \$\endgroup\$ – Samuel Duclos Feb 1 '12 at 22:14
  • \$\begingroup\$ The thing is, while Perl optimization works by shaving off characters, Scheme optimization works by shaving off functions. I should win more often but people keep wanting less characters instead of just less processing... \$\endgroup\$ – Samuel Duclos Feb 1 '12 at 22:43
  • \$\begingroup\$ You don't normally optimize Perl code by removing characters. However, the definition of a code golf is that the shortest entry wins. Note that this problem is not a code golf (and correctly not tagged as one) because the fastest code wins. Of course the optimization required for code golf problems is to remove characters because that's the winning criterion. You won't write code golf code for production, though, while you may well write speed-optimized production code. \$\endgroup\$ – celtschk Feb 4 '12 at 11:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.