Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
open System
type Sector = | TopLeft = 1 | TopMiddle = 2 | TopRight = 3 | CenterLeft = 4 | CenterMiddle = 5 | CenterRight = 6 | BottomLeft = 7 | BottomMiddle = 8 | BottomRight = 9
type Position = { Rank : Rank; File : File }
and File = | A = 1 | B = 2 | C = 3 | D = 4 | E = 5 | F = 6 | G = 7 | H = 8 | I = 9
and Rank = | One = 1 | Two = 2 | Three = 3 | Four = 4 | Five = 5 | Six = 6 | Seven = 7 | Eight = 8 | Nine = 9
type Grid = Map<Position, int>
let lengthOfSecondItemInTuple e = (snd e) |> Array.length
let allPositions = [for r in 1..9 do for f in 1..9 do yield { Rank = enum<Rank>(r) ; File = enum<File>(f)}]
let positionsToCheck =
let sectorMap =[({Rank = Rank.One; File = File.A;}, Sector.TopLeft)
({Rank = Rank.One; File = File.B;}, Sector.TopLeft)
({Rank = Rank.One; File = File.C;}, Sector.TopLeft)
({Rank = Rank.One; File = File.D;}, Sector.TopMiddle)
({Rank = Rank.One; File = File.E;}, Sector.TopMiddle)
({Rank = Rank.One; File = File.F;}, Sector.TopMiddle)
({Rank = Rank.One; File = File.G;}, Sector.TopRight)
({Rank = Rank.One; File = File.H;}, Sector.TopRight)
({Rank = Rank.One; File = File.I;}, Sector.TopRight)
({Rank = Rank.Two; File = File.A;}, Sector.TopLeft)
({Rank = Rank.Two; File = File.B;}, Sector.TopLeft)
({Rank = Rank.Two; File = File.C;}, Sector.TopLeft)
({Rank = Rank.Two; File = File.D;}, Sector.TopMiddle)
({Rank = Rank.Two; File = File.E;}, Sector.TopMiddle)
({Rank = Rank.Two; File = File.F;}, Sector.TopMiddle)
({Rank = Rank.Two; File = File.G;}, Sector.TopRight)
({Rank = Rank.Two; File = File.H;}, Sector.TopRight)
({Rank = Rank.Two; File = File.I;}, Sector.TopRight)
({Rank = Rank.Three; File = File.A;}, Sector.TopLeft)
({Rank = Rank.Three; File = File.B;}, Sector.TopLeft)
({Rank = Rank.Three; File = File.C;}, Sector.TopLeft)
({Rank = Rank.Three; File = File.D;}, Sector.TopMiddle)
({Rank = Rank.Three; File = File.E;}, Sector.TopMiddle)
({Rank = Rank.Three; File = File.F;}, Sector.TopMiddle)
({Rank = Rank.Three; File = File.G;}, Sector.TopRight)
({Rank = Rank.Three; File = File.H;}, Sector.TopRight)
({Rank = Rank.Three; File = File.I;}, Sector.TopRight)
({Rank = Rank.Four; File = File.A;}, Sector.CenterLeft)
({Rank = Rank.Four; File = File.B;}, Sector.CenterLeft)
({Rank = Rank.Four; File = File.C;}, Sector.CenterLeft)
({Rank = Rank.Four; File = File.D;}, Sector.CenterMiddle)
({Rank = Rank.Four; File = File.E;}, Sector.CenterMiddle)
({Rank = Rank.Four; File = File.F;}, Sector.CenterMiddle)
({Rank = Rank.Four; File = File.G;}, Sector.CenterRight)
({Rank = Rank.Four; File = File.H;}, Sector.CenterRight)
({Rank = Rank.Four; File = File.I;}, Sector.CenterRight)
({Rank = Rank.Five; File = File.A;}, Sector.CenterLeft)
({Rank = Rank.Five; File = File.B;}, Sector.CenterLeft)
({Rank = Rank.Five; File = File.C;}, Sector.CenterLeft)
({Rank = Rank.Five; File = File.D;}, Sector.CenterMiddle)
({Rank = Rank.Five; File = File.E;}, Sector.CenterMiddle)
({Rank = Rank.Five; File = File.F;}, Sector.CenterMiddle)
({Rank = Rank.Five; File = File.G;}, Sector.CenterRight)
({Rank = Rank.Five; File = File.H;}, Sector.CenterRight)
({Rank = Rank.Five; File = File.I;}, Sector.CenterRight)
({Rank = Rank.Six; File = File.A;}, Sector.CenterLeft)
({Rank = Rank.Six; File = File.B;}, Sector.CenterLeft)
({Rank = Rank.Six; File = File.C;}, Sector.CenterLeft)
({Rank = Rank.Six; File = File.D;}, Sector.CenterMiddle)
({Rank = Rank.Six; File = File.E;}, Sector.CenterMiddle)
({Rank = Rank.Six; File = File.F;}, Sector.CenterMiddle)
({Rank = Rank.Six; File = File.G;}, Sector.CenterRight)
({Rank = Rank.Six; File = File.H;}, Sector.CenterRight)
({Rank = Rank.Six; File = File.I;}, Sector.CenterRight)
({Rank = Rank.Seven; File = File.A;}, Sector.BottomLeft)
({Rank = Rank.Seven; File = File.B;}, Sector.BottomLeft)
({Rank = Rank.Seven; File = File.C;}, Sector.BottomLeft)
({Rank = Rank.Seven; File = File.D;}, Sector.BottomMiddle)
({Rank = Rank.Seven; File = File.E;}, Sector.BottomMiddle)
({Rank = Rank.Seven; File = File.F;}, Sector.BottomMiddle)
({Rank = Rank.Seven; File = File.G;}, Sector.BottomRight)
({Rank = Rank.Seven; File = File.H;}, Sector.BottomRight)
({Rank = Rank.Seven; File = File.I;}, Sector.BottomRight)
({Rank = Rank.Eight; File = File.A;}, Sector.BottomLeft)
({Rank = Rank.Eight; File = File.B;}, Sector.BottomLeft)
({Rank = Rank.Eight; File = File.C;}, Sector.BottomLeft)
({Rank = Rank.Eight; File = File.D;}, Sector.BottomMiddle)
({Rank = Rank.Eight; File = File.E;}, Sector.BottomMiddle)
({Rank = Rank.Eight; File = File.F;}, Sector.BottomMiddle)
({Rank = Rank.Eight; File = File.G;}, Sector.BottomRight)
({Rank = Rank.Eight; File = File.H;}, Sector.BottomRight)
({Rank = Rank.Eight; File = File.I;}, Sector.BottomRight)
({Rank = Rank.Nine; File = File.A;}, Sector.BottomLeft)
({Rank = Rank.Nine; File = File.B;}, Sector.BottomLeft)
({Rank = Rank.Nine; File = File.C;}, Sector.BottomLeft)
({Rank = Rank.Nine; File = File.D;}, Sector.BottomMiddle)
({Rank = Rank.Nine; File = File.E;}, Sector.BottomMiddle)
({Rank = Rank.Nine; File = File.F;}, Sector.BottomMiddle)
({Rank = Rank.Nine; File = File.G;}, Sector.BottomRight)
({Rank = Rank.Nine; File = File.H;}, Sector.BottomRight)
({Rank = Rank.Nine; File = File.I;}, Sector.BottomRight)] |> Map.ofList
let allPositionsBySector = allPositions |> List.groupBy (fun n -> sectorMap.[n]) |> Map.ofList
allPositions |> List.map (fun n -> (n, [for r in 1..9 do
yield { Rank = enum<Rank>(r); File = n.File }
yield { Rank = n.Rank; File = enum<File>(r); } ]
@ allPositionsBySector.[sectorMap.[n]] |> List.filter (fun m -> m <> n) |> Set.ofList )) |> Map.ofList
let asString (grid : Grid) =
let stringValues = allPositions |> List.map (fun position -> if grid.[position] = 0 then "-" else sprintf "%i" grid.[position]) |> Array.ofList
String.Join(",", stringValues)
// expect a string like "A1,B1,C1," (etc, till I9)
let parseGrid (puzzle : string) : Grid option =
let m = puzzle.Split(",".ToCharArray(), System.StringSplitOptions.None)
let tryForValue c =
let success, value = System.Int32.TryParse(c)
if success then value else 0
let values = Array.toList m |> List.map tryForValue
if List.length values <> 81 then None
else
let gridAsList = List.zip allPositions values
Some (Map.ofList gridAsList)
let renderGrid (grid : Grid) =
System.Environment.NewLine + String.Join("", [|
for r in 1..9
do
if r > 1 && r % 3 = 1 then yield "*********************************" + System.Environment.NewLine
for f in 1..9
do
let pos = { Rank = enum<Rank>(r) ; File = enum<File>(f)}
if f > 1 && f % 3 = 1 then yield " | "
match grid.[pos] with
| 0 -> yield " - "
| m -> yield sprintf " %i " m
yield System.Environment.NewLine
|])
// given a grid, and a position, return an integer set of available values
// if the list is empty, the grid cannot be solved with the numbers as they are
let getAvailableValues (grid : Grid) position =
if grid.[position] > 0 then
position, [|grid.[position]|]
else
let currentlySelectedValues = positionsToCheck.[position] |> Set.map (fun p -> grid.[p])
let availableValues = set [1..9]
position, (Set.difference availableValues currentlySelectedValues) |> Set.toArray
let isNotSolvable solutions =
if List.isEmpty solutions then false
else
let test = solutions |> List.minBy lengthOfSecondItemInTuple
snd test |> Array.isEmpty
let isSolved solutions =
if List.isEmpty solutions then false
else
let test = solutions |> List.maxBy lengthOfSecondItemInTuple
snd test |> Array.length = 1
// Solve a grid, if possible.
let solve grid =
let rec createSolution g =
let possibleValuesByPosition = allPositions
|> List.map (fun n -> getAvailableValues g n)
if isNotSolvable possibleValuesByPosition then
None
elif isSolved possibleValuesByPosition then
let mapToSingleValue (ps, m : int[]) = (ps, m.[0])
let result = possibleValuesByPosition |> List.map mapToSingleValue |> Map.ofList
Some result
else
let moreThanOnePossibleAnswer e = (snd e) |> Array.length > 1
let (ps, l) = possibleValuesByPosition |> List.filter moreThanOnePossibleAnswer |> List.minBy lengthOfSecondItemInTuple
let notTheCurrentPosition key _ = key <> ps
let possibleAnswers = seq [for i in l do
let newGrid = (g |> Map.filter notTheCurrentPosition).Add(ps, i)
let possibleSolution = createSolution newGrid
if Option.isSome (possibleSolution) then yield (Option.get possibleSolution)
]
if Seq.isEmpty possibleAnswers then
None
else
Some (Seq.head possibleAnswers)
createSolution grid
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.