new puzzle challenge
03-30-2015, 04:50 AM
Post: #5
 Paul Dale Senior Member Posts: 1,839 Joined: Dec 2013
RE: new puzzle challenge
(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;
}
}
 « Next Oldest | Next Newest »

 Messages In This Thread new puzzle challenge - Don Shepherd - 03-30-2015, 02:30 AM RE: new puzzle challenge - Paul Dale - 03-30-2015, 03:19 AM RE: new puzzle challenge - Claudio L. - 03-30-2015, 02:34 PM RE: new puzzle challenge - Claudio L. - 03-30-2015, 04:58 PM RE: new puzzle challenge - Paul Dale - 03-30-2015, 10:11 PM RE: new puzzle challenge - Claudio L. - 03-31-2015, 12:40 PM RE: new puzzle challenge - Claudio L. - 03-31-2015, 05:31 PM RE: new puzzle challenge - Gilles - 03-31-2015, 06:00 PM RE: new puzzle challenge - Claudio L. - 03-31-2015, 10:03 PM RE: new puzzle challenge - Claudio L. - 04-01-2015, 12:25 PM RE: new puzzle challenge - Gilles - 04-01-2015, 07:22 PM RE: new puzzle challenge - Claudio L. - 04-02-2015, 10:53 PM RE: new puzzle challenge - Paul Dale - 04-02-2015, 11:11 PM RE: new puzzle challenge - Claudio L. - 04-04-2015, 07:02 PM RE: new puzzle challenge - Paul Dale - 04-04-2015, 11:43 PM RE: new puzzle challenge - Claudio L. - 04-05-2015, 02:29 AM RE: new puzzle challenge - Paul Dale - 04-05-2015, 03:24 AM RE: new puzzle challenge - Claudio L. - 04-03-2015, 11:31 AM RE: new puzzle challenge - Claudio L. - 04-03-2015, 07:04 PM RE: new puzzle challenge - rprosperi - 04-03-2015, 07:36 PM RE: new puzzle challenge - Han - 04-03-2015, 08:09 PM RE: new puzzle challenge - Claudio L. - 04-04-2015, 12:53 PM RE: new puzzle challenge - Paul Dale - 03-30-2015, 04:00 AM RE: new puzzle challenge - brouhaha - 03-30-2015, 04:35 AM RE: new puzzle challenge - Paul Dale - 03-30-2015 04:50 AM RE: new puzzle challenge - Tugdual - 03-30-2015, 05:45 AM RE: new puzzle challenge - Don Shepherd - 03-30-2015, 11:44 AM RE: new puzzle challenge - Don Shepherd - 03-30-2015, 04:40 PM RE: new puzzle challenge - RayAtHP - 04-02-2015, 07:32 PM RE: new puzzle challenge - Don Shepherd - 04-02-2015, 08:30 PM RE: new puzzle challenge - RayAtHP - 04-02-2015, 08:58 PM RE: new puzzle challenge - Don Shepherd - 04-02-2015, 10:08 PM RE: new puzzle challenge - PANAMATIK - 04-03-2015, 08:43 PM RE: new puzzle challenge - Claudio L. - 04-04-2015, 12:48 PM RE: new puzzle challenge - Don Shepherd - 04-04-2015, 03:06 PM RE: new puzzle challenge - Claudio L. - 04-04-2015, 06:44 PM

User(s) browsing this thread: 1 Guest(s)