Rosetta Code

Sudoku: Difference between revisions

Page Discussion

Sudoku (view source)

Revision as of 11:51, 26 November 2021

15 bytes removed ,  2 years ago
m
→‎Immutable Backtracker
m (→‎Immutable Backtracker: Fixing syntax highlighting)
Line 3,988:
//Helpers
let tuple2 a b = a,b
let flip f a b = f b a
let (>>=) f g = Option.bind g f
 
Line 4,012 ⟶ 4,013:
[for s in squares do s, [| for u in unitList do if u |> Array.contains s then u |] ] |> Map.ofSeq
 
/// DictionaryDistionary of all peer squares in the relevant units wrt square in question
let peers =
[for s in squares do units[s] |> Array.concat |> Array.distinct |> Array.except [s] |> tuple2 s] |> Map.ofSeq
Line 4,039 ⟶ 4,040:
let next s = squares |> Array.tryFindIndex ((=)s) |> function Some i when i + 1 < 81 -> Some squares[i + 1] | _ -> None
 
/// Backtrack recursivelyrecursvely and immutably from index
let rec backtrack sbacktracker (values:Map<string,int>) = function
match s with
| None -> Some values // solved!
| Some s2s when values[s2s] > 0 -> backtrackbacktracker values (next s2s) values // square not empty
| Some s2s ->
let rec tracker (vx:Map<_,_>) dx= =function
match dx with▼
| [] -> None
| d::dxrestdx ->
let vx2 = vx |> Map.change s2 (Option.map (fun _ -> d)) values
match|> backtrackMap.change s (nextOption.map s2)(fun vx2_ with-> d))
| None -> flip trackerbacktracker vx(next dxrests)
▲ match dx with |> function
| None -> tracker valuesdx ▼
| success -> success
|>[for Listd in 1.filter.9 do if (constraints values s2)s d then d] |> tracker▼
[1..9]
▲ |> List.filter (constraints values s2)
▲ |> tracker values
/// solve sudoku using simple backtracking
let solve grid = grid |> parseGrid >>= backtrackflip backtracker (Some "A1")</lang>
</lang>
'''Usage:'''
<lang fsharp>open System
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/121384"