(03-30-2015 04:35 AM)brouhaha Wrote: I wrote a recursive Python program to do a search with backtracking, and it finds 12 solutions, but only one is unique and the remainder are rotations and/or reflections.
Detecting the rotations and reflections is easy enough. Only accept a case where the top left corner is the lowest value of any corner and the value to its right is smaller than the value below and to the left. Using my nomenclature:
Code:
a b c
d e f g
h i j k l
m n o p
q r s
a = min(a, c, h, l, q, s) and b < d.
These restrictions should be encoded into the search algorithm directly to increase pruning possibilities.
Quote:It would be much faster if written in C.
It is
My program executes completely in under 0.01 seconds on a slower machine. Adding in the reflection and rotation constrains, reduces this by a factor of five.
Pauli
Code:
#include <stdio.h>
/*
a b c
d e f g
h i j k l
m n o p
q r s
*/
int main() {
unsigned char usedbuf[120], *used;
for (int i=0; i<120; i++)
usedbuf[i] = 1;
used = usedbuf + 60;
for (int i=1; i<20; i++) used[i] = 0;
for (int a=1; a<20; a++) {
used[a] = 1;
for (int b=1; b<20; b++) {
if (used[b]) continue;
int c = 38 - a - b;
if (used[c] || c <= b || c < a) continue;
used[b] = used[c] = 1;
for (int d=1; d<20; d++) {
if (used[d]) continue;
int h = 38 - a - d;
if (used[h] || d == h || h < a) continue;
used[d] = used[h] = 1;
for (int g=1; g<20; g++) {
if (used[g]) continue;
int l = 38 - c - g;
if (used[l] || l == g || l < a) continue;
used[l] = used[g] = 1;
for (int m=1; m<20; m++) {
if (used[m]) continue;
int q = 38 - m - h;
if (used[q] || m == q || q < a) continue;
used[m] = used[q] = 1;
for (int p=1; p<20; p++) {
if (used[p]) continue;
int s = 38 - p - l;
if (used[s] || p == s || s < a) continue;
int r = 38 - s - q;
if (used[r] || r == s || r == p) continue;
used[p] = used[s] = used[r] = 1;
for (int e=1; e<20; e++) {
if (used[e]) continue;
int f = 38 - d - e - g;
if (used[f] || e == f) continue;
int i = 38 - b - e - m;
if (used[i] || i == f || i == e) continue;
int k = 38 - b - f - p;
if (used[k] || k == i || k == f || k == e) continue;
used[e] = used[f] = used[i] = used[k] = 1;
int o = 38 - r - k - g;
if (used[o]) goto ex;
int n = 38 - i - d - r;
if (used[n] || n==o) goto ex;
int j = 38 - a - e - o - s;
if (used[j] || j==o || j==n) goto ex;
printf(" %3d %3d %3d\n", a, b, c);
printf(" %3d %3d %3d %3d\n", d, e, f, g);
printf("%3d %3d %3d %3d %3d\n", h, i, j, k, l);
printf(" %3d %3d %3d %3d\n", m, n, o, p);
printf(" %3d %3d %3d\n\n", q, r, s);
ex: used[e] = used[f] = used[i] = used[k] = 0;
}
used[p] = used[s] = used[r] = 0;
}
used[m] = used[q] = 0;
}
used[l] = used[g] = 0;
}
used[d] = used[h] = 0;
}
used[b] = used[c] = 0;
}
used[a] = 0;
}
}
Search
Member List
Calendar
Help
