Skip to content

Instantly share code, notes, and snippets.

@orb
Forked from swannodette/gist:3217582
Last active April 24, 2020 12:04
Show Gist options
  • Save orb/5884956 to your computer and use it in GitHub Desktop.
Save orb/5884956 to your computer and use it in GitHub Desktop.
updated for the latest core.logic, with some minor tweaks for (I hope) clarity
(ns sudoku
(:refer-clojure :exclude [==])
(:use [clojure.core.logic])
(:require [clojure.core.logic.fd :as fd]))
(defn init-board [vars puzzle]
(matche [vars puzzle]
([[] []]
succeed)
([[_ . more-vars] [0 . more-puzzle]]
(init-board more-vars more-puzzle))
([[num . more-vars] [num . more-puzzle]]
(init-board more-vars more-puzzle))))
(defn solve [puzzle]
(let [sdnum (fd/domain 1 2 3 4 5 6 7 8 9)
board (repeatedly 81 lvar)
rows (into [] (map vec (partition 9 board)))
cols (apply map vector rows)
get-square (fn [x y]
(for [x (range x (+ x 3))
y (range y (+ y 3))]
(get-in rows [x y])))
squares (for [x (range 0 9 3)
y (range 0 9 3)]
(get-square x y))]
(run* [q]
(== q board)
(everyg #(fd/in % sdnum) board)
(init-board board puzzle)
(everyg fd/distinct rows)
(everyg fd/distinct cols)
(everyg fd/distinct squares))))
(def puzzle1
[0 0 0 0 0 9 0 6 0
0 3 8 0 0 5 0 0 4
0 2 0 0 6 0 0 7 0
0 0 0 0 0 0 3 9 0
0 0 0 9 2 6 0 0 0
0 9 7 0 0 0 0 0 0
0 4 0 0 7 0 0 3 0
5 0 0 4 0 0 2 1 0
0 7 0 8 0 0 0 0 0])
(def puzzle2
[0 3 0 5 0 0 0 0 0
7 0 0 0 6 0 9 0 0
8 2 9 0 0 0 0 0 0
9 6 0 0 3 0 1 0 0
3 0 0 6 0 4 0 0 2
0 0 4 0 8 0 0 7 6
0 0 0 0 0 0 7 5 3
0 0 7 0 5 0 0 0 9
0 0 0 0 0 9 0 1 0])
;; http://www.sudokudragon.com/unsolvable.htm
(def puzzle3
[0 8 0 0 0 9 7 4 3
0 5 0 0 0 8 0 1 0
0 1 0 0 0 0 0 0 0
8 0 0 0 0 5 0 0 0
0 0 0 8 0 4 0 0 0
0 0 0 3 0 0 0 0 6
0 0 0 0 0 0 0 7 0
0 3 0 5 0 0 0 8 0
9 7 2 4 0 0 0 5 0])
(comment
(partition 9 (first (solve puzzle1)))
((7 1 4 2 8 9 5 6 3)
(6 3 8 7 1 5 9 2 4)
(9 2 5 3 6 4 1 7 8)
(8 6 1 5 4 7 3 9 2)
(4 5 3 9 2 6 7 8 1)
(2 9 7 1 3 8 4 5 6)
(1 4 9 6 7 2 8 3 5)
(5 8 6 4 9 3 2 1 7)
(3 7 2 8 5 1 6 4 9))
(partition 9 (first (solve puzzle2)))
((4 3 6 5 9 1 2 8 7)
(7 5 1 8 6 2 9 3 4)
(8 2 9 4 7 3 5 6 1)
(9 6 8 2 3 7 1 4 5)
(3 7 5 6 1 4 8 9 2)
(2 1 4 9 8 5 3 7 6)
(6 9 2 1 4 8 7 5 3)
(1 8 7 3 5 6 4 2 9)
(5 4 3 7 2 9 6 1 8))
(count (solve puzzle3))
8
)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment