src/sicp/sudoku.rkt

   1 #lang racket
   2
   3 (require "amb-eli.rkt"
   4          "distinct.rkt")
   5
   6 (define (positions size)
   7   (for*/list ([x (in-range 1 (+ size 1))]
   8               [y (in-range 1 (+ size 1))])
   9     (list x y)))
  10
  11 ;; board is represented as list of lists
  12 ;;
  13
  14 (define (sudoku board)
  15   (let ([size (length board)])
  16     (let ([new-board (amb-board board)])
  17       (for ([r new-board])
  18         (assert (distinct? r)))
  19       (for ([c (apply map list new-board)])
  20         (assert (distinct? c)))
  21       (let ([ss (segments size)])
  22         (for ([s ss])
  23           (assert (distinct? s)))
  24         new-board))))
  25
  26
  27 (define (amb-board board)
  28   (cond [(empty? board) empty]
  29         [else
  30          (let ([row (first board)])
  31            (cons (for/list ([r row])
  32                    (if (eq? r '?)
  33                        (amb-list (set->list (set-subtract (set 1 2 3 4 5 6 7 8 9) (list->set row))))
  34                        r))
  35                  (amb-board (rest board))))]))
  36
  37 (define (segments board)
  38   (let ([size (length board)])
  39     (let ([s (sqrt size)])
  40       (for*/list ([i (in-range 0 size s)]
  41                   [j (in-range 0 size s)])
  42         (for*/list ([x (in-range i (+ i s))]
  43                     [y (in-range j (+ j s))])
  44           (list-ref (list-ref board x) y))))))
  45
  46
  47
  48 #|
  49
  50 ((? ? 8 ? ? ? 1 5 ?)
  51  (? ? ? ? ? 1 8 ? ?)
  52  (3 ? 5 4 ? ? ? ? 9)
  53  (5 ? ? ? ? 9 ? ? ?)
  54  (? 9 ? 2 3 4 ? 7 ?)
  55  (? ? ? 1 ? ? ? ? 8)
  56  (4 ? ? ? ? 5 9 ? 1)
  57  (? ? 6 7 ? ? ? ? ?)
  58  (? 5 3 ? ? ? 2 ? ?))
  59
  60 |#
  61