using System;

using System.Collections.Generic;

using System.Drawing;

using System.Linq;

​

public class Solution

{

    public void SolveSudoku(char[][] board)

    {

        // Want to solve with integers (Allows more general solution)

        // Doubles memory but oh well

        int[,] iBoard = board.Convert(c => c == '.' ? default(int) : c - '0');

        Soduku.Solve(iBoard);

        board.CopyFrom(iBoard, i => (char)('0' + i));

    }

}

​

public static class Soduku

{

    public static void Solve(int[,] board)

    {

        if (board is null)

            throw new ArgumentNullException(nameof(board));

​

        int N = board.GetLength(0);

        if (N != board.GetLength(1))

            throw new ArgumentException("Board must be square.", nameof(board));

        int n = (int)Math.Sqrt(N); // ex. for standard Soduku n=3 and N=9

        if (n * n != N)

            throw new ArgumentException("Board dimensions are invalid.", nameof(board));

​

        // Note: not validating individual entries on board; assume they fall in range [1, N]

​

        Solve(board, n, N);    

    }

​

    private static void Solve(in int[,] board, in int n, in int N)

    {

        if (!TrySolve(board, n, N, new Point(0, 0)))

            throw new InvalidOperationException("Unsolvable.");

    }

​

    private static bool TrySolve(in int[,] board, in int n, in int N, in Point start)

    {

        if (start.Y == N)

            return true;

        if (board[start.Y, start.X] == default)

        {

            foreach (int candidate in GetCandidates(board, n, N, start))

            {

                board[start.Y, start.X] = candidate;

                if (TrySolve(board, n, N, start))

                    return true;

                board[start.Y, start.X] = default; // backtrack

            }

            return false;

        }

​

        // Iterate pts in left-to-right, top-to-bottom order.

        // It doesn't matter the order, as long as we visit

        // every point once.

        Point next = start.X + 1 == N

            ? new Point(0, start.Y + 1)

            : new Point(start.X + 1, start.Y);

​

        return TrySolve(board, n, N, next);

    }

​

    private static IEnumerable<int> GetCandidates(in int[,] board, in int n, in int N, in Point point)

    {

        var candidates = Enumerable.Range(1, N); 

        var used = GetVerticalNumbers(board, N, point)

            .Union(GetHorizontalNumbers(board, N, point))

            .Union(GetSubsquareNumbers(board, n, N, point));

        return candidates.Except(used);

    }

​

    private static IEnumerable<int> GetVerticalNumbers(int[,] board, in int N, Point point)

    {

        return Enumerable.Range(0, N).Select(y => board[y, point.X]).Where(i => i != default);

    }

​

    private static IEnumerable<int> GetHorizontalNumbers(int[,] board, in int N, Point point)

    {

        return Enumerable.Range(0, N).Select(x => board[point.Y, x]).Where(i => i != default);

    }

​

    private static IEnumerable<int> GetSubsquareNumbers(int[,] board, int n, int N, Point point)

    {

        return Enumerable.Range(point.Y / n * n, n)

            .SelectMany(y => Enumerable.Range(point.X / n * n, n).Select(x => board[y, x]))

            .Where(i => i != default);

    }

}

​

public static class JaggedArrayExtensions

{

    public static U[,] Convert<T, U>(this T[][] arr, Func<T, U> converter)

    {

        if (arr is null)

            throw new ArgumentNullException(nameof(arr));

        if (converter is null)

            throw new ArgumentNullException(nameof(converter));

​

        if (arr.Length == 0)

            return new U[0, 0];

        int m = arr.Length, n = arr[0].Length;

        U[,] result = new U[m, n];

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

        {

            if (arr[i].Length != n)

                throw new ArgumentException("Array of arrays should be square.", nameof(arr));

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

                result[i, j] = converter(arr[i][j]);

        }

        return result;

    }

​

    public static void CopyFrom<T, U>(this U[][] target, T[,] source, Func<T, U> converter)

    {

        if (target is null)

            throw new ArgumentNullException(nameof(target));

        if (source is null)

            throw new ArgumentNullException(nameof(source));

        if (converter is null)

            throw new ArgumentNullException(nameof(converter));

​

        int m = target.Length;

        if (m != source.GetLength(0))

            throw new ArgumentException();

        if (m == 0)

            return;

        int n = target[0].Length;

        if (n != source.GetLength(1))

            throw new ArgumentException();

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

        {

            if (target[i].Length != n)

                throw new ArgumentException();

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

                target[i][j] = converter(source[i, j]);

        }

    }

}