// 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

​

​

using System;

using System.Text;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    private static readonly IEnumerable<int> defValues = Enumerable.Range(1, 9);

    public static void Main()

    {

        var board = new int[9, 9]

        {

            {5,3,0,0,7,0,0,0,0},

            {6,0,0,1,9,5,0,0,0},

            {0,9,8,0,0,0,0,6,0},

            {8,0,0,0,6,0,0,0,3},

            {4,0,0,8,0,3,0,0,1},

            {7,0,0,0,2,0,0,0,6},

            {0,6,0,0,0,0,2,8,0},

            {0,0,0,4,1,9,0,0,5},

            {0,0,0,0,8,0,0,7,9}

        };

        SolveSudoku(board);

    }

​

    public static void SolveSudoku(int[,] board)

    {

        Console.WriteLine("Input");

        WriteBoard(board);

        int rows = board.GetLength(0);

        int cols = board.GetLength(1);

        if (rows != 9 || cols != 9)

        {

            Console.WriteLine("Sudoku must be 9x9 in size");

            return;

        }

        try

        {

            //

            int found = 0;

            do

            {

                found = 0;

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

                {

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

                    {

                        //try to find value for for empty cells

                        if (board[i, j] == 0)

                        {

                            found += FindCellValues(board, i, j, rows, cols);

                        }

                    }

                }           

            } while (found > 0);

            // loop iterates while new values were found

            Console.WriteLine("Output");

            WriteBoard(board);

            bool valid = Validate(board);

            Console.WriteLine("Sudoku was solved: " + valid);

        }

        catch (SudokuException sex)

        {

            Console.WriteLine("There is an error when solving: " + sex.Message);

        }            

    }

​

​

​

    private static int FindCellValues(int[,] board, int i, int j, int rows, int cols)

    {   

        if (board[i, j] > 0)

            return 0;

        int squareRow = (i / 3) * 3, squareCol = (j / 3) * 3;

        // values in row, column and square

        List<int> deniedValues = new List<int>();

        for (int j2 = 0; j2 < cols; j2++)

            if (j2 != j && board[i, j2] > 0)

        {

            deniedValues.Add(board[i, j2]);

        }

        for (int i2 = 0; i2 < rows; i2++)

            if (i2 != i && board[i2, j] > 0)

        {

            deniedValues.Add(board[i2, j]);

        }

        for (int i3 = squareRow; i3 < squareRow + 3; i3++)

        {

            for (int j3 = squareCol; j3 < squareCol + 3; j3++)

            {

                if (i3 != i && j3 != j && board[i3, j3] > 0)

                {

                    deniedValues.Add(board[i3, j3]);

                }

            }

        }

        var res = defValues.Except(deniedValues).ToArray();

        if (res.Length == 1)

        {

            board[i, j] = res[0];

            return 1;            

        }

        if (res.Length == 0)

            throw new SudokuException("Sudoku hasn't solution");

        return 0;

    }

    private static bool Validate(int[,] board)

    {

        for (int i = 0; i < board.GetLength(0); i++)

        {

            HashSet<int> row = new HashSet<int>();

            for (int j = 0; j < board.GetLength(1); j++)

            {

                if (board[i, j] > 0)

                    row.Add(board[i, j]);

            }

            if (row.Count < 9)

                return false;

        }

        for (int j = 0; j < board.GetLength(1); j++)

        {

            HashSet<int> col = new HashSet<int>();

            for (int i = 0; i < board.GetLength(0); i++)

            {

                if (board[i, j] > 0)

                    col.Add(board[i, j]);

            }

            if (col.Count < 9)

                return false;

        }

        for (int sqi = 0; sqi < board.GetLength(0) / 3; sqi++)

        {

            for (int sqj = 0; sqj < board.GetLength(1) / 3; sqj++)

            {

                HashSet<int> square = new HashSet<int>();

                for (int i = sqi * 3; i < sqi * 3 + 3; i++)

                    for (int j = sqj * 3; j < sqj * 3 + 3; j++)

                    if (board[i, j] > 0)

                    square.Add(board[i, j]);

                    if (square.Count < 9)

                    return false;

                    }

        }

        return true;

    }

    public static void WriteBoard(int[,] 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] + " | ");

            }

            sb.AppendLine();

            sb.AppendLine("-------------------------------------");

        }

        Console.WriteLine(sb.ToString());

    }

}

​

​

​

public class SudokuException : Exception

{

    public SudokuException() : base()

    {

    }

    public SudokuException(string message) : base(message)

    {

    }

}