My 2nd grade daughter get the following math problem:
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;
}
Result
done
15 6 12 1
2 7 9 16
3 10 8 13
14 11 5 4
Exec time: 2108ms
Quite long time for i7 12700H. Are there any better ways to solve it, especially that 2nd grader can use?
Top comments (0)