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?

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

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