open System
type Cell = {Number : Option<int>; PossibleNumbers : int list} with
        static member Cell =
            {Number = None; PossibleNumbers = [1..9]}
        member this.SetNumber number =
            {this with Number = Some(number); PossibleNumbers = List<int>.Empty}
        member this.RemovePossible number =
            {this with PossibleNumbers = this.PossibleNumbers |> List.filter (fun x -> x <> number)}
type Board = {Cells : Cell[,]} with
    static member Board =
         { Cells = Array2D.init<Cell> 9 9 (fun _ _ -> Cell.Cell) }
    static member private createIterByCell i j =
        let rowIter = List.init 9 (fun index -> (i, index)) |> List.filter (fun tuple -> snd tuple <> j)
        let colIter = List.init 9 (fun index -> (index, j)) |> List.filter (fun tuple -> fst tuple <> i)
        let topLeft = (i-i%3, j-j%3)
        let sqrIter = List.init 9 (fun index -> (fst topLeft + index/3, snd topLeft + index%3))|> List.filter (fun tuple -> fst tuple <> i || snd tuple <> j)
        Seq.distinct(rowIter @ colIter @ sqrIter) |> Seq.toList
    member this.SetCell i j value =
        let cells = Board.createIterByCell i j
        match value with
        | 0 -> this
        | v ->
            (
                let newArray = this.Cells |> Array2D.mapi (fun row column cell ->
                    match (row, column) with
                    | a, b when a = i && b = j -> cell.SetNumber v
                    | a, b when cells |> List.contains (a, b) -> cell.RemovePossible value
                    | _ -> cell
                )
                {this with Cells = newArray}
            )
    static member private SetBoardRec (board:Board) (values: (int*int*int) list) =
        match values with
        | [] -> board
        | (i, j, value)::tail -> Board.SetBoardRec (board.SetCell i j value) tail
    member this.SetBoard (values: int[,]) =
        let cells = values |> Array2D.mapi (fun i j value -> (i, j, value)) |> Seq.cast<int*int*int> |> Seq.toList
        Board.SetBoardRec this cells
    member this.printBoard =
        ignore([0..8] |> List.map (fun row ->
            ignore ([0..8] |> List.map (fun col ->
                let cell = this.Cells.[row, col]
                match cell.Number with
                | None -> Console.Write("0 ")
                | Some(x) -> Console.Write(x.ToString() + " ")
                ))
            Console.WriteLine()
            ))
let rec solveSudoku (board:Board) =
    let unknownCellsInd =
        Array2D.init 9 9 (fun i j -> (i, j))
        |> Seq.cast<int*int> |> Seq.toList
        |> List.filter (fun tuple -> board.Cells.[fst tuple, snd tuple].Number = None)
    match unknownCellsInd with
    | [] -> (
            printfn "You win"
            board.printBoard
        )
    | _ -> (
            let firstGuess = board.Cells.[fst unknownCellsInd.Head, snd unknownCellsInd.Head]
            let possibleNumbersEnum = (firstGuess.PossibleNumbers |> List.toSeq).GetEnumerator()
            while possibleNumbersEnum.MoveNext() do
                let newBoard = board.SetCell (fst unknownCellsInd.Head) (snd unknownCellsInd.Head) possibleNumbersEnum.Current
                solveSudoku newBoard
        )
    ()
[<EntryPoint>]
let main _ =
    let start = array2D
                    [
                        [|0; 0; 7; 8; 6; 1; 0; 5; 0|];
                        [|0; 1; 8; 4; 5; 3; 0; 0; 0|];
                        [|5; 6; 0; 7; 9; 2; 8; 1; 0|];
                        [|1; 0; 0; 0; 7; 6; 3; 8; 5|];
                        [|0; 0; 0; 3; 4; 5; 0; 0; 1|];
                        [|6; 3; 5; 0; 1; 8; 0; 0; 7|];
                        [|0; 5; 0; 1; 2; 4; 0; 9; 8|];
                        [|0; 0; 1; 6; 8; 9; 5; 0; 0|];
                        [|0; 0; 0; 5; 3; 7; 1; 0; 0|]
                    ]
    let board = Board.Board.SetBoard start
    board.printBoard
    solveSudoku board
    0