using System;

using System.Linq;

using System.Collections.Generic;

public class Program

{

    public static int SudokuBlock = 3;

    public static int SudokuSize = SudokuBlock * SudokuBlock;

    public static bool Solved = false;

    public static void Sudoku(char[][] board)

    {

        Solved = false;

        BacktrackHelper(ref board, 0, 0);

        DisplaySudoku(board);

    }

    public static void BacktrackHelper(ref char[][] board, int row, int col)

    {

        if (board[row][col] == '.')

        {

            // для текущей точки берем все возможные цифры-кандидаты

            List<int> candidates = GetCandidates(board, row, col);

​

            // проходим по всем кандидатам и запускаем функцию backtracking

            foreach (int digit in candidates)

            {

                if (board[row][col] == '.')

                {

                    char candidate = (char)(digit + 48);

​

                    // делаем предположение

                    board[row][col] = candidate;

​

                    GoNextNumbers(ref board, row, col);

​

                    // снимаем текущее предположение, если оно не привело к решению

                    if (!Solved)

                    {

                        board[row][col] = '.';

                    }

                }

            }

        }

        else

        {

            // переходим к другой ячейке таблицы

            GoNextNumbers(ref board, row, col);

        }

    }

    private static void GoNextNumbers(ref char[][] board, int row, int col)

    {

        // Если мы дошли до последней строки и последнего столбца,

        // значит мы нашли решение

        if (row == SudokuSize - 1 && col == SudokuSize - 1)

        {

            Solved = true;

        } 

        else

        {

            // двигаемся к след.ячейке по столбцу, строке

            if (col == SudokuSize - 1)

            {

                BacktrackHelper(ref board, row + 1, 0);

            }

            else

            {

                BacktrackHelper(ref board, row, col + 1);

            }

        }

    }

    // Можно оптимизировать поиск потенциальных цифр-кандидатов:

    // завести матрицу Rows[9][9], Cols[9][9], Boxes[9][9]:

    // т.е. строка 1 Rows[1][i] - будет хранить цифры i, ктр уже содержатся в ней

    // Cols[col][i] - хранит цифры i, ктр уже находятся в этой колонке

    // Boxes[box][i] - хранит цифры i, ктр уже находятся в этой подблоке.

    // Тогда для определения потенци.кандидата достаточно пройти от 1 до 9

    // И проверить, что Rows[row][candidate] == -1 && Cols[col][candidate] == -1 && Boxes[box][candidate] == -1

    // Т.е. этой цифры еще нет в строке row, столбце col, подблоке box.

    public static List<int> GetCandidates(char[][] board, int row, int col)

    {

        var result = new List<int>();

        var hashSet = new HashSet<int>();

​

        // Брутфорс: для ячейки [row,col] проходим по строке row и столбцу col

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

        {

            if (board[row][i] != '.')

            {

                int digit = board[row][i] - '0'; // convert to int

                hashSet.Add(digit);

            }

            if (board[i][col] != '.')

            {

                int digit = board[i][col] - '0'; // convert to int

                hashSet.Add(digit);

            }

        }

​

        if (hashSet.Count == SudokuSize)

        {

            return result;

        }

​

        // Также проходим по текущему блоку судоку

        int cubeRow = SudokuBlock * (row / SudokuBlock);

        int cubeCol = SudokuBlock * (col / SudokuBlock);

        for (int r = cubeRow; r < cubeRow + SudokuBlock; r++)

        {

            for (int c = cubeCol; c < cubeCol + SudokuBlock; c++)

            {

                if (board[r][c] != '.')

                {

                    int digit = board[r][c] - '0'; // convert to int   return (char)(d + 48);

                    hashSet.Add(digit);

                }

            }

        }

​

        // возвращаем цифры-кандидады для текущей ячейки

        for (int d = 1; d <= SudokuSize; d++)

        {

            if (!hashSet.Contains(d))

                result.Add(d);

        }

​

        return result;

    }

    private static void DisplaySudoku(char[][] board)

    {

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

        {

            for (int col = 0; col < SudokuSize; col++)

            {

                string colMargin = " ";

                if ((col + 1) % SudokuBlock == 0) colMargin = "   ";

​

                Console.Write(board[row][col].ToString() + colMargin);

            }

            string rowMargin = "";

            if ((row + 1) % SudokuBlock == 0) rowMargin = "\n";

            Console.WriteLine(rowMargin);

        }

    }

    public static void SudokuTest()

    {

        Console.WriteLine("\nSudoku tests\n");

        var board = new char[][]

        {

            new char[] { '5','3','.','.','7','.','.','.','.' },

            new char[] { '6','.','.','1','9','5','.','.','.' },

            new char[] { '.','9','8','.','.','.','.','6','.' },

            new char[] { '8','.','.','.','6','.','.','.','3' },

            new char[] { '4','.','.','8','.','3','.','.','1' },

            new char[] { '7','.','.','.','2','.','.','.','6' },

            new char[] { '.','6','.','.','.','.','2','8','.' },

            new char[] { '.','.','.','4','1','9','.','.','5' },

            new char[] { '.','.','.','.','8','.','.','7','9' }

        };

        Sudoku(board);

        Console.WriteLine("---------------------\n");

​

        board = new char[][]

        {

            new char[] { '5','.','.',  '2','.','8',  '.','.','1' },

            new char[] { '.','.','.',  '3','9','7',  '.','.','.' },

            new char[] { '.','.','3',  '1','.','4',  '8','.','.' },

​

            new char[] { '3','7','1',  '.','.','.',  '6','8','9' },

            new char[] { '.','5','.',  '.','.','.',  '.','7','.' },

            new char[] { '8','9','6',  '.','.','.',  '5','2','4' },

​

            new char[] { '.','.','4',  '6','.','3',  '9','.','.' },

            new char[] { '.','.','.',  '5','1','2',  '.','.','.' },

            new char[] { '6','.','.',  '8','.','9',  '.','.','2' }

        };

        Sudoku(board);

        Console.WriteLine("---------------------\n");

    }

    public static void Main()

    {

        Console.WriteLine("UniLecs");

        // Tests

        SudokuTest();

    }

}