DEV Community

Stanislav Berkov
Stanislav Berkov

Posted on

Magic square problem and solver in C#

My 2nd grade daughter get the following math problem:

Image description

I tried to solve it for couple hours but no luck. Then I wrote C# program that employed DFS approach

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;
}
Enter fullscreen mode Exit fullscreen mode

Result

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

Quite long time for i7 12700H. Are there any better ways to solve it, especially that 2nd grader can use?

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay