Rosetta Code

Sudoku: Difference between revisions

Page Discussion

Sudoku (view source)

Revision as of 14:52, 2 December 2021

420 bytes removed ,  2 years ago
m
→‎Constraint Satisfaction (Norvig)
m (→‎Constraint Satisfaction (Norvig): 3.7 ms looked too good, even if could not find issue but this 6.7 ms timings with updated code I trust better)
Line 4,253:
/// Using depth-first search and propagation, try all possible values.
let rec search (values:Map<_,_>)=
let rec some = function
| [] -> None // No Solution
| s::sx ->
values[s]
|> Seq.tryPick (fun d -> assign values s d >>= search)▼
|> function
| Some seqx when Seq.isEmpty seqx -> some sx // reduces calls to find fewest possibilities
| Some seq -> Some seq // returns Some in previous stack's tryPick
| _ -> None // returns None in previous stack's tryPick
// Choose the unfilled square s with the fewest possibilities
[for s in squares do if Seq.length values[s] > 1 then Seq.length values[s] ,s]
|> function
| [] -> Some values // Solved!
| list -> list// |>tryPick List.sortBy~ fst |> List.map snd |>Norvig's `some`
▲ list |> List.minBy fst |> fun (_,s) -> values[s] |> Seq.tryPick (fun d -> assign values s d >>= search)
 
// Core API
Line 4,387 ⟶ 4,378:
5 9 8 |7 3 6 |2 4 1
 
Elapsed milliseconds = 1115 ms
All puzzles in sudoku17
 
Puzzles:49151, Total:332327.5015 s, Average:6.7666 ms</pre>
 
===SLPsolve===
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/121409"