From 93c2731de053d0698800eb8a7ba1a475a38e58cc Mon Sep 17 00:00:00 2001 From: Ummon Date: Fri, 29 May 2015 21:44:35 +0200 Subject: [PATCH 1/1] First commit. --- SudokuSolver.sln | 17 ++++ SudokuSolver/AssemblyInfo.fs | 21 +++++ SudokuSolver/Program.fs | 28 ++++++ SudokuSolver/SudokuSolver.fsproj | 46 ++++++++++ SudokuSolver/Version1.fs | 151 +++++++++++++++++++++++++++++++ SudokuSolver/Version2.fs | 150 ++++++++++++++++++++++++++++++ sudokus/mm_01.txt | 12 +++ sudokus/mm_110.txt | 11 +++ sudokus/mm_22.txt | 11 +++ sudokus/mm_47.txt | 12 +++ sudokus/mm_52.txt | 11 +++ sudokus/naked_single.txt | 11 +++ sudokus/sudoku_easy.txt | 11 +++ sudokus/sudoku_empty.txt | 11 +++ sudokus/sudoku_hard.txt | 11 +++ sudokus/sudoku_hard_2.txt | 11 +++ sudokus/sudoku_impossible.txt | 11 +++ sudokus/sudoku_slow.txt | 1 + sudokus/sudokus.txt | 20 ++++ sudokus/unique_candidate.txt | 11 +++ 20 files changed, 568 insertions(+) create mode 100644 SudokuSolver.sln create mode 100644 SudokuSolver/AssemblyInfo.fs create mode 100644 SudokuSolver/Program.fs create mode 100644 SudokuSolver/SudokuSolver.fsproj create mode 100644 SudokuSolver/Version1.fs create mode 100644 SudokuSolver/Version2.fs create mode 100644 sudokus/mm_01.txt create mode 100644 sudokus/mm_110.txt create mode 100644 sudokus/mm_22.txt create mode 100644 sudokus/mm_47.txt create mode 100644 sudokus/mm_52.txt create mode 100644 sudokus/naked_single.txt create mode 100644 sudokus/sudoku_easy.txt create mode 100644 sudokus/sudoku_empty.txt create mode 100644 sudokus/sudoku_hard.txt create mode 100644 sudokus/sudoku_hard_2.txt create mode 100644 sudokus/sudoku_impossible.txt create mode 100644 sudokus/sudoku_slow.txt create mode 100644 sudokus/sudokus.txt create mode 100644 sudokus/unique_candidate.txt diff --git a/SudokuSolver.sln b/SudokuSolver.sln new file mode 100644 index 0000000..3e0c525 --- /dev/null +++ b/SudokuSolver.sln @@ -0,0 +1,17 @@ + +Microsoft Visual Studio Solution File, Format Version 12.00 +# Visual Studio 2012 +Project("{f2a71f9b-5d33-465a-a702-920d77279786}") = "SudokuSolver", "SudokuSolver\SudokuSolver.fsproj", "{244C26E9-4AA3-42E2-BFD9-4CFB848C7230}" +EndProject +Global + GlobalSection(SolutionConfigurationPlatforms) = preSolution + Debug|x86 = Debug|x86 + Release|x86 = Release|x86 + EndGlobalSection + GlobalSection(ProjectConfigurationPlatforms) = postSolution + {244C26E9-4AA3-42E2-BFD9-4CFB848C7230}.Debug|x86.ActiveCfg = Debug|x86 + {244C26E9-4AA3-42E2-BFD9-4CFB848C7230}.Debug|x86.Build.0 = Debug|x86 + {244C26E9-4AA3-42E2-BFD9-4CFB848C7230}.Release|x86.ActiveCfg = Release|x86 + {244C26E9-4AA3-42E2-BFD9-4CFB848C7230}.Release|x86.Build.0 = Release|x86 + EndGlobalSection +EndGlobal diff --git a/SudokuSolver/AssemblyInfo.fs b/SudokuSolver/AssemblyInfo.fs new file mode 100644 index 0000000..0ec66d0 --- /dev/null +++ b/SudokuSolver/AssemblyInfo.fs @@ -0,0 +1,21 @@ +module SudokuSolver.AssemblyInfo +open System.Reflection +open System.Runtime.CompilerServices + +[] +[] +[] +[] +[] +[] +[] + +// The assembly version has the format {Major}.{Minor}.{Build}.{Revision} + +[] + +//[] +//[] + +() + diff --git a/SudokuSolver/Program.fs b/SudokuSolver/Program.fs new file mode 100644 index 0000000..3402bc5 --- /dev/null +++ b/SudokuSolver/Program.fs @@ -0,0 +1,28 @@ +module SudokuSolver.Main + +module Solver = Version1 + +open System +open System.IO + +[] +let main argv = + use fs = new FileStream ("../../../sudokus/mm_22.txt", FileMode.Open, FileAccess.Read) + use sr = new StreamReader (fs) + + while sr.Peek () <> -1 do + let b = Solver.Board sr + b.Show System.Console.Out + + printfn "vvvvvvvvvvv" + + let timer = System.Diagnostics.Stopwatch () + timer.Start () + + if b.Solve () + then b.Show System.Console.Out + else printfn "No solution" + + timer.Stop () + printfn "Time: %A ms" timer.ElapsedMilliseconds + 0 \ No newline at end of file diff --git a/SudokuSolver/SudokuSolver.fsproj b/SudokuSolver/SudokuSolver.fsproj new file mode 100644 index 0000000..631f372 --- /dev/null +++ b/SudokuSolver/SudokuSolver.fsproj @@ -0,0 +1,46 @@ + + + + Debug + x86 + {244C26E9-4AA3-42E2-BFD9-4CFB848C7230} + Exe + SudokuSolver + SudokuSolver + + + true + full + false + bin\Debug + DEBUG + prompt + true + false + x86 + + + false + none + true + bin\Release + prompt + x86 + true + true + + + + + + + + + + + + + + + + \ No newline at end of file diff --git a/SudokuSolver/Version1.fs b/SudokuSolver/Version1.fs new file mode 100644 index 0000000..f0216ad --- /dev/null +++ b/SudokuSolver/Version1.fs @@ -0,0 +1,151 @@ +module SudokuSolver.Version1 + +open System +open System.IO +open System.Collections.Generic + +let printUsage progname = + printfn "Usage: %A " progname + +type Pos = + { i: int; j: int } + member this.Next : Pos option = + match this with + | { i = 8; j = 8 } -> None + | { i = i; j = 8 } -> Some { i = i + 1; j = 0 } + | { i = _; j = j } -> Some { this with j = j + 1 } + +let zoneRange c = + match c with + | 0 | 1 | 2 -> [0 .. 2] + | 3 | 4 | 5 -> [3 .. 5] + | _ -> [6 .. 8] + +// All possible positions. +let AllPos = seq { + for i in 0 .. 8 do + for j in 0 .. 8 -> { i = i; j = j } } + +type Board (values : seq) = + let size = 9 + let board = Array2D.create size size 0 + + do + Seq.take (size * size) values |> Seq.zip AllPos |> Seq.iter (fun ({ i = iVal; j = jVal}, value) -> + board.[iVal, jVal] <- value) + + let get pos = board.[pos.i, pos.j] + let set pos value = board.[pos.i, pos.j] <- value + + let rec nextFree (pos : Pos) : Pos option = + match pos.Next with + | Some pos -> if get pos = 0 then Some pos else nextFree pos + | _ -> None + + let isValid pos n = + List.forall (fun j -> get { pos with j = j } <> n) [0 .. 8] && + List.forall (fun i -> get { pos with i = i } <> n) [0 .. 8] && + List.forall (fun (i, j) -> get { i = i; j = j } <> n) [ + for i' in zoneRange pos.i do + for j' in zoneRange pos.j -> i', j' ] + + let validNumbers pos = + [ + let valid = isValid pos + for n in 1 .. 9 do + if valid n then yield n ] + + let show (output : TextWriter) = + for i in 0 .. size - 1 do + for j in 0 .. size - 1 do + if board.[i, j] = 0 + then output.Write '.' + else output.Write board.[i, j] + if (j + 1) % 3 = 0 && j <> size - 1 then + output.Write '|' + output.WriteLine () + if (i + 1) % 3 = 0 && i <> size - 1 then + output.WriteLine "-----------" + + + let presolve () = + let (|OnlyOneNumber|_|) (pos : Pos) = + if get pos <> 0 + then None + else + let numbers = Array.create 10 false + let nb = ref 0 + let add n = + if not numbers.[n] + then + numbers.[n] <- true + nb := !nb + 1 + + for i in 0 .. 8 do get { pos with i = i } |> add + for j in 0 .. 8 do get { pos with j = j } |> add + for i in zoneRange pos.i do + for j in zoneRange pos.j do + get { i = i; j = j } |> add + + match !nb with + | 9 -> try Some (Array.findIndex not numbers) with _ -> None + | 10 -> None + | _ -> + // For all remaining numbers. + let remainingNumbers = Array.mapi (fun i p -> i, p) numbers + |> Array.fold (fun acc (i, p) -> if not p then i :: acc else acc) [] + + let rec findNumber numbers = + match numbers with + | [] -> None + | n :: tail -> + // If there is no other valid position, then the current is the only one. + if seq { + for i in 0 .. 8 do + let pos' = { pos with i = i } + if i <> pos.i && get pos' = 0 + then yield not (isValid pos' n) } |> Seq.forall id || + seq { + for j in 0 .. 8 do + let pos' = { pos with j = j } + if j <> pos.j && get pos' = 0 + then yield not (isValid pos' n) } |> Seq.forall id || + seq { + for i in zoneRange pos.i do + for j in zoneRange pos.j do + let pos' = { i = i; j = j } + if pos' <> pos && get pos' = 0 + then yield not (isValid pos' n) } |> Seq.forall id + then Some n + else findNumber tail + + findNumber remainingNumbers + + while Seq.exists (fun pos -> + match pos with + | OnlyOneNumber n -> set pos n; true + | _ -> false) AllPos do () + + new (input : TextReader) = + Board (seq { + while input.Peek () <> -1 do + match char (input.Read ()) with + | ' ' | '.' | '0' -> yield 0 + | a when Char.IsDigit a -> yield int (Char.GetNumericValue a) + | _ -> () } |> Seq.take 81) + + member this.Show = show + + member this.Solve () = + let rec solveFrom pos : bool = // Returns true if the solution is valid and complete. + match nextFree pos with + | Some pos' -> + if List.exists (fun n -> set pos' n; solveFrom pos') (validNumbers pos') + then true + else + set pos' 0 + false + | _ -> true + presolve () + solveFrom { i = 0; j = -1 } + diff --git a/SudokuSolver/Version2.fs b/SudokuSolver/Version2.fs new file mode 100644 index 0000000..a05d072 --- /dev/null +++ b/SudokuSolver/Version2.fs @@ -0,0 +1,150 @@ +module SudokuSolver.Version2 + +open System +open System.IO +open System.Collections.Generic + +let printUsage progname = + printfn "Usage: %A " progname + +type Pos = + { i: int; j: int } + member this.Next : Pos option = + match this with + | { i = 8; j = 8 } -> None + | { i = i; j = 8 } -> Some { i = i + 1; j = 0 } + | { i = _; j = j } -> Some { this with j = j + 1 } + +let zoneRange c = + match c with + | 0 | 1 | 2 -> [0 .. 2] + | 3 | 4 | 5 -> [3 .. 5] + | _ -> [6 .. 8] + +// All possible positions. +let AllPos = seq { + for i in 0 .. 8 do + for j in 0 .. 8 -> { i = i; j = j } } + +type Board (values : seq) = + let size = 9 + let board = Array2D.create size size 0 + + do + Seq.take (size * size) values |> Seq.zip AllPos |> Seq.iter (fun ({ i = iVal; j = jVal}, value) -> + board.[iVal, jVal] <- value) + + let get pos = board.[pos.i, pos.j] + let set pos value = board.[pos.i, pos.j] <- value + + let rec nextFree (pos : Pos) : Pos option = + match pos.Next with + | Some pos -> if get pos = 0 then Some pos else nextFree pos + | _ -> None + + let isValid pos n = + List.forall (fun j -> get { pos with j = j } <> n) [0 .. 8] && + List.forall (fun i -> get { pos with i = i } <> n) [0 .. 8] && + List.forall (fun (i, j) -> get { i = i; j = j } <> n) [ + for i' in zoneRange pos.i do + for j' in zoneRange pos.j -> i', j' ] + + let validNumbers pos = + [ + let valid = isValid pos + for n in 1 .. 9 do + if valid n then yield n ] + + let show (output : TextWriter) = + for i in 0 .. size - 1 do + for j in 0 .. size - 1 do + if board.[i, j] = 0 + then output.Write '.' + else output.Write board.[i, j] + if (j + 1) % 3 = 0 && j <> size - 1 then + output.Write '|' + output.WriteLine () + if (i + 1) % 3 = 0 && i <> size - 1 then + output.WriteLine "-----------" + + + let presolve () = + let (|OnlyOneNumber|_|) (pos : Pos) = + if get pos <> 0 + then None + else + let numbers = Array.create 10 false + let nb = ref 0 + let add n = + if not numbers.[n] + then + numbers.[n] <- true + nb := !nb + 1 + + for i in 0 .. 8 do get { pos with i = i } |> add + for j in 0 .. 8 do get { pos with j = j } |> add + for i in zoneRange pos.i do + for j in zoneRange pos.j do + get { i = i; j = j } |> add + + match !nb with + | 9 -> try Some (Array.findIndex not numbers) with _ -> None + | 10 -> None + | _ -> + // For all remaining numbers. + let remainingNumbers = Array.mapi (fun i p -> i, p) numbers + |> Array.fold (fun acc (i, p) -> if not p then i :: acc else acc) [] + + let rec findNumber numbers = + match numbers with + | [] -> None + | n :: tail -> + // If there is no other valid position, then the current is the only one. + if seq { + for i in 0 .. 8 do + let pos' = { pos with i = i } + if i <> pos.i && get pos' = 0 + then yield not (isValid pos' n) } |> Seq.forall id || + seq { + for j in 0 .. 8 do + let pos' = { pos with j = j } + if j <> pos.j && get pos' = 0 + then yield not (isValid pos' n) } |> Seq.forall id || + seq { + for i in zoneRange pos.i do + for j in zoneRange pos.j do + let pos' = { i = i; j = j } + if pos' <> pos && get pos' = 0 + then yield not (isValid pos' n) } |> Seq.forall id + then Some n + else findNumber tail + + findNumber remainingNumbers + + while Seq.exists (fun pos -> + match pos with + | OnlyOneNumber n -> set pos n; true + | _ -> false) AllPos do () + + new (input : TextReader) = + Board (seq { + while input.Peek () <> -1 do + match char (input.Read ()) with + | ' ' | '.' | '0' -> yield 0 + | a when Char.IsDigit a -> yield int (Char.GetNumericValue a) + | _ -> () } |> Seq.take 81) + + member this.Show = show + + member this.Solve () = + let rec solveFrom pos : bool = // Returns true if the solution is valid and complete. + match nextFree pos with + | Some pos' -> + if List.exists (fun n -> set pos' n; solveFrom pos') (validNumbers pos') + then true + else + set pos' 0 + false + | _ -> true + presolve () + solveFrom { i = 0; j = -1 } diff --git a/sudokus/mm_01.txt b/sudokus/mm_01.txt new file mode 100644 index 0000000..0106ef1 --- /dev/null +++ b/sudokus/mm_01.txt @@ -0,0 +1,12 @@ +8.2|...|9.7 +.7.|...|.1. +6..|1.7|..5 +----------- +..1|.7.|4.. +...|8.6|... +..4|.3.|6.. +----------- +3..|9.8|..6 +.2.|...|.9. +5.6|...|8.1 + diff --git a/sudokus/mm_110.txt b/sudokus/mm_110.txt new file mode 100644 index 0000000..7ac8f6f --- /dev/null +++ b/sudokus/mm_110.txt @@ -0,0 +1,11 @@ +3 4| |1 6 + 8 |1 5| 4 +5 | | 2 +----------- + 6 | | 1 + |417| + 4 | | 9 +----------- +1 | | 8 + 3 |7 2| 6 +8 9| |2 5 \ No newline at end of file diff --git a/sudokus/mm_22.txt b/sudokus/mm_22.txt new file mode 100644 index 0000000..cad55cf --- /dev/null +++ b/sudokus/mm_22.txt @@ -0,0 +1,11 @@ +3 5| 68| +81 | 74| + 69| | 4 +----------- + 2 | 9 | + 5 | 2 | 3 + | 8 | 7 +----------- + 7 | |16 + |64 | 59 + |31 |4 8 \ No newline at end of file diff --git a/sudokus/mm_47.txt b/sudokus/mm_47.txt new file mode 100644 index 0000000..2600216 --- /dev/null +++ b/sudokus/mm_47.txt @@ -0,0 +1,12 @@ +...|6.9|... +..3|...|9.. +.5.|874|.3. +----------- +6.1|...|8.7 +...|.1.|... +3.7|...|6.9 +----------- +.7.|185|.4. +..5|...|1.. +...|2.7|... + diff --git a/sudokus/mm_52.txt b/sudokus/mm_52.txt new file mode 100644 index 0000000..ff84d93 --- /dev/null +++ b/sudokus/mm_52.txt @@ -0,0 +1,11 @@ + | | + 4|3 9|2 + 81| 5 |49 +----------- + 5 |9 2| 7 + 6| 7 |1 + 2 |8 6| 5 +----------- + 67| 9 |83 + 5|2 4|6 + | | \ No newline at end of file diff --git a/sudokus/naked_single.txt b/sudokus/naked_single.txt new file mode 100644 index 0000000..66160df --- /dev/null +++ b/sudokus/naked_single.txt @@ -0,0 +1,11 @@ +...|...|... +...|...|... +...|.4.|... +----------- +...|6..|... +...|..9|... +2.8|...|..3 +----------- +...|.1.|... +...|.5.|... +...|...|... diff --git a/sudokus/sudoku_easy.txt b/sudokus/sudoku_easy.txt new file mode 100644 index 0000000..6b4460a --- /dev/null +++ b/sudokus/sudoku_easy.txt @@ -0,0 +1,11 @@ + 3 | 6| 72 + 2| 8 |91 + 6 | |48 +----------- + |4 | 7 +7 |2 1| 9 +2 | 7| +----------- + 17| | 2 + 58| 7 |3 +92 |6 | 5 \ No newline at end of file diff --git a/sudokus/sudoku_empty.txt b/sudokus/sudoku_empty.txt new file mode 100644 index 0000000..eaf3324 --- /dev/null +++ b/sudokus/sudoku_empty.txt @@ -0,0 +1,11 @@ + | | + | | + | | +----------- + | | + | | + | | +----------- + | | + | | + | | \ No newline at end of file diff --git a/sudokus/sudoku_hard.txt b/sudokus/sudoku_hard.txt new file mode 100644 index 0000000..341eca4 --- /dev/null +++ b/sudokus/sudoku_hard.txt @@ -0,0 +1,11 @@ + 79| |8 +3 | 5| 6 +5 |4 |2 3 +----------- + | 5 | + 4 |2 6| 7 + | 9 | +----------- +4 7| 1| 5 + 3 |5 | 7 + 8| |62 \ No newline at end of file diff --git a/sudokus/sudoku_hard_2.txt b/sudokus/sudoku_hard_2.txt new file mode 100644 index 0000000..dd0b2fc --- /dev/null +++ b/sudokus/sudoku_hard_2.txt @@ -0,0 +1,11 @@ +8..|...|... +..3|6..|... +.7.|.9.|2.. +----------- +.5.|..7|... +...|.45|7.. +...|1..|.3. +----------- +..1|...|.68 +..8|5..|.1. +.9.|...|4.. \ No newline at end of file diff --git a/sudokus/sudoku_impossible.txt b/sudokus/sudoku_impossible.txt new file mode 100644 index 0000000..488519f --- /dev/null +++ b/sudokus/sudoku_impossible.txt @@ -0,0 +1,11 @@ +11 | | + | | + | | +----------- + | | + | | + | | +----------- + | | + | | + | | \ No newline at end of file diff --git a/sudokus/sudoku_slow.txt b/sudokus/sudoku_slow.txt new file mode 100644 index 0000000..62eae32 --- /dev/null +++ b/sudokus/sudoku_slow.txt @@ -0,0 +1 @@ +4...3.......6..8..........1....5..9..8....6...7.2........1.27..5.3....4.9........ \ No newline at end of file diff --git a/sudokus/sudokus.txt b/sudokus/sudokus.txt new file mode 100644 index 0000000..e299c76 --- /dev/null +++ b/sudokus/sudokus.txt @@ -0,0 +1,20 @@ +..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9 +.......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6... +.2..5.7..4..1....68....3...2....8..3.4..2.5.....6...1...2.9.....9......57.4...9.. +........3..1..56...9..4..7......9.5.7.......8.5.4.2....8..2..9...35..1..6........ +12.3....435....1....4........54..2..6...7.........8.9...31..5.......9.7.....6...8 +1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1 +.......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7..... +12.3.....4.....3....3.5......42..5......8...9.6...5.7...15..2......9..6......7..8 +..3..6.8....1..2......7...4..9..8.6..3..4...1.7.2.....3....5.....5...6..98.....5. +1.......9..67...2..8....4......75.3...5..2....6.3......9....8..6...4...1..25...6. +..9...4...7.3...2.8...6...71..8....6....1..7.....56...3....5..1.4.....9...2...7.. +....9..5..1.....3...23..7....45...7.8.....2.......64...9..1.....8..6......54....7 +4...3.......6..8..........1....5..9..8....6...7.2........1.27..5.3....4.9........ +7.8...3.....2.1...5.........4.....263...8.......1...9..9.6....4....7.5........... +3.7.4...........918........4.....7.....16.......25..........38..9....5...2.6..... +........8..3...4...9..2..6.....79.......612...6.5.2.7...8...5...1.....2.4.5.....3 +.......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6... +.......12....35......6...7.7.....3.....4..8..1...........12.....8.....4..5....6.. +1.......2.9.4...5...6...7...5.3.4.......6........58.4...2...6...3...9.8.7.......1 +.....1.2.3...4.5.....6....7..2.....1.8..9..3.4.....8..5....2....9..3.4....67..... diff --git a/sudokus/unique_candidate.txt b/sudokus/unique_candidate.txt new file mode 100644 index 0000000..2c4e1ed --- /dev/null +++ b/sudokus/unique_candidate.txt @@ -0,0 +1,11 @@ +...|...|... +...|...|... +...|...|... +----------- +4..|...|... +...|3.2|... +...|...|..4 +----------- +...|...|... +...|...|... +...|...|... -- 2.45.2