--- /dev/null
+\r
+Microsoft Visual Studio Solution File, Format Version 12.00\r
+# Visual Studio 2012\r
+Project("{f2a71f9b-5d33-465a-a702-920d77279786}") = "SudokuSolver", "SudokuSolver\SudokuSolver.fsproj", "{244C26E9-4AA3-42E2-BFD9-4CFB848C7230}"\r
+EndProject\r
+Global\r
+ GlobalSection(SolutionConfigurationPlatforms) = preSolution\r
+ Debug|x86 = Debug|x86\r
+ Release|x86 = Release|x86\r
+ EndGlobalSection\r
+ GlobalSection(ProjectConfigurationPlatforms) = postSolution\r
+ {244C26E9-4AA3-42E2-BFD9-4CFB848C7230}.Debug|x86.ActiveCfg = Debug|x86\r
+ {244C26E9-4AA3-42E2-BFD9-4CFB848C7230}.Debug|x86.Build.0 = Debug|x86\r
+ {244C26E9-4AA3-42E2-BFD9-4CFB848C7230}.Release|x86.ActiveCfg = Release|x86\r
+ {244C26E9-4AA3-42E2-BFD9-4CFB848C7230}.Release|x86.Build.0 = Release|x86\r
+ EndGlobalSection\r
+EndGlobal\r
--- /dev/null
+module SudokuSolver.AssemblyInfo
+open System.Reflection
+open System.Runtime.CompilerServices
+
+[<assembly: AssemblyTitle("SudokuSolver")>]
+[<assembly: AssemblyDescription("")>]
+[<assembly: AssemblyConfiguration("")>]
+[<assembly: AssemblyCompany("")>]
+[<assembly: AssemblyProduct("")>]
+[<assembly: AssemblyCopyright("gburri")>]
+[<assembly: AssemblyTrademark("")>]
+
+// The assembly version has the format {Major}.{Minor}.{Build}.{Revision}
+
+[<assembly: AssemblyVersion("1.0.0.0")>]
+
+//[<assembly: AssemblyDelaySign(false)>]
+//[<assembly: AssemblyKeyFile("")>]
+
+()
+
--- /dev/null
+module SudokuSolver.Main
+
+module Solver = Version1
+
+open System
+open System.IO
+
+[<EntryPoint>]
+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
--- /dev/null
+<?xml version="1.0" encoding="utf-8"?>\r
+<Project DefaultTargets="Build" ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">\r
+ <PropertyGroup>\r
+ <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>\r
+ <Platform Condition=" '$(Platform)' == '' ">x86</Platform>\r
+ <ProjectGuid>{244C26E9-4AA3-42E2-BFD9-4CFB848C7230}</ProjectGuid>\r
+ <OutputType>Exe</OutputType>\r
+ <RootNamespace>SudokuSolver</RootNamespace>\r
+ <AssemblyName>SudokuSolver</AssemblyName>\r
+ </PropertyGroup>\r
+ <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|x86' ">\r
+ <DebugSymbols>true</DebugSymbols>\r
+ <DebugType>full</DebugType>\r
+ <Optimize>false</Optimize>\r
+ <OutputPath>bin\Debug</OutputPath>\r
+ <DefineConstants>DEBUG</DefineConstants>\r
+ <ErrorReport>prompt</ErrorReport>\r
+ <Externalconsole>true</Externalconsole>\r
+ <Tailcalls>false</Tailcalls>\r
+ <PlatformTarget>x86</PlatformTarget>\r
+ </PropertyGroup>\r
+ <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|x86' ">\r
+ <DebugSymbols>false</DebugSymbols>\r
+ <DebugType>none</DebugType>\r
+ <Optimize>true</Optimize>\r
+ <OutputPath>bin\Release</OutputPath>\r
+ <ErrorReport>prompt</ErrorReport>\r
+ <PlatformTarget>x86</PlatformTarget>\r
+ <Externalconsole>true</Externalconsole>\r
+ <Tailcalls>true</Tailcalls>\r
+ </PropertyGroup>\r
+ <ItemGroup>\r
+ <Reference Include="mscorlib" />\r
+ <Reference Include="FSharp.Core" />\r
+ <Reference Include="System" />\r
+ <Reference Include="System.Core" />\r
+ <Reference Include="System.Numerics" />\r
+ </ItemGroup>\r
+ <ItemGroup>\r
+ <Compile Include="AssemblyInfo.fs" />\r
+ <Compile Include="Version1.fs" />\r
+ <Compile Include="Version2.fs" />\r
+ <Compile Include="Program.fs" />\r
+ </ItemGroup>\r
+ <Import Project="$(MSBuildExtensionsPath32)\..\Microsoft SDKs\F#\3.1\Framework\v4.0\Microsoft.FSharp.Targets" />\r
+</Project>
\ No newline at end of file
--- /dev/null
+module SudokuSolver.Version1
+
+open System
+open System.IO
+open System.Collections.Generic
+
+let printUsage progname =
+ printfn "Usage: %A <filename>" 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<int>) =
+ 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 }
+
--- /dev/null
+module SudokuSolver.Version2
+
+open System
+open System.IO
+open System.Collections.Generic
+
+let printUsage progname =
+ printfn "Usage: %A <filename>" 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<int>) =
+ 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 }
--- /dev/null
+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
+
--- /dev/null
+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
--- /dev/null
+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
--- /dev/null
+...|6.9|...
+..3|...|9..
+.5.|874|.3.
+-----------
+6.1|...|8.7
+...|.1.|...
+3.7|...|6.9
+-----------
+.7.|185|.4.
+..5|...|1..
+...|2.7|...
+
--- /dev/null
+ | |
+ 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
--- /dev/null
+...|...|...
+...|...|...
+...|.4.|...
+-----------
+...|6..|...
+...|..9|...
+2.8|...|..3
+-----------
+...|.1.|...
+...|.5.|...
+...|...|...
--- /dev/null
+ 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
--- /dev/null
+ | |
+ | |
+ | |
+-----------
+ | |
+ | |
+ | |
+-----------
+ | |
+ | |
+ | |
\ No newline at end of file
--- /dev/null
+ 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
--- /dev/null
+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
--- /dev/null
+11 | |
+ | |
+ | |
+-----------
+ | |
+ | |
+ | |
+-----------
+ | |
+ | |
+ | |
\ No newline at end of file
--- /dev/null
+4...3.......6..8..........1....5..9..8....6...7.2........1.27..5.3....4.9........
\ No newline at end of file
--- /dev/null
+..............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.....
--- /dev/null
+...|...|...
+...|...|...
+...|...|...
+-----------
+4..|...|...
+...|3.2|...
+...|...|..4
+-----------
+...|...|...
+...|...|...
+...|...|...
projects / sudokuSolver.git / commitdiff