f0216ada32bf8da17aa6bc58ff7ee1b67d1b2cd7
1
module SudokuSolver.Version1
5 open System.Collections.Generic
7 let printUsage progname
=
8 printfn
"Usage: %A <filename>" progname
12 member this
.Next : Pos option =
14 | { i
= 8; j
= 8 } -> None
15 | { i
= i
; j
= 8 } -> Some { i
= i
+ 1; j
= 0 }
16 | { i
= _
; j
= j
} -> Some { this
with j
= j
+ 1 }
20 | 0 | 1 | 2 -> [0 .. 2]
21 | 3 | 4 | 5 -> [3 .. 5]
24 // All possible positions.
27 for j
in 0 .. 8 -> { i
= i
; j
= j
} }
29 type Board (values
: seq
<int>) =
31 let board = Array2D.create
size size 0
34 Seq.take
(size * size) values
|> Seq.zip
AllPos |> Seq.iter
(fun ({ i
= iVal
; j
= jVal
}, value
) ->
35 board.[iVal
, jVal
] <- value
)
37 let get pos
= board.[pos
.i
, pos
.j
]
38 let set pos
value = board.[pos
.i
, pos
.j
] <- value
40 let rec nextFree
(pos
: Pos) : Pos option =
42 | Some pos
-> if get pos = 0 then Some pos else nextFree pos
46 List.forall
(fun j
-> get { pos with j
= j
} <> n) [0 .. 8] &&
47 List.forall
(fun i
-> get { pos with i
= i
} <> n) [0 .. 8] &&
48 List.forall
(fun (i
, j
) -> get { i
= i
; j
= j
} <> n) [
49 for i
' in zoneRange pos.i do
50 for j' in zoneRange pos.j
-> i
', j' ]
52 let validNumbers pos =
54 let valid = isValid pos
56 if valid n then yield
n ]
58 let show (output
: TextWriter) =
59 for i
in 0 .. size - 1 do
60 for j
in 0 .. size - 1 do
63 else output.Write board.[i
, j
]
64 if (j
+ 1) % 3 = 0 && j
<> size - 1 then
67 if (i
+ 1) % 3 = 0 && i
<> size - 1 then
68 output.WriteLine "-----------"
72 let (|OnlyOneNumber|_|) (pos : Pos) =
76 let numbers = Array.create
10 false
84 for i
in 0 .. 8 do get { pos with i
= i
} |> add
85 for j
in 0 .. 8 do get { pos with j
= j
} |> add
86 for i
in zoneRange pos.i
do
87 for j
in zoneRange pos.j
do
88 get { i
= i
; j
= j
} |> add
91 | 9 -> try Some (Array.findIndex not
numbers) with _ -> None
94 // For all remaining numbers.
95 let remainingNumbers = Array.mapi
(fun i p
-> i
, p
) numbers
96 |> Array.fold
(fun acc
(i
, p
) -> if not
p then i
:: acc
else acc) []
98 let rec findNumber
numbers =
102 // If there is no other valid position, then the current is the only one.
105 let pos' = { pos with i = i }
106 if i <> pos.i && get pos' = 0
107 then yield not
(isValid pos' n) } |> Seq.forall id ||
110 let pos' = { pos with j
= j
}
111 if j
<> pos.j
&& get pos' = 0
112 then yield not (isValid pos' n) } |> Seq.forall
id ||
114 for i
in zoneRange pos.i
do
115 for j
in zoneRange pos.j
do
116 let pos' = { i = i; j = j }
117 if pos' <> pos && get pos' = 0
118 then yield not (isValid pos' n) } |> Seq.forall
id
122 findNumber remainingNumbers
124 while Seq.exists
(fun pos ->
126 | OnlyOneNumber n -> set pos n; true
127 | _ -> false) AllPos do ()
129 new (input
: TextReader) =
131 while input.Peek () <> -1 do
132 match char
(input.Read ()) with
133 | ' ' | '.' | '0' -> yield
0
134 | a when Char.IsDigit a -> yield
int (Char.GetNumericValue a)
135 | _ -> () } |> Seq.take
81)
137 member this
.Show = show
139 member this
.Solve () =
140 let rec solveFrom
pos : bool = // Returns true if the solution is valid and complete.
141 match nextFree pos with
143 if List.exists (fun n -> set pos' n; solveFrom
pos') (validNumbers pos')
150 solveFrom { i = 0; j = -1 }