Instantly share code, notes, and snippets.

# kohyama/plex03.clj Last active Oct 12, 2015

Exercise 03 Sudoku Level 0
 (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
 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]
 (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)
 ;; ---------------------------------------------------------------- ;; 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...

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.