using System;

using System.Text;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

​

// Write a program to solve a Sudoku puzzle by filling the empty cells.Empty cells are indicated by 0

// You may assume that there will be only one unique solution.

​

// Input: https://www.screencast.com/t/WfKc0wUWHi

​

// Output: https://www.screencast.com/t/qNLm0Kh59cz

​

public class Program

{

    public static void Main()

    {

        var board = new Board(new []

        {

            new [] {5,3,0,0,7,0,0,0,0},

            new [] {6,0,0,1,9,5,0,0,0},

            new [] {0,9,8,0,0,0,0,6,0},

            new [] {8,0,0,0,6,0,0,0,3},

            new [] {4,0,0,8,0,3,0,0,1},

            new [] {7,0,0,0,2,0,0,0,6},

            new [] {0,6,0,0,0,0,2,8,0},

            new [] {0,0,0,4,1,9,0,0,5},

            new [] {0,0,0,0,8,0,0,7,9}

        });

        SolveSudoku(board);

    }

    public static void SolveSudoku(Board board)

    {

​

        Console.WriteLine("Input");

        WriteBoard(board);

​

​

        board.Solve();

​

        Console.WriteLine("Output");

        WriteBoard(board);

​

        //Test here

        //Write a test to make sure output has correct data

        if (!board.IsSolved())

        {

            Console.WriteLine("ERROR: Board was solved incorrectly");

        }

    }

    public static void WriteBoard(Board board)

    {

        StringBuilder sb = new StringBuilder();

        sb.AppendLine("╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗");

        for (int i = 0; i < 9; i++)

        {

            sb.Append("║ ");

​

            for (int j = 0; j < 9; j++)

            {

                sb.Append(board[i, j] + (j % 3 == 2 ? " ║ " : " │ "));

            }

​

            sb.AppendLine();

            switch(i)

            {

                case 8: sb.AppendLine("╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝"); break;

                case 2:

                case 5: sb.AppendLine("╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣"); break;

                default: sb.AppendLine("╟───┼───┼───╫───┼───┼───╫───┼───┼───╢"); break;

            }

        }

​

        Console.WriteLine(sb.ToString());

    }

}

​

public class Board 

{

    List<List<int>> board;

    public Board(IEnumerable<IEnumerable<int>> board)

    {

        Debug.Assert(board.Count() == 9,"Wrong number of rows");

        for(int i = 0; i < 9; i++)

        {

            Debug.Assert(board.ElementAt(i).Count() == 9, $"Row #{i + 1} has wrong number of columns");

        }

        this.board = board.Select(row => row.ToList()).ToList();        

    }

    public int this[int x,int y]

    {

        get

        {

            return board[x][y];

        }

        set

        {

            board[x][y] = value;

        }

    }

    public List<int> RowValues(int row)

    {

        return board[row];

    }

    public List<int> ColumnValues(int column)

    {

        return board.Select(row => row[column]).ToList();

    }

     public List<int> SquareValues(int row, int column)

     {

        return Enumerable.Range(row / 3 * 3, 3)

            .Select(x => board[x])

            .SelectMany(x => Enumerable.Range(column / 3 * 3, 3).Select(y => x[y]))

            .ToList();

    }

    public List<int> PossibleValues(int row, int column)

    {

        return Enumerable.Range(1, 9)

            .Except(RowValues(row))

            .Except(ColumnValues(column))

            .Except(SquareValues(row, column))

            .ToList();

    }

    public void Solve()

    {

        bool compleated = false;

        while(!compleated)

        {

            bool restart = false;

            for(int row = 0; row < 9; row++)

            {

                if(restart)

                {

                    break;

                }

                for(int column = 0; column < 9; column++)

                {

                    if(restart)

                    {

                        break;

                    }

                    if(board[row][column] !=0)

                    {

                        continue;

                    }

                    var posible = PossibleValues(row, column);

                    if(posible.Count == 1)

                    {

                        board[row][column] = posible[0];

                            restart = true;

                            continue;

                    }

                }

            }

            if(!restart)

            {

                compleated = true;

            }

        }

    }

    public bool CheckRow(int row)

    {

        var values = RowValues(row);

        return values.Count() == 9 && values.Sum() == 45;

    }

    public bool CheckColumn(int column)

    {

        var values = ColumnValues(column);

        return values.Count() == 9 && values.Sum() == 45;

    }

​

    public bool CheckSquare(int row, int column)

    {

        var values = SquareValues(row, column);

        return values.Count() == 9 && values.Sum() == 45;

    }

​

    public bool IsSolved()

    {

        return

        Enumerable.Range(0, 9).All(row => CheckRow(row)) &&

        Enumerable.Range(0, 9).All(column => CheckColumn(column)) &&

        new[] { 0, 3, 6 }.All(row => new[] { 0, 3, 6 }.All(column => CheckSquare(row, column)));

    }

} 

​

​

​

​

​