Sudoku: Difference between revisions

Content added Content deleted

Inline

@@ Line 4,253: / 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 |> List.sortBy fst |> List.map snd |> some
+    | list -> // tryPick ~ 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: / Line 4,378: @@
 9 8 |7 3 6 |2 4 1
-Elapsed milliseconds = 11 ms
+Elapsed milliseconds = 15 ms
 All puzzles in sudoku17
-Puzzles:49151, Total:332.50 s, Average:6.76 ms</pre>
+Puzzles:49151, Total:327.15 s, Average:6.66 ms</pre>
 ===SLPsolve===