{{ message }}

Instantly share code, notes, and snippets.

# ericnormand/00 Sudoku validator.md

Last active May 17, 2020

Sudoku Validator

Write a function that validates a finished sudoku board. It should take a vector of vectors. The inner vectors represent rows from the sudoku board. The rows should contain nine integers. If the board is well-played, the function should return `true`, otherwise, `false`.

```(sudoku-valid? [[ 1 5 2 4 8 9 3 7 6 ]
[ 7 3 9 2 5 6 8 4 1 ]
[ 4 6 8 3 7 1 2 9 5 ]
[ 3 8 7 1 2 4 6 5 9 ]
[ 5 9 1 7 6 3 4 2 8 ]
[ 2 4 6 8 9 5 7 1 3 ]
[ 9 1 4 6 3 7 5 8 2 ]
[ 6 2 5 9 4 8 1 3 7 ]
[ 8 7 3 5 1 2 9 6 4 ]]) ;=> true

(sudoku-valid? [[ 1 1 2 4 8 9 3 7 6 ]
[ 7 3 9 2 5 6 8 4 1 ]
[ 4 6 8 3 7 1 2 9 5 ]
[ 3 8 7 1 2 4 6 5 9 ]
[ 5 9 1 7 6 3 4 2 8 ]
[ 2 4 6 8 9 5 7 1 3 ]
[ 9 1 4 6 3 7 5 8 2 ]
[ 6 2 5 9 4 8 1 3 7 ]
[ 8 7 3 5 1 2 9 6 4 ]]) ;=> false```

Notes:

• A sudoku puzzle is successfully solved if all rows contain the numbers 1-9, all columns contain 1-9, and the nine 3x3 boxes contain 1-9. See the Wikipedia page for more information.

Thanks to this site for the challenge idea where it is considered Expert level in JavaScript.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn valid? [xs] (every? #(= (range 1 10) (sort %)) xs)) (defn cols [xs] (apply mapv vector xs)) (defn get-block [xs x-offset y-offeset] (->> (drop (* y-offeset 3) xs) (take 3) (mapcat #(->> (drop (* x-offset 3) %) (take 3))))) (defn blocks [xs] (for [x [0 1 2] y [0 1 2]] (get-block xs x y))) (defn sudoku-valid? [xs] (every? #(-> (% xs) (valid?)) [identity cols blocks]))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (letfn [(xf-box->line [idx] (let [i (* 3 (mod idx 3)) j (* 3 (int (/ idx 3)))] (comp (map #(take 3 (drop i %))) (drop j) (take 3) cat))) (sudoku-valid? [sudoku] (transduce (comp (map-indexed (fn [idx _] [(get sudoku idx) (map #(get % idx) sudoku) (sequence (xf-box->line idx) sudoku)])) cat (map (partial apply distinct?))) (fn ([coll] coll) ([coll el] (if el coll (reduced false)))) true sudoku))] (let [sudokus {:valid [[1 5 2 4 8 9 3 7 6] [7 3 9 2 5 6 8 4 1] [4 6 8 3 7 1 2 9 5] [3 8 7 1 2 4 6 5 9] [5 9 1 7 6 3 4 2 8] [2 4 6 8 9 5 7 1 3] [9 1 4 6 3 7 5 8 2] [6 2 5 9 4 8 1 3 7] [8 7 3 5 1 2 9 6 4]] :invalid [[1 1 2 4 8 9 3 7 6] [7 3 9 2 5 6 8 4 1] [4 6 8 3 7 1 2 9 5] [3 8 7 1 2 4 6 5 9] [5 9 1 7 6 3 4 2 8] [2 4 6 8 9 5 7 1 3] [9 1 4 6 3 7 5 8 2] [6 2 5 9 4 8 1 3 7] [8 7 3 5 1 2 9 6 4]]}] (into {} (map (fn [[k v]] [k (sudoku-valid? v)])) sudokus)))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (def group-coords (concat ;; rows (for [y (range 9)] (for [x (range 9)] [x y])) ;; cols (for [x (range 9)] (for [y (range 9)] [x y])) ;; squares (for [xo (range 0 9 3) yo (range 0 9 3)] (for [x (range 3) y (range 3)] [(+ x xo) (+ y yo)])))) (defn lookup [board [x y]] (-> board (get y) (get x))) (defn lookup-group [board group] (map #(lookup board %) group)) (defn sudoku-valid? [board] (->> group-coords (map #(lookup-group board %)) (map set) (every? #{(set (range 1 10))})))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (ns functional-tv-puzzles.-2020.sudoku-377-golf) (defn row [i] (quot i 9)) (defn column [i] (rem i 9)) (defn box [i] [(quot (row i) 3), (quot (column i) 3)]) (def allowed? (set (range 1 10))) (defn sudoku-valid? [rows] (->> rows (transduce (comp cat (keep-indexed vector)) (completing (fn [acc [i v]] (let [paths (->> [row column box] (map #(% i)) (map vector [:rows :cols :boxes]))] (if (or (not (allowed? v)) (->> paths (map #(get-in acc % #{})) (some #(% v)))) (reduced false) (reduce (fn [acc path] (update-in acc path #(conj (or % #{}) v))) acc paths))))) {}) (#(and % true))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn extract-row "Returns a sequence with the values found in a single row of a sudoku grid." [grid row] (nth grid row)) (defn extract-column "Returns a sequence with the values found in a single column of a sudoku grid." [grid column] (map first (map (partial drop column) grid))) (defn extract-sub-grid "Returns a sequence with the values found in the 3x3 section of a sudoku grid whose top-left corner is the specified row and column." [grid row column] (let [rows (map (partial extract-row grid) (range row (+ row 3)))] (mapcat (partial take 3) (map (partial drop column) rows)))) (defn valid-nine? "Checks whether the supplied sequence of numbers conforms to the sudoku rules of containing each integer from 1 to 9. Assumes that only nine values have been supplied, as per the problem statement." [values] (= (set values) #{1 2 3 4 5 6 7 8 9})) (defn sudoku-valid? "Checks whether the supplied sudoku grid, which must consist of nine sequences of nine sequences of integers, meets the win condition of having each digit from 1 to 9 in every row, column, and 3x3 sub-grid." [grid] (every? valid-nine? (concat (for [row (range 9)] (extract-row grid row)) (for [column (range 9)] (extract-column grid column)) (for [row (range 0 9 3) column (range 0 9 3)] (extract-sub-grid grid row column)))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn sudoku-valid? [sudoku] (let [valid-set (set (range 1 10)) rows-sets (map set sudoku) columns-sets (apply (partial map hash-set) sudoku) quadrant (fn [x y] [(quot x 3) (quot y 3)]) ;; given a coord return the quadrant boxes-sets (->> (for [x (range 9) y (range 9)] [x y]) (reduce (fn [r [x y]] ;; add the num to its quadrant set (update r (quadrant x y) (fnil conj #{}) (get-in sudoku [x y]))) {}) vals)] (->> (concat rows-sets columns-sets boxes-sets) (map #(= % valid-set)) (reduce #(and %1 %2) true))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ;; transpose matrix (defn xp [mx] (apply (partial map vector) mx)) ;; collection contains all digits (defn alldigits? [c] (= (set c) (set (range 1 10)))) ;; get 3x3 boxes (defn boxes [p] (->> (partition 3 p) (map xp) (map (partial partition 3)) (apply concat) (map flatten))) (defn sudoku-valid? [p] (every? true? (map alldigits? (concat p (xp p) (boxes p)))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn valid-set? [s] (= (sort s) (range 1 10))) (defn rotate [matrix] (apply map list matrix)) (defn rows [matrix] matrix) (defn cols [matrix] (rotate matrix)) (defn boxes [matrix] (->> (map (partial partition 3) matrix) rotate flatten (partition 9))) (defn cell-sets [matrix] (concat (rows matrix) (cols matrix) (boxes matrix))) (defn sudoku-valid? [sudoku] (->> (cell-sets sudoku) (every? valid-set?)))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn sudoku-valid? [rows] (let [columns (apply map vector rows) boxes (->> rows (map #(partition 3 %)) (partition 3) (mapcat #(apply map concat %)))] (every? #(= 9 (count (set %))) (concat rows columns boxes))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (def rows (let [row (fn [r] (for [c (range 9)] [r c]))] (for [r (range 9)] (row r)))) (def cols (let [col (fn [c] (for [r (range 9)] [r c]))] (for [c (range 9)] (col c)))) (def squares (let [origins (for [r (range 0 9 3) c (range 0 9 3)] [r c]) sq (fn [[r0 c0]] (for [r (range 3) c (range 3)] [(+ r0 r) (+ c0 c)]))] (for [o origins] (sq o)))) (defn solved? [bd] (let [paths (concat rows cols squares) valset (fn [path] (set (map #(get-in bd %) path))) val-sets (map valset paths) valid? (fn [vs] (= 9 (count vs)))] (every? valid? val-sets)))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn sudoku-valid? [s] (->> s (apply map vector) (apply merge s) (map sort) (map #(= [1 2 3 4 5 6 7 8 9] %)) (reduce #(and %1 %2) true)))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (ns pfsudoku.core) (defn contains-all-digits? "Does a collection contain all the digits from 1 to 9?" [x] (= (sort x) (range 1 10))) (defn row "Get a row of a matrix" [x n] (get x n)) (defn column "Get a column of a matrix" [x n] (map #(get % n) x)) (defn submatrix "Get a 3x3 submatrix" [m [s1 e1] [s2 e2]] (let [rows (subvec m s1 e1)] (map #(subvec % s2 e2) rows))) (def cutmap "A list of cuts to make all 3x3s of a 9x9 matrix. The first pair is rows to get, the second is columns." [[[0 3] [0 3]] [[3 6] [0 3]] [[6 9] [0 3]] [[0 3] [3 6]] [[3 6] [3 6]] [[6 9] [3 6]] [[0 3] [6 9]] [[3 6] [6 9]] [[6 9] [6 9]]]) (defn squares3x3 "Get all 3x3 matrixes of a 9x9 matrix" [x] (map #(apply submatrix (cons x %)) cutmap)) (defn sudoku? "Checks if a matrix is a valid sudoku solution." [x] (let [columns (map #(column x %) (range 0 9)) rows (map #(row x %) (range 0 9)) squares (map flatten (squares3x3 x))] (every? contains-all-digits? (concat columns rows squares))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn transpose [mat] (apply mapv vector mat)) (defn blocks3 [mat] (->> mat (map #(partition 3 %)) transpose flatten (partition 9))) (defn segment-valid? [xs] (= (set xs) (set (range 1 10)))) (defn sudoku-valid? [mat] (every? segment-valid? (concat mat (transpose mat) (blocks3 mat))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (ns sudoku) (def numbers (set (range 1 10))) (defn has-all-numbers? [xs] (= numbers (set xs))) (defn cols [board] (apply map list board)) (defn boxes [board] (for [i (range 3) j (range 3)] (mapcat #(nth (partition 3 %) j) (nth (partition 3 board) i)))) (defn valid? [board] (and (every? has-all-numbers? board) (every? has-all-numbers? (cols board)) (every? has-all-numbers? (boxes board))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (ns purelyfunctional-newsletters.issue-377 (:require [clojure.test :refer :all])) (defn rows [board] board) (defn cols [board] (apply map vector board)) (defn boxes [board] (for [i [0 3 6] j [0 3 6]] (for [x (range i (+ i 3)) y (range j (+ j 3))] (get-in board [x y])))) (defn valid? [xs] (= #{1 2 3 4 5 6 7 8 9} (set xs))) (defn sudoku-valid? [board] (every? valid? (concat (rows board) (cols board) (boxes board)))) (deftest sudoku-validation-test (is (true? (sudoku-valid? [[ 1 5 2 4 8 9 3 7 6 ] [ 7 3 9 2 5 6 8 4 1 ] [ 4 6 8 3 7 1 2 9 5 ] [ 3 8 7 1 2 4 6 5 9 ] [ 5 9 1 7 6 3 4 2 8 ] [ 2 4 6 8 9 5 7 1 3 ] [ 9 1 4 6 3 7 5 8 2 ] [ 6 2 5 9 4 8 1 3 7 ] [ 8 7 3 5 1 2 9 6 4 ]]))) (is (false? (sudoku-valid? [[ 1 1 2 4 8 9 3 7 6 ] [ 7 3 9 2 5 6 8 4 1 ] [ 4 6 8 3 7 1 2 9 5 ] [ 3 8 7 1 2 4 6 5 9 ] [ 5 9 1 7 6 3 4 2 8 ] [ 2 4 6 8 9 5 7 1 3 ] [ 9 1 4 6 3 7 5 8 2 ] [ 6 2 5 9 4 8 1 3 7 ] [ 8 7 3 5 1 2 9 6 4 ]]))))

### g7s commented May 16, 2020

@miner good point! TBH my first try was with 3 shorts but `bit-set` was returning a long so I abandoned shorts but kept the implementation the same..

### miner commented May 16, 2020 • edited

Here's a variation on the @g7s bit testing approach. I use `reduce-kv` to drive it so I have the row and col already. The bit twiddling stores the seen bits in a long. The offsets are not critical as long as the bit fields don't overlap. Using shifts for the mask was slightly faster than bit-set on my machine. [Updated to refactor the offsets]

```(defn sudoku-valid-bits? [board]
(boolean (reduce-kv
(fn [res ^long r row]
(let [boxoff (+ 32 (* (quot r 3) 3))
rbit (bit-shift-left 1 (+ r 16))]
(reduce-kv (fn [res ^long c x]
(bit-shift-left 1 c)
(bit-shift-left 1 (+ (quot c 3) boxoff)))
bits ^long (nth res x)]