public static class FlatMap
{
    // Polyfill over this not existing in the C# implementation of IEnumerable
    // "this" argument attaches this method to IEnumerable instances.
    public static IEnumerable<U> flatMap<T, U>(this IEnumerable<T> list, Func<T,IEnumerable<U>> func)
    {
        foreach (var item in list)
            foreach (var thing in func(item))
                yield return thing;
    }
}

struct SudokuState
{
    // int? is equivalent of Option<i32>, T[,] is syntax sugar for T[][], i.e. [[T]]
    int?[,] board;

    public SudokuState(int?[] input)
    {
        board = new int?[,]{
            { null, null, null, null, null, null, null, null, null},
            { null, null, null, null, null, null, null, null, null},
            { null, null, null, null, null, null, null, null, null},
            { null, null, null, null, null, null, null, null, null},
            { null, null, null, null, null, null, null, null, null},
            { null, null, null, null, null, null, null, null, null},
            { null, null, null, null, null, null, null, null, null},
            { null, null, null, null, null, null, null, null, null},
            { null, null, null, null, null, null, null, null, null},
            };

        int i = 0;
        for (int x = 0; x < 9; x++)
            for (int y = 0; y < 9; y++)
            {
                if (isValidInsertion(x, y, input[i]))
                    board[x, y] = input[i];
                else
                    throw new ArgumentException();
                i++;
            }
    }

    public bool isValidValue(int v)
    {
        return 0 < v && v <= 9;
    }

    public bool isValidInsertion(int x, int y, int? v)
    {
        if (!(0 <= x || x < 9))
        { return false; }
        if (!(0 <= y || y < 9))
        { return false; }
        if (v != null && !isValidValue(v.Value))
        { return false; }

        if (v == null) return true;

        int offx = x - (x % 3);
        int offy = y - (y % 3);
        for (int n = 0; n < 9; n++)
        {
            if (board[x, n] == v)
            {
                return false;
            }
            if (board[n, y] == v)
            {
                return false;
            }
            if (board[offx + n % 3, offy + n / 3] == v)
            {
                return false;
            }
        };
        return true;
    }

    static public SudokuState Insert(SudokuState S, int x, int y, int v)
    {
        var clone = new SudokuState() { board = S.board };
        clone.board[x,y] = v;
        return clone;
    }

    public Tuple<int, int> getFirstEmpty()
    {
        for (int x = 0; x < 9; x++)
            for (int y = 0; y < 9; y++)
                if (board[x,y] == null)
                    return Tuple.Create(x, y);
        return null;
    }

    public IEnumerable<SudokuState> GetSolutions()
    {
        var firstEmptySpace = getFirstEmpty();
        if (firstEmptySpace == null)
            return Enumerable.Repeat(this, 1);
        else
        {
            var state = this;
            int x = firstEmptySpace.Item1;
            int y = firstEmptySpace.Item2;
            return Enumerable.Range(1, 9)
                .Where(v => state.isValidInsertion(x, y, v))
                .Select(v => Insert(state, x, y, v))
                .flatMap(S => S.GetSolutions());
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        var data = new int?[]{
            4, 2, 3, 6, 9, 7, 8, 1, 5,
            6, 9, 1, 5, 3, 8, 4, 7, 2,
            5, 8, 7, 4, 2, 1, 6, 3, 9,
            3, 1, 9, 8, 7, 5, 2, 6, 4,
            2, 5, 6, 1, 4, 9, 3, 8, 7,
            7, 4, 8, 3, 6, 2, 5, 9, 1,
            9, 6, 4, 2, 1, 3, 7, 5, 8,
            1, 3, 5, 7, 8, 4, 9, 2, 6,
            8, 7, 2, 9, 5, 6, 1, 4, null,
            };

        SudokuState game = new SudokuState(data);

        var list = game.GetSolutions().ToArray()[0];

        /* list[0].board is
        4, 2, 3, 6, 9, 7, 8, 1, 5
        6, 9, 1, 5, 3, 8, 4, 7, 2
        5, 8, 7, 4, 2, 1, 6, 3, 9
        3, 1, 9, 8, 7, 5, 2, 6, 4
        2, 5, 6, 1, 4, 9, 3, 8, 7
        7, 4, 8, 3, 6, 2, 5, 9, 1
        9, 6, 4, 2, 1, 3, 7, 5, 8
        1, 3, 5, 7, 8, 4, 9, 2, 6
        8, 7, 2, 9, 5, 6, 1, 4, 3
        */

    }
}