Sudoku Solver

(ns sudoku-solver)

(defn valid-move? [board row col num]
  "Check if placing num at [row col] is valid"
  (and
    ;; Check row
    (not (some #{num} (nth board row)))
    
    ;; Check column
    (not (some #{num} (map #(nth % col) board)))
    
    ;; Check 3x3 box
    (let [box-row (* 3 (quot row 3))
          box-col (* 3 (quot col 3))]
      (not (some #{num}
                 (for [r (range box-row (+ box-row 3))
                       c (range box-col (+ box-col 3))]
                   (nth (nth board r) c)))))))

(defn find-empty-cell [board]
  "Find the first empty cell (containing 0)"
  (first
    (for [row (range 9)
          col (range 9)
          :when (= 0 (nth (nth board row) col))]
      [row col])))

(defn set-cell [board row col value]
  "Return new board with value set at [row col]"
  (assoc board row
         (assoc (nth board row) col value)))

(defn solve-sudoku [board]
  "Solve sudoku using backtracking algorithm"
  (if-let [[row col] (find-empty-cell board)]
    ;; Found empty cell, try numbers 1-9
    (loop [num 1]
      (cond
        (> num 9) nil  ;; No valid number found, backtrack
        
        (valid-move? board row col num)
        (let [new-board (set-cell board row col num)
              result (solve-sudoku new-board)]
          (if result
            result  ;; Found solution
            (recur (inc num))))  ;; Try next number
        
        :else (recur (inc num))))
    
    ;; No empty cells found, puzzle is solved
    board))

(defn print-board [board]
  "Pretty print the sudoku board"
  (println "┌─────────┬─────────┬─────────┐")
  (doseq [row (range 9)]
    (when (and (> row 0) (= 0 (mod row 3)))
      (println "├─────────┼─────────┼─────────┤"))
    
    (print "│ ")
    (doseq [col (range 9)]
      (when (and (> col 0) (= 0 (mod col 3)))
        (print "│ "))
      (let [cell (nth (nth board row) col)]
        (print (if (= cell 0) "." cell) " ")))
    (println "│"))
  (println "└─────────┴─────────┴─────────┘"))

(defn is-complete? [board]
  "Check if the board is completely filled"
  (not (some #(some #{0} %) board)))

(defn validate-solution [board]
  "Validate that the solution is correct"
  (and
    (is-complete? board)
    (every? true?
            (for [row (range 9)
                  col (range 9)]
              (let [num (nth (nth board row) col)]
                (and (>= num 1) (<= num 9)
                     ;; Temporarily set cell to 0 and check if move is valid
                     (valid-move? (set-cell board row col 0) row col num)))))))

;; Example usage
(def sample-puzzle
  [[5 3 0 0 7 0 0 0 0]
   [6 0 0 1 9 5 0 0 0]
   [0 9 8 0 0 0 0 6 0]
   [8 0 0 0 6 0 0 0 3]
   [4 0 0 8 0 3 0 0 1]
   [7 0 0 0 2 0 0 0 6]
   [0 6 0 0 0 0 2 8 0]
   [0 0 0 4 1 9 0 0 5]
   [0 0 0 0 8 0 0 7 9]])

(defn -main []
  (println "Original Sudoku Puzzle:")
  (print-board sample-puzzle)
  
  (println "\nSolving...")
  (let [solution (solve-sudoku sample-puzzle)]
    (if solution
      (do
        (println "\nSolution found:")
        (print-board solution)
        (println "\nValidation:" (if (validate-solution solution) "✓ Valid" "✗ Invalid")))
      (println "\nNo solution exists for this puzzle.")))
  
  ;; Test with a harder puzzle
  (println "\n" (repeat 50 "="))
  (println "Testing with a harder puzzle:")
  
  (def hard-puzzle
    [[0 0 0 6 0 0 4 0 0]
     [7 0 0 0 0 3 6 0 0]
     [0 0 0 0 9 1 0 8 0]
     [0 0 0 0 0 0 0 0 0]
     [0 5 0 1 8 0 0 0 3]
     [0 0 0 3 0 6 0 4 5]
     [0 4 0 2 0 0 0 6 0]
     [9 0 3 0 0 0 0 0 0]
     [0 2 0 0 0 0 1 0 0]])
  
  (print-board hard-puzzle)
  
  (let [hard-solution (solve-sudoku hard-puzzle)]
    (if hard-solution
      (do
        (println "\nHard puzzle solution:")
        (print-board hard-solution))
      (println "\nNo solution found for hard puzzle."))))

(-main)