Exercise 03 Sudoku Level 0

plex03.clj

(require '[clojure.set :refer (difference)])

(defn sudoku-level0 [coll]
  (let [ics (vec (map #(if % #{%} (set (range 1 10))) coll))
        cnb (fn [cs i]
              (set
                (keep #(if (= 1 (count %)) (first %))
                  (concat
                    (map first (partition-all 1 9 (drop (mod i 9) cs)))
                    (take 9 (drop (* 9 (quot i 9)) cs))
                    (apply concat
                      (partition-all 3 9
                        (take 21 (drop (+ (* 27 (quot i 27))
                                          (* 3 (quot (mod i 9) 3)))
                                       cs))))))))
        rmv (fn [cs]
              (reduce (fn [cs i]
                        (let [c (nth cs i)]
                          (if (< 1 (count c))
                              (assoc cs i (difference c (cnb cs i)))
                              cs)))
                      cs
                      (range 81)))]
    (loop [prev nil curr ics]
      (if (= prev curr)
          (map #(if (< 1 (count %)) nil (first %)) curr)
          (recur curr (rmv curr))))))

(sudoku-level0
  [nil   6 nil   5 nil nil   2 nil nil
   nil   9   8 nil nil   2 nil nil   6
   nil nil   7 nil nil nil   4 nil   3
   nil nil   1 nil nil   7 nil   2 nil
     8 nil nil   1 nil   9 nil nil   5
   nil   7 nil   3 nil nil   9 nil nil
     4 nil   6 nil nil nil   8 nil nil
     5 nil nil   7 nil nil   6   1 nil
   nil nil   2 nil nil   6 nil   9 nil])
; ->
; (1 6 4 5 8 3 2 7 9
;  3 9 8 4 7 2 1 5 6
;  2 5 7 9 6 1 4 8 3
;  9 4 1 6 5 7 3 2 8
;  8 2 3 1 4 9 7 6 5
;  6 7 5 3 2 8 9 4 1
;  4 1 6 2 9 5 8 3 7
;  5 8 9 7 3 4 6 1 2
;  7 3 2 8 1 6 5 9 4)

;; '(pprint (partition 9 9 (sudoku-level0 [...])))
;; will print little nice

plex03.js

function sudokuLevel0 (coll) {
  function quot(a, b) { return Math.floor(a/b); }
  function mod(a, b) { return a - b*quot(a, b); }
  var cs = (function (coll) {
              var a = [], i;
              for (i = 0; i < 81; i++)
                a.push(coll[i]?[coll[i]]:[1,2,3,4,5,6,7,8,9]);
              return a;
            })(coll);
  function cnb(cs, i) {
    var j, a = [], x = mod(i, 9), y = quot(i, 9);
    var bx = quot(mod(i, 9), 3);
    var by = quot(i, 27);
    function f (v) {
      if (v.length == 1 && a.indexOf(v[0]) < 0)
        a.push(v[0])
    }
    for (j = 0; j < 9; j++) {
      f(cs[9*j + x]);
      f(cs[9*y + j]);
      f(cs[27*by + 3*bx + 9*quot(j, 3) + mod(j, 3)]);
    }
    return a;
  }
  function del(a, i, e) {
    var j = a[i].indexOf(e);
    if (0 <= j)
      a[i] = a[i].slice(0, j).concat(a[i].slice(j + 1, a[i].length));
  }
  function rmv(cs) {
    var i, j, l, tbd;
    for (i = 0; i < 81; i++) {
      if (cs[i].length == 1)
        continue;
      tbd = cnb(cs, i);
      l = tbd.length;
      for (j = 0; j < l; j++)
        del(cs, i, tbd[j]);
    }
  }
  do {
    var i, pcs = [];
    for (i = 0; i < 81; i++)
      pcs.push(cs[i]);
    rmv(cs);
  } while ((function (a, b) {
              var i, l = a.length;
              for (i = 0; i < l; i++)
                if (a[i] != b[i])
                  return true;
              return false;
            })(pcs, cs));
  (function () {
    var i;
    for (i = 0; i < 81; i++)
      if (cs[i].length == 1)
        coll[i] = cs[i][0];
   })();

  return coll;
}

sudokuLevel0(
      [ , 6,  , 5,  ,  , 2,  ,  ,
        , 9, 8,  ,  , 2,  ,  , 6,
        ,  , 7,  ,  ,  , 4,  , 3,
        ,  , 1,  ,  , 7,  , 2,  ,
       8,  ,  , 1,  , 9,  ,  , 5,
        , 7,  , 3,  ,  , 9,  ,  ,
       4,  , 6,  ,  ,  , 8,  ,  ,
       5,  ,  , 7,  ,  , 6, 1,  ,
        ,  , 2,  ,  , 6,  , 9,  ]);

// -> [1, 6, 4, 5, 8, 3, 2, 7, 9,
//     3, 9, 8, 4, 7, 2, 1, 5, 6,
//     2, 5, 7, 9, 6, 1, 4, 8, 3,
//     9, 4, 1, 6, 5, 7, 3, 2, 8,
//     8, 2, 3, 1, 4, 9, 7, 6, 5,
//     6, 7, 5, 3, 2, 8, 9, 4, 1,
//     4, 1, 6, 2, 9, 5, 8, 3, 7,
//     5, 8, 9, 7, 3, 4, 6, 1, 2,
//     7, 3, 2, 8, 1, 6, 5, 9, 4]

plex03.scm

(use srfi-1)

(define (sudoku-level0 coll)
  (let* ((ics (map (lambda (c) (if c `(,c) '(1 2 3 4 5 6 7 8 9))) coll))
    (cnb (lambda (cs i)
      (delete-duplicates
        (filter-map
          (lambda (x) (and (= (length x) 1) (car x)))
          (append
            (map car (slices (drop cs (mod i 9)) 9))
            (take (drop cs (* 9 (quotient i 9))) 9)
            (concatenate
              (map (cut take <> 3)
                (slices (take (drop cs (+ (* 27 (quotient i 27))
                                          (* 3 (quotient (mod i 9) 3))))
                              21)
                        9))))))))
   (rps (lambda (l i n) (append (take l i) (cons n (cdr (drop l i))))))
   (rmv (lambda (cs)
          (fold (lambda (i cs)
                  (let ((c (ref cs i)))
                    (if (< 1 (length c))
                        (rps cs i (lset-difference = c (cnb cs i)))
                        cs)))
                cs
                (iota 81)))))
    (let loop ((prev #f) (curr ics))
      (if (equal? prev curr)
          (map (lambda (c) (if (< 1 (length c)) #f (car c))) curr)
          (loop curr (rmv curr))))))

(sudoku-level0
  (list
     #f  6 #f  5 #f #f  2 #f #f
     #f  9  8 #f #f  2 #f #f  6
     #f #f  7 #f #f #f  4 #f  3
     #f #f  1 #f #f  7 #f  2 #f
      8 #f #f  1 #f  9 #f #f  5
     #f  7 #f  3 #f #f  9 #f #f
      4 #f  6 #f #f #f  8 #f #f
      5 #f #f  7 #f #f  6  1 #f
     #f #f  2 #f #f  6 #f  9 #f))

; -> (1 6 4 5 8 3 2 7 9
;     3 9 8 4 7 2 1 5 6
;     2 5 7 9 6 1 4 8 3
;     9 4 1 6 5 7 3 2 8
;     8 2 3 1 4 9 7 6 5
;     6 7 5 3 2 8 9 4 1
;     4 1 6 2 9 5 8 3 7
;     5 8 9 7 3 4 6 1 2
;     7 3 2 8 1 6 5 9 4)

plex03hints.clj

;; ----------------------------------------------------------------
;; Step 1
;; Transform a given vector

;; Use '[]' to describe a vector literal
[3 1 4 1 5 9 2] ; -> [3 1 4 1 5 9 2]

;; Elements of a vector are indexed.
;; So we can use 'assoc' to replace an element of a vector by specifying an index,
;; while cannot of a list.
(assoc [3 1 4 1 5 9 2] 5 7) ; -> [3 1 4 1 5 7 2]

(assoc '(3 1 4 1 5 9 2) 5 7)
; -> Exception: PersistentList cannot be cast to Associative

;; Use 'vec' to transform any type of sequence to a vector
(vec '(3 1 4 1 5 9 2)) ; -> [3 1 4 1 5 9 2]

;; Use '#{}' to describe a set literal

#{3 1 4 1 5} ; -> IllegalArgumentException Duplicate key: 1

#{3 1 4 5} ; -> #{1 3 4 5}

;; Use 'conj' to add an element to a set and
;; 'disj' to remove an element to a set.

(conj #{3 1 4} 1) ; -> #{1 3 4}

(conj #{3 1 4} 5) ; -> #{1 3 4 5}

(disj #{3 1 4} 1) ; -> #{3 4}

(disj #{3 1 4} 5) ; -> #{1 3 4}

;; 'set' transform any sequence to a set
(set [3 1 4 1 5]) ; -> #{1 3 4 5}

(set '(3 1 4 1 5)) ; -> #{1 3 4 5}

;; We wanna get a cell of a Sudoku puzzle
;; as a set of numbers the value of the cell can be.
;; So 'nil' of a given vector is to be transformed to #{1 2 3 4 5 6 7 8 9}
;; 3 is to be transformed to #{3}
(set (range 1 10)) ; -> #{1 2 3 4 5 6 7 8 9}

(map #(if % #{%} (set (range 1 10))) [3 nil 4 nil])
; -> (#{3} #{1 2 3 4 5 6 7 8 9} #{4} #{1 2 3 4 5 6 7 8 9})

(vec (map #(if % #{%} (set (range 1 10))) [3 nil 4 nil]))
; -> [#{3} #{1 2 3 4 5 6 7 8 9} #{4} #{1 2 3 4 5 6 7 8 9}]

;; ----------------------------------------------------------------
;; Step 2

;; 'partition' sequentially partialize a sequence to its subsequences.
;; It accepts a number of elements in a subsequent and a step.
(partition 2 1 '(a b c d e)) ; -> ((a b) (b c) (c d) (d e))

(partition 2 2 '(a b c d e)) ; -> ((a b) (c d))

(partition 2 3 '(a b c d e)) ; -> ((a b) (d e))

;; If a step is equal to a number of elements, it need not to be specified
(partition 2 '(a b c d e)) ; -> ((a b) (c d))

;; 'partition' doesn't return subsequents having less number of
;; elements than specified, while 'partition-all' returns.
(partition 2 '(a b c d e)) ; -> ((a b) (c d))

(partition-all 2 '(a b c d e)) ; -> ((a b) (c d) (e))

;; 'first' is used to take the first element from a sequence
(first '(a b c d e)) ; -> a

;; 'take' to take the first specified number of elements from a sequence
(take 3 '(a b c d e)) ; -> (a b c)

;; 'drop' to drop the first specified number of elements from a sequence
(drop 3 '(a b c d e)) ; -> (d e)

;; Assumed a given sequnce of n*n elements represents a n*n matrix,
;; we wanna get elements of a column by a column index
(def t0
  '(a b c d
    e f g h
    i j k l
    m n o p))

(map first (partition-all 1 4 (drop 0 t0))) ; -> (a e i m)

(map first (partition-all 1 4 (drop 1 t0))) ; -> (b f j n)

(map first (partition-all 1 4 (drop 2 t0))) ; -> (c g k o)

(map first (partition-all 1 4 (drop 3 t0))) ; -> (d h l p)

;; How can you get row index from an index of a sequence of n*n elements
;; representing n*n matrix?
;; Yes, (mod index m) is it.
;; Then you can get all elements in the same column as an given index

(#(map first (partition-all 1 4 (drop (mod % 4) t0))) 5)
; -> (b f j n)
;; where '5' is the index of 'f'

(#(map first (partition-all 1 4 (drop (mod % 4) t0))) 14)
; -> (c g k o)
;; where '14' is the index of 'o'

;; We also wanna get elements of a row by specifying a row index.
(take 4 (drop (* 4 0) t0)) ; -> (a b c d)

(take 4 (drop (* 4 1) t0)) ; -> (e f g h)

(take 4 (drop (* 4 2) t0)) ; -> (i j k l)

(take 4 (drop (* 4 3) t0)) ; -> (m n o p)

;; How can you get row index?
;; (quot index m) is it.
;; Then you can get all elements in the same row as an given index

(#(take 4 (drop (* 4 (quot % 4)) t0)) 5) ; -> (e f g h)

(#(take 4 (drop (* 4 (quot % 4)) t0)) 14) ; -> (m n o p)

;; Use 'concat' to concatenate sequences.
(concat '(a b c) '(d e f)) ; -> '(a b c d e f)

;; Use 'apply' to a function for multiple arguments
;; when the arguments given as a list
(+ 1 2 3) ; -> 6

(apply + '(1 2 3)) ; -> 6

(apply concat '((a b c) (d e f))) ; -> '(a b c d e f)

;; Assumed that the number of elements in the given sequences is
;; a square number of another square number, for example 16,
;; we can define blocks like below with block column index 'bx'
;; and block row index 'by'
;; 
;; by\bx |  0  |  1
;; ------+-----+-----
;;   0   | a b | c d
;;       | e f | g h
;; ------+-----+-----
;;   1   | i j | k l
;;       | m n | o p
;;
;; We want get elements in a block by specifying bx and by.

(apply concat (partition-all 2 4 (take 8 (drop (+ (* 8 0) (* 2 0)) t0))))
; -> (a b e f)

(apply concat (partition-all 2 4 (take 8 (drop (+ (* 8 0) (* 2 1)) t0))))
; -> (c d g h)

(apply concat (partition-all 2 4 (take 8 (drop (+ (* 8 1) (* 2 0)) t0))))
; -> (i j m n)

(apply concat (partition-all 2 4 (take 8 (drop (+ (* 8 1) (* 2 1)) t0))))
; -> (k l o p)

;; Use 'quot' to get a quotient of a division
(quot 5 3) ; -> 1

(quot 6 3) ; -> 2

;; How can you get bx from n*n matrix where n equals to m^2?
;; 
;; O.K.
;; '(quot (mod index n) m)' is.
;; 
;; Then, by?
;;
;; '(quot index (* m n))' is it.
;;
;; Now, you can get all elements in the same block as a given index.
(#(apply concat
    (partition-all 2 4
      (take 8
        (drop (+ (* 8 (quot % 8))
                 (* 2 (quot (mod % 4) 2))) t0))))
 5) ; -> (a b e f)

(#(apply concat
    (partition-all 2 4
      (take 8
        (drop (+ (* 8 (quot % 8))
                 (* 2 (quot (mod % 4) 2))) t0))))
 14) ; -> (k l o p)

;; To be continued...

plex03spec.md

There is a 9 * 9 matrix.
Each cell must be a digit from 1 to 9.
Each digit must appear once in 9 cells of each row.
Each digit must appear once in 9 cells of each column.
Divide cells 9 * (3 * 3 matrix) and Each digit must appear once in 9 cells in each 3 * 3 matrix.
When some cells are filled and others aren't filled,
fill unfilled cells.

Assumed at least 1 cell is deterministic at each situation in 'Level 0'.
You must solve a puzzle assumed that cells are given as a each languages idiomatic collection, for example a list or an array.
A filled cell have a typical integer value and an unfilled cell have each languages idiomatic value to represents not a valid value, for example, , null, nil or Nothing.