Skip to content

Instantly share code, notes, and snippets.

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

Embed
What would you like to do?
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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.