0 people like it.

# Sudoku with general solve function

Using the general solve function to solve Sudoku. The puzzle specific code was translated from Norvig's Sudoku code, but any errors are mine. Reuses code from fssnip.net/6m and fssnip.net/6n

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: ``` ``````let solve next_f done_f initial = let rec go state = seq { if done_f state then yield state else for state' in next_f state do yield! go state' } go initial let get_row idx = idx / 9 let get_col idx = idx % 9 let get_box idx = let r = get_row idx / 3 let c = get_col idx / 3 3 * r + c let get_neighbors idx = let r = get_row idx let c = get_col idx let b = get_box idx [0 .. 80] |> List.filter (fun x -> x <> idx && (get_row x = r || get_col x = c || get_box x = b)) let squares = [|0 .. 80|] let unit_list = Array.concat [[|0 .. 8|] |> Array.map (fun r -> Array.filter (fun x -> get_row x = r) squares); [|0 .. 8|] |> Array.map (fun r -> Array.filter (fun x -> get_col x = r) squares); [|0 .. 8|] |> Array.map (fun r -> Array.filter (fun x -> get_box x = r) squares)] let units = squares |> Array.map (fun idx -> unit_list |> Array.filter (fun xs -> xs |> Array.exists (fun x -> x = idx))) let neighbor_table = [|0 .. 80|] |> Array.map get_neighbors type Board = string [] let initial_board () = Array.create 81 "123456789" let sudoku_show (board:Board) = for r in 0 .. 8 do if r = 3 || r = 6 then printfn "-------------------" for c in 0 .. 8 do if c = 3 || c = 6 then printf " |" printf " %A" (board.[r * 9 + c]) printfn "" let rec assign (board:Board) idx value = board.[idx].Replace(value, "") |> String.forall (fun c -> eliminate board idx (string c)) and eliminate board idx value = if not (board.[idx].Contains(value)) then true else board.[idx] <- board.[idx].Replace(value, "") if board.[idx].Length = 0 then false // cannot set here else let r1 = if board.[idx].Length = 1 then let v = board.[idx] (neighbor_table.[idx] |> Seq.forall (fun i -> eliminate board i v)) else true let r2 = r1 && units.[idx] |> Array.forall (fun un -> let dplaces = un |> Array.filter (fun x -> board.[x].Contains(value)) if Array.isEmpty dplaces then false elif Array.length dplaces = 1 then assign board dplaces.[0] value else true) r2 let val_count (board:Board) idx = board.[idx].Length let sudoku_next_2 (board:Board) = let best_count, best_idx = seq { 0 .. 80 } |> Seq.map (fun idx -> val_count board idx, idx) |> Seq.filter (fun (c, idx) -> c <> 1) |> Seq.min // printfn "best_idx: %A, best_count: %A" best_idx best_count seq { for v in board.[best_idx] do let board' = Array.copy board if assign board' best_idx (string v) then yield board' } let sudoku_done_2 (board:Board) = board |> Array.forall (fun x -> x.Length = 1) let sudoku_read str = let board = initial_board() Seq.fold (fun idx c -> if c = '.' || c = '0' then idx + 1 elif c < '1' || c > '9' then idx else assign board idx (string c) |> ignore idx + 1) 0 str |> fun c -> if c <> 81 then failwithf "%d chars read" c else board let sudoku board = board |> sudoku_read |> solve sudoku_next_2 sudoku_done_2 |> Seq.head |> sudoku_show let ex2 = "003020600900305001001806400008102900700000008006708200002609500800203009005010300" sudoku ex2 ``````
val solve : next_f:('a -> #seq<'a>) -> done_f:('a -> bool) -> initial:'a -> seq<'a>

Full name: Script.solve
val next_f : ('a -> #seq<'a>)
val done_f : ('a -> bool)
val initial : 'a
val go : ('a -> seq<'a>)
val state : 'a
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
val state' : 'a
val get_row : idx:int -> int

Full name: Script.get_row
val idx : int
val get_col : idx:int -> int

Full name: Script.get_col
val get_box : idx:int -> int

Full name: Script.get_box
val r : int
val c : int
val get_neighbors : idx:int -> int list

Full name: Script.get_neighbors
val b : int
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val filter : predicate:('T -> bool) -> list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.filter
val x : int
val squares : int []

Full name: Script.squares
val unit_list : int [] []

Full name: Script.unit_list
module Array

from Microsoft.FSharp.Collections
val concat : arrays:seq<'T []> -> 'T []

Full name: Microsoft.FSharp.Collections.Array.concat
val map : mapping:('T -> 'U) -> array:'T [] -> 'U []

Full name: Microsoft.FSharp.Collections.Array.map
val filter : predicate:('T -> bool) -> array:'T [] -> 'T []

Full name: Microsoft.FSharp.Collections.Array.filter
val units : int [] [] []

Full name: Script.units
val xs : int []
val exists : predicate:('T -> bool) -> array:'T [] -> bool

Full name: Microsoft.FSharp.Collections.Array.exists
val neighbor_table : int list []

Full name: Script.neighbor_table
type Board = string []

Full name: Script.Board
Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = System.String

Full name: Microsoft.FSharp.Core.string
val initial_board : unit -> string []

Full name: Script.initial_board
val create : count:int -> value:'T -> 'T []

Full name: Microsoft.FSharp.Collections.Array.create
val sudoku_show : board:Board -> unit

Full name: Script.sudoku_show
val board : Board
val r : int32
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
val c : int32
val printf : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printf
val assign : board:Board -> idx:int -> value:string -> bool

Full name: Script.assign
val value : string
module String

from Microsoft.FSharp.Core
val forall : predicate:(char -> bool) -> str:string -> bool

Full name: Microsoft.FSharp.Core.String.forall
val c : char
val eliminate : board:Board -> idx:int -> value:string -> bool

Full name: Script.eliminate
val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not
val r1 : bool
val v : string
module Seq

from Microsoft.FSharp.Collections
val forall : predicate:('T -> bool) -> source:seq<'T> -> bool

Full name: Microsoft.FSharp.Collections.Seq.forall
val i : int
val r2 : bool
val forall : predicate:('T -> bool) -> array:'T [] -> bool

Full name: Microsoft.FSharp.Collections.Array.forall
val un : int []
val dplaces : int []
val isEmpty : array:'T [] -> bool

Full name: Microsoft.FSharp.Collections.Array.isEmpty
val length : array:'T [] -> int

Full name: Microsoft.FSharp.Collections.Array.length
val val_count : board:Board -> idx:int -> int

Full name: Script.val_count
val sudoku_next_2 : board:Board -> seq<string []>

Full name: Script.sudoku_next_2
val best_count : int
val best_idx : int
val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map
val filter : predicate:('T -> bool) -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.filter
val min : source:seq<'T> -> 'T (requires comparison)

Full name: Microsoft.FSharp.Collections.Seq.min
val v : char
val board' : string []
val copy : array:'T [] -> 'T []

Full name: Microsoft.FSharp.Collections.Array.copy
val sudoku_done_2 : board:Board -> bool

Full name: Script.sudoku_done_2
val x : string
property System.String.Length: int
val sudoku_read : str:seq<char> -> string []

val str : seq<char>
val board : string []
val fold : folder:('State -> 'T -> 'State) -> state:'State -> source:seq<'T> -> 'State

Full name: Microsoft.FSharp.Collections.Seq.fold
val ignore : value:'T -> unit

Full name: Microsoft.FSharp.Core.Operators.ignore
val failwithf : format:Printf.StringFormat<'T,'Result> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.failwithf
val sudoku : board:seq<char> -> unit

Full name: Script.sudoku
val board : seq<char>
val head : source:seq<'T> -> 'T