using System.Diagnostics;

int d = 4;
int magicNumber = 34;

bool[] taken = new bool[d * d + 1];
taken[0] = true;

int[,] state = {
    {15, 0, 0, 0},
    {0, 0, 9, 0},
    {0, 0, 0, 13},
    {0, 11, 0, 0}
};

FillTaken();

var sw = new Stopwatch();
sw.Start();

Dfs((0, 0));

sw.Stop();
Console.WriteLine("Exec time: " + sw.ElapsedMilliseconds + "ms");

void FillTaken() {
    for (int i = 0; i < d; i++) {
        for (int j = 0; j < d; j++) {
            if (state[i, j] != 0) {
                taken[state[i, j]] = true;
            }
        }
    }
}

bool CheckRow(int r) {
    int sum = 0;
    for (int i = 0; i < d; i++) {
        sum += state[r, i];
        if (state[r, i] == 0) {
            return true;
        }
    }

    return sum == magicNumber;
}

bool CheckCol(int c) {
    int sum = 0;
    for (int i = 0; i < d; i++) {
        sum += state[i, c];
        if (state[i, c] == 0) {
            return true;
        }
    }

    return sum == magicNumber;
}

bool OnDiagonal(Point p) {
    if (p.Row == p.Col || p.Row + p.Col == d - 1) {
        return true;
    }
    return false;
}

bool CheckDiag(Point p) {
    if (!OnDiagonal(p)) {
        return true;
    }

    bool hasZero1 = false;
    int sum = 0;
    for (int i = 0; i < d; i++) {
        sum += state[i, i];
        if (state[i, i] == 0) {
            hasZero1 = true;
        }
    }

    if (!hasZero1 && sum != magicNumber) {
        return false;
    }

    bool hasZero2 = false;
    sum = 0;
    for (int i = 0; i < d; i++) {
        var c = d - i - 1;
        sum += state[i, c];
        if (state[i, c] == 0) {
            hasZero2 = true;
        }
    }

    if (hasZero2) {
        return true;
    }

    return sum == magicNumber;
}

void PrintState() {
    for (int i = 0; i < d; i++) {
        for (int j = 0; j < d; j++) {
            Console.Write(state[i, j] + " ");
        }
        Console.WriteLine();
    }
}

bool Dfs(Point p) {
    if (taken.All(x => x)) {
        Console.WriteLine("done");
        PrintState();
        return true;
    }

    foreach (var move in Point.Moves) {
        var next = p + move;
        if (!next.InGrid(d, d)) {
            continue;
        }

        if (state[next.Row, next.Col] != 0) {
            continue;
        }

        for (int i = 1; i <= 16; i++) {
            if (taken[i]) {
                continue;
            }
            state[next.Row, next.Col] = i;
            taken[i] = true;
            if (CheckCol(next.Col) && CheckRow(next.Row) && CheckDiag(next)) {
                if (Dfs(next)) {
                    return true;
                }
            }
            state[next.Row, next.Col] = 0;
            taken[i] = false;
        }
    }

    return false;
}

public record struct Point(int Row, int Col) {
    public static readonly Point[] Moves = { (-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1) };
    public static Point operator +(Point a, Point b) => new(a.Row + b.Row, a.Col + b.Col);
    public static implicit operator Point((int Row, int Col) p) => new(p.Row, p.Col);
    public readonly bool InGrid(int rows, int cols) => Row >= 0 && Row < rows && Col >= 0 && Col < cols;
}

done
15 6 12 1
2 7 9 16
3 10 8 13
14 11 5 4
Exec time: 2108ms