Skip to content

Instantly share code, notes, and snippets.

@skeeto

skeeto/mazelog-2016-09.c

Last active November 8, 2021 15:00
Show Gist options
  • Save skeeto/ade312b93d0a0021e1bc8de9178bd4e3 to your computer and use it in GitHub Desktop.
Save skeeto/ade312b93d0a0021e1bc8de9178bd4e3 to your computer and use it in GitHub Desktop.
Download ZIP
Mazelog Monthly Challenge Solvers
Raw
mazelog-2016-09.c
#include <stdio.h>
static char game[8][8] = {
"nbrnnnnr",
"rbnn n n",
"bnnnrbb ",
"rnrkknnb",
"rbrkk n ",
"bnn r n",
"nnnnn bn",
"n nnnnn",
};
static const char knight[] = {
1, -2, 2, -1, 2, 1, 1, 2, -1, 2, -2, 1, -2, -1, -1, 2
};
static const char bishop[] = {
1, -1, 1, 1, -1, 1, -1, -1
};
static const char rook[] = {
0, -1, 1, 0, 0, 1, -1, 0
};
static const char king[] = {
0, -1, 1, -1, 1, 0, 1, 1, 0, 1, -1, 1, -1, 0, -1, -1
};
static struct {
char x;
char y;
} path[32];
unsigned best = sizeof(path) / sizeof(path[0]);
static void
output(unsigned n)
{
if (n < best) {
best = n;
for (unsigned i = 0; i < n; i++)
printf("%d%c", 8 * path[i].y + path[i].x + 1, " \n"[i == n - 1]);
}
}
#define VALID(x, y) ((x) >= 0 && (x) < 8 && (y) >= 0 && (y) < 8)
static void
solve(unsigned n)
{
if (n == best)
return;
int x = path[n - 1].x;
int y = path[n - 1].y;
if (x == 7 && y == 7) {
output(n);
return;
}
char c = game[y][x];
game[y][x] = '#';
switch (c) {
case 'k':
case 'n': {
const char *base = c == 'n' ? knight : king;
for (int i = 0; i < 8; i++) {
int tx = x + base[i * 2 + 0];
int ty = y + base[i * 2 + 1];
if (VALID(tx, ty)) {
path[n].x = (char)tx;
path[n].y = (char)ty;
solve(n + 1);
}
}
} break;
case 'b':
case 'r': {
const char *base = c == 'r' ? rook : bishop;
for (int i = 0; i < 4; i++) {
int tx = x;
int ty = y;
do {
tx += base[i * 2 + 0];
ty += base[i * 2 + 1];
} while (VALID(tx, ty) && game[ty][tx] == ' ');
if (VALID(tx, ty)) {
path[n].x = (char)tx;
path[n].y = (char)ty;
solve(n + 1);
}
}
} break;
}
game[y][x] = c;
}
int
main(void)
{
solve(1);
return 0;
}
Raw
mazelog-2016-10.c
#include <stdio.h>
#define N 4
static const signed char grid[] = {
+3, -1, +1, -2,
-1, +1, -1, +2,
-1, +0, +0, -1,
-1, +2, +1, +0,
};
static const signed char moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1
};
static int
solve(int *p, int n, int v, int bestn)
{
if (p[n - 1] == N * N - 1) {
/* Found a solution. */
for (int i = 0; i < n; i++)
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n');
bestn = n;
} else if (n < bestn - 1) {
for (int i = 0; i < (int)(sizeof(moves) / sizeof(*moves) / 2); i++) {
int x = p[n - 1] % N;
int y = p[n - 1] / N;
int tx = x + moves[i * 2 + 0] * v;
int ty = y + moves[i * 2 + 1] * v;
int t = ty * N + tx;
if (tx == 0 && ty == 0) {
/* Special rule: (0, 0) resets the value. */
p[n] = 0;
bestn = solve(p, n + 1, grid[0], bestn);
} else if (tx >= 0 && tx < N && ty >= 0 && ty < N &&
grid[t] + v > 0 && grid[t] + v < N) {
p[n] = t;
bestn = solve(p, n + 1, grid[t] + v, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[16] = {0};
solve(path, 1, grid[0], sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2016-11.c
#include <stdio.h>
#define H 5
#define W 6
#define TARGET (W * H - 1)
static const signed char grid[] = {
+3, +0, +1, +1, -2, +1,
+1, -1, +1, +0, +1, +2,
+1, +1, -1, -1, +2, +1,
+1, -1, +0, +2, -2, +1,
+0, -1, +3, -3, +2, +0,
};
static const signed char moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1
};
static int
solve(int *p, int n, int v, int bestn)
{
if (p[n - 1] == TARGET) {
/* Found a solution. */
for (int i = 0; i < n; i++)
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n');
bestn = n;
} else if (n < bestn - 1) {
for (int i = 0; i < (int)(sizeof(moves) / sizeof(*moves) / 2); i++) {
int x = p[n - 1] % W;
int y = p[n - 1] / W;
int tx = x + moves[i * 2 + 0] * v;
int ty = y + moves[i * 2 + 1] * v;
int t = ty * W + tx;
if (tx == 0 && ty == 0) {
/* Special rule: (0, 0) resets the value. */
p[n] = 0;
bestn = solve(p, n + 1, grid[0], bestn);
} else if (tx >= 0 && tx < W &&
ty >= 0 && ty < H &&
grid[t] + v >= 0) {
p[n] = t;
bestn = solve(p, n + 1, grid[t] + v, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[24] = {0};
solve(path, 1, grid[0], sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2016-12.c
#include <stdio.h>
#define W 5
#define H 5
#define T 21
static const struct {
enum { M, A } op;
int value;
} grid[] = {
{M, +0}, {A, +1}, {M, +3}, {A, +2}, {A, -2},
{A, +1}, {M, +4}, {M, +2}, {A, -2}, {A, -2},
{M, +2}, {A, +2}, {A, -2}, {A, +2}, {M, +2},
{A, +2}, {A, -2}, {M, +2}, {M, +4}, {A, +1},
{A, +0}, {A, +2}, {M, +3}, {A, +3}, {A, +1},
};
static const int moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1
};
static int
solve(int *p, int n, int v, int bestn)
{
switch (grid[p[n]].op) {
case M:
v *= grid[p[n]].value;
break;
case A:
v += grid[p[n]].value;
break;
}
if (p[n] == H * W - 1 && v == T) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
for (int i = 0; i < 4; i++) {
int xx = x + moves[i * 2 + 0];
int yy = y + moves[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = xx + yy * W;
bestn = solve(p, n + 1, v, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[24] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2017-01.c
#include <stdio.h>
#include <stdlib.h>
#define W 8
#define H 8
static const signed char grid[] = {
+3, +3, -3, +5, +6, +3, +6, +3,
+3, +6, +6, +3, +3, +5, +6, -3,
+3, -3, -3, +3, +3, +2, +3, +3,
+3, +3, +5, +3, +3, +3, -3, +3,
+2, +3, -3, +3, +3, +3, -3, +3,
-3, +6, +3, +3, +3, -2, +3, -2,
+3, -3, +3, +4, +3, +3, +3, +3,
+3, +3, -3, +6, +3, +3, -3, +0,
};
static const signed char moves[][8] = {
{-1, +0, +1, +0, +0, -1, +0, +1},
{-1, -1, +1, +1, +1, -1, -1, +1},
};
static int
solve(int *p, int n, int m, int bestn)
{
if (p[n] == H * W - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int v = abs(grid[p[n]]);
int x = p[n] % W;
int y = p[n] / W;
if (grid[p[n]] < 0)
m = !m;
for (int i = 0; i < 4; i++) {
int xx = x + v * moves[m][i * 2 + 0];
int yy = y + v * moves[m][i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = xx + yy * W;
bestn = solve(p, n + 1, m, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[24] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2017-02.c
#include <stdio.h>
#define W 8
#define H 8
enum direction {UU, UR, RR, DR, DD, DL, LL, UL};
static const signed char grid[] = {
DD, DR, RR, DR, DD, DR, LL, DL,
UR, DD, DR, DR, DR, RR, UR, DD,
RR, UR, UU, UR, LL, DL, RR, LL,
UR, UR, DL, UL, DR, LL, UU, UL,
UU, DR, DD, UR, LL, UL, DR, UL,
UR, RR, UL, DR, UR, UU, DL, DL,
DR, UL, RR, UR, UU, UL, UU, UL,
UR, LL, UR, UR, UL, UL, RR, -1,
};
static const signed char moves[] = {
+0, -1, +1, -1, +1, +0, +1, +1,
+0, +1, -1, +1, -1, +0, -1, -1,
};
#define VALID(x, y) ((x) >= 0 && (x) < W && (y) >= 0 && (y) < H)
#define VISIT(v, n) ((v) | (1ULL << (n)))
#define VISITED(v, n) ((v) & (1ULL << (n)))
static int
solve(int *p, int n, int m, int bestn, unsigned long long visit)
{
if (p[n] == H * W - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int sx = p[n] % W;
int sy = p[n] / W;
int dx = moves[grid[p[n]] * 2 + 0];
int dy = moves[grid[p[n]] * 2 + 1];
for (int x = sx + dx, y = sy + dy; VALID(x, y); x += dx, y += dy) {
int next = x + y * W;
if (!VISITED(visit, next)) {
p[n + 1] = next;
visit = VISIT(visit, next);
bestn = solve(p, n + 1, m, bestn, visit);
}
}
}
return bestn;
}
int
main(void)
{
int path[24] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path), VISIT(0, 1));
return 0;
}
Raw
mazelog-2017-03.c
#include <stdio.h>
#define S 6
enum shape {SC=0x00, ST=0x01, SX=0x02, SP=0x03, SH=0x04, SV=0x05, SS=0x06};
enum color {CB=0x10, CO=0x20, CP=0x30, CG=0x40, CR=0x50, CY=0x60};
static const unsigned char grid[] = {
SC|CB, ST|CO, SX|CP, SX|CG, SC|CR, ST|CG,
SV|CR, ST|CR, ST|CB, SX|CB, SC|CY, SX|CO,
SC|CO, SH|CG, SP|CP, SH|CO, SC|CP, SP|CR,
ST|CO, SH|CB, SV|CB, SS|CO, SS|CR, SH|CR,
ST|CR, SC|CG, SS|CG, SS|CR, SX|CP, SC|CO,
SV|CY, SP|CO, SV|CG, SP|CP, SX|CY, SC|CP,
};
static const signed char moves[] = {
+0, -1, +1, +0, +0, +1, -1, +0,
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] == S * S - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int s = (n % 2) * 4;
int x = p[n] % S;
int y = p[n] / S;
unsigned v = (grid[p[n]] >> s) & 0xf;
for (int d = 0; d < 4; d++) {
for (int r = 1; r < S; r++) {
int cx = x + r * moves[d * 2 + 0];
int cy = y + r * moves[d * 2 + 1];
if (cx < 0 || cx >= S || cy < 0 || cy >= S)
break;
int cp = cy * S + cx;
unsigned cv = (grid[cp] >> s) & 0x0f;
if (v == cv) {
p[n + 1] = cp;
bestn = solve(p, n + 1, bestn);
}
}
}
}
return bestn;
}
int
main(void)
{
int path[24] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2017-04.c
#include <stdio.h>
#define W 5
#define H 5
enum direction { UU, UR, RR, DR, DD, DL, LL, UL };
static const char grid[] = {
RR, DL, DR, DL, LL,
UU, LL, DL, DL, LL,
DR, DR, UL, UL, UR,
UR, LL, UR, DR, DD,
DL, DD, DR, UL, 0
};
static const signed char moves[] = {
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] == H * W - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int v = (grid[p[n]] + n % 4 / 2 * 4) % 8;
int x = p[n] % W;
int y = p[n] / W;
for (int d = 1; d < W; d++) {
int xx = x + d * moves[v * 2 + 0];
int yy = y + d * moves[v * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = xx + yy * W;
bestn = solve(p, n + 1, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[24] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2017-05.c
#include <stdio.h>
#include <stdlib.h>
#define W 5
#define H 5
static const signed char grid[] = {
+3, -1, +1, -1, +1,
+1, +1, +0, -1, -2,
+1, +1, -1, +0, -2,
-1, +1, -1, +1, +3,
+0, -1, +2, +0, +0,
};
static const signed char moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1,
};
static int
solve(int *p, int n, int d, int bestn)
{
if (p[n] == H * W - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int j = x == 0 && y == 0 ? grid[0] : d + grid[p[n]];
if (j > 0) {
for (int i = 0; i < 4; i++) {
int xx = x + j * moves[i * 2 + 0];
int yy = y + j * moves[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = xx + yy * W;
bestn = solve(p, n + 1, j, bestn);
}
}
}
}
return bestn;
}
int
main(void)
{
int path[16] = {0};
solve(path, 0, grid[0], sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2017-06.c
#include <stdio.h>
#include <stdlib.h>
#define W 6
#define H 6
static const char grid[] = {
2, 0, 3, 0, 0, 2,
4, 0, 0, 0, 2, 0,
0, 0, 0, 3, 0, 0,
1, 2, 3, 0, 0, 0,
0, 2, 4, 0, 3, 3,
0, 0, 0, 3, 0, 0,
};
static const signed char moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1,
};
static int
solve(int *p, int n, int j, int bestn)
{
if (p[n] == H * W - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int d = grid[p[n]] ? grid[p[n]] : j;
for (int i = 0; i < 4; i++) {
int xx = x + d * moves[i * 2 + 0];
int yy = y + d * moves[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = xx + yy * W;
bestn = solve(p, n + 1, d, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[16] = {0};
solve(path, 0, grid[0], sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2017-07.c
#include <stdio.h>
#include <stdlib.h>
#define W 7
#define H 7
enum {UU, UR, RR, DR, DD, DL, LL, UL, TT};
static const char grid[] = {
TT, DR, DL, DR, DD, DR, TT,
RR, RR, DL, UL, RR, UL, LL,
UR, UU, UU, UR, LL, LL, LL,
DR, DR, RR, UU, DR, UR, UL,
DR, UR, UU, RR, UU, UU, LL,
UU, UR, DR, RR, UU, DR, DL,
TT, UU, UR, UR, UU, UL, TT,
};
static const signed char moves[] = {
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1,
};
static int
solve(int *p, int n, int bestn)
{
if (grid[p[n]] == TT) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int d = grid[p[n]];
for (int s = 1; ; s++) {
int xx = x + s * moves[d * 2 + 0];
int yy = y + s * moves[d * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = xx + yy * W;
bestn = solve(p, n + 1, bestn);
} else {
break;
}
}
}
return bestn;
}
int
main(void)
{
int path[12] = {24};
solve(path, 0, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2017-08.c
#include <stdio.h>
#define W 5
#define H 5
enum {P, R, B, K, X};
static const char grid[] = {
R, B, P, R, B,
B, R, B, R, P,
P, P, P, B, B,
B, P, P, R, B,
B, P, K, B, X,
};
static const signed char moves[] = {
0, 0, 8, 4, 16, 4, 24, 8,
-1, +0, +1, +0, +0, -1, +0, +1,
-1, -1, +1, +1, -1, +1, +1, -1,
-2, -1, -2, +1, +2, -1, +2, +1,
-1, -2, -1, +2, +1, -2, +1, +2,
};
static int
solve(int *p, int n, int last, int bestn)
{
if (grid[p[n]] == X) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int c = grid[p[n]] ? grid[p[n]] : last;
int off = moves[c * 2 + 0];
int len = moves[c * 2 + 1];
const signed char *m = moves + off;
for (int i = 0; i < len; i++) {
int xx = x + m[i * 2 + 0];
int yy = y + m[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = xx + yy * W;
bestn = solve(p, n + 1, c, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[18] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2017-09.c
#include <stdio.h>
#define W 5
#define H 4
enum {UU, UR, RR, DR, DD, DL, LL, UL, TL, TR};
static const char grid[] = {
DR, TL, DL, TR, TL,
TL, UU, DD, DD, LL,
TL, UR, DR, UL, UU,
TR, TL, TR, LL, 0,
};
static const int moves[] = {
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1
};
int
main(void)
{
long h = 0;
long t = 1;
static char queue[W * H * 16384L];
static long fromq[W * H * 16384L];
static char prevd[W * H * 16384L];
queue[0] = 0;
fromq[0] = -1;
prevd[0] = grid[0];
for (;;) {
int p = queue[h];
int d = prevd[h];
int x = p % W;
int y = p / W;
/* Solution found */
if (p == W * H - 1) {
int n = 0;
int path[32];
while (h >= 0) {
path[n++] = queue[h] + 1;
h = fromq[h];
}
while (n--)
printf("%d%c", path[n], "\n "[!!n]);
break;
}
int v = grid[p];
if (v == TL) {
v = (d + 6) % 8;
} else if (v == TR) {
v = (d + 2) % 8;
}
int dx = moves[v * 2 + 0];
int dy = moves[v * 2 + 1];
for (int i = 1; ; i++) {
int cx = x + i * dx;
int cy = y + i * dy;
if (cx < 0 || cx >= W || cy < 0 || cy >= H)
break;
queue[t] = cy * W + cx;
fromq[t] = h;
prevd[t] = v;
t++;
}
h++;
}
}
Raw
mazelog-2017-10.c
#include <stdio.h>
#define W 6
#define H 6
enum {R = 0x10, G = 0x20, B = 0x30, V = 0x40, O = 0x50};
enum {C = 0x01, D = 0x02, X = 0x03, P = 0x04, A = 0x05};
static const char grid[] = {
B|A, G|C, G|P, G|X, G|A, G|A,
B|P, G|C, B|P, V|P, R|C, O|A,
O|A, O|D, V|X, B|C, O|P, B|A,
R|A, V|C, B|D, O|X, G|A, O|A,
O|X, O|C, B|X, G|P, R|X, G|C,
G|C, O|C, V|X, G|P, B|X, V|D,
};
static const int moves[] = {
+0, -1, +0, +1, +1, +0, -1, +0,
+1, +1, -1, -1, +1, -1, -1, +1,
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int v = grid[p[n]];
int s = v & 0x0f;
int c = v & 0xf0;
const int *m = moves + (n % 2) * 8;
for (int i = 0; i < 4; i++) {
for (int d = 1; ; d++) {
int xx = x + d * m[i * 2 + 0];
int yy = y + d * m[i * 2 + 1];
if (xx < 0 || xx >= W || yy < 0 || yy >= H)
break;
int t = grid[yy * W + xx];
if ((t & 0x0f) == s || (t & 0xf0) == c) {
p[n + 1] = yy * W + xx;
bestn = solve(p, n + 1, bestn);
}
}
}
}
return bestn;
}
int
main(void)
{
int path[28] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2017-11.c
#include <stdio.h>
#define W 6
#define H 6
static const char grid[] = {
3, 2, 2, 2, 2, 3,
2, 3, 3, 1, 1, 1,
3, 1, 2, 2, 3, 2,
2, 3, 2, 2, 3, 1,
3, 3, 2, 1, 2, 3,
2, 1, 2, 1, 2, 1,
};
static const int moves[] = {
+0, -1, +0, +1, +1, +0, -1, +0,
+1, +1, -1, -1, +1, -1, -1, +1,
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int d = grid[p[n]];
const int *m = moves + (n % 2) * 8;
for (int i = 0; i < 4; i++) {
int xx = x + d * m[i * 2 + 0];
int yy = y + d * m[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = yy * W + xx;
bestn = solve(p, n + 1, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[20] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2017-12.c
#include <stdio.h>
#define W 6
#define H 6
enum {P, R, B, K};
enum {D, L = 0x10};
static const char grid[] = {
D|B, D|K, L|B, D|R, D|K, L|R,
L|K, D|K, D|K, D|K, D|B, D|K,
D|K, D|K, L|K, L|B, D|K, D|K,
L|B, D|K, D|K, D|K, D|K, D|K,
L|B, L|R, L|K, L|B, D|K, L|B,
D|R, L|B, L|K, L|K, L|B, L|K,
};
static const signed char moves[] = {
0, 0, 8, 4, 16, 4, 24, 8,
-1, +0, +1, +0, +0, -1, +0, +1,
-1, -1, +1, +1, -1, +1, +1, -1,
-2, -1, -2, +1, +2, -1, +2, +1,
-1, -2, -1, +2, +1, -2, +1, +2,
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int g = ((n + 1) / 2) % 2;
int x = p[n] % W;
int y = p[n] / W;
int v = grid[p[n]] & ~L;
int off = moves[v * 2 + 0];
int len = moves[v * 2 + 1];
const signed char *m = moves + off;
for (int i = 0; i < len; i++) {
int xx = x + m[i * 2 + 0];
int yy = y + m[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
int t = yy * W + xx;
if (grid[t] >> 4== g) {
p[n + 1] = t;
bestn = solve(p, n + 1, bestn);
}
}
}
}
return bestn;
}
int
main(void)
{
int path[27] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2018-01.c
#include <stdio.h>
enum {NN, SS, EE, WW, SE, NW, NE, SW};
#define W 8
#define H 8
static const char grid[] = {
SS, EE, EE, SE, EE, SW, WW, WW,
NE, NE, SS, EE, SE, SE, NE, NW,
NE, NW, WW, SW, SW, SE, WW, NW,
NE, NE, NW, SE, EE, SS, NE, NN,
SE, WW, SS, EE, WW, EE, SS, SW,
NE, WW, NN, SE, SE, NE, SS, SS,
SE, NN, NN, NW, SS, NE, WW, NW,
NN, WW, NE, NE, NW, WW, NW, -1,
};
static const int moves[] = {
+0, -1, +0, +1, +1, +0, -1, +0,
+1, +1, -1, -1, +1, -1, -1, +1,
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int v = grid[p[n]];
for (int d = 1; ; d++) {
int xx = x + d * moves[v * 2 + 0];
int yy = y + d * moves[v * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = yy * W + xx;
bestn = solve(p, n + 1, bestn);
} else {
break;
}
}
}
return bestn;
}
int
main(void)
{
int path[13] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2018-02.c
#include <stdio.h>
enum {NN, SS, EE, WW, SE, NW, NE, SW};
enum {B = 0x00, R = 0x10};
#define W 5
#define H 5
static const char grid[] = {
B|SS, B|EE, B|EE, B|SS, R|SW,
B|NN, R|EE, R|SW, R|SS, B|SS,
B|SE, B|EE, R|SW, R|EE, R|WW,
B|EE, B|SW, B|NW, R|NW, B|SW,
B|NN, B|NN, B|WW, R|WW, 0,
};
static const int moves[] = {
+0, -1, +0, +1, +1, +0, -1, +0,
+1, +1, -1, -1, +1, -1, -1, +1,
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int v = grid[p[n]] & 0x0f;
int t = ((n + 1) / 3) & 1;
for (int d = 1; ; d++) {
int xx = x + d * moves[v * 2 + 0];
int yy = y + d * moves[v * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
int i = yy * W + xx;
int c = grid[i] >> 4;
if (c == t) {
p[n + 1] = i;
bestn = solve(p, n + 1, bestn);
}
} else {
break;
}
}
}
return bestn;
}
int
main(void)
{
int path[26] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2018-03.c
#include <stdio.h>
#define C 0x80
enum {A=0x01, E=0x02, X=0x03, D=0x04, P=0x05, S=0x06};
enum {R=0x10, Y=0x20, B=0x30, V=0x40, O=0x50, G=0x60};
#define W 6
#define H 6
static const unsigned char grid[] = {
0|R|A, 0|Y|E, 0|O|X, 0|O|E, 0|O|E, 0|G|E,
C|B|A, 0|B|D, 0|V|A, 0|B|P, 0|B|E, 0|R|E,
0|O|X, 0|R|E, 0|B|X, 0|R|X, 0|G|E, 0|O|P,
0|Y|P, 0|B|X, C|O|A, 0|Y|A, C|O|A, 0|O|E,
0|G|E, 0|R|E, 0|O|E, 0|V|A, 0|G|X, 0|V|A,
0|V|A, 0|B|A, 0|G|A, C|B|A, 0|R|E, 0|O|S,
};
static const int moves[] = {
+0, -1, +0, +1, +1, +0, -1, +0,
+1, +1, -1, -1, +1, -1, -1, +1,
};
static int
solve(int *p, int n, int m, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int s = grid[p[n]] & 0x07;
int c = grid[p[n]] & 0x70;
for (int v = 0; v < 8; v++) {
for (int d = 1; ; d++) {
int tx = x + d * moves[v * 2 + 0];
int ty = y + d * moves[v * 2 + 1];
if (tx >= 0 && tx < W && ty >= 0 && ty < H) {
int i = ty * W + tx;
int ts = grid[i] & 0x07;
int tc = grid[i] & 0x70;
int to = grid[i] & 0x80;
if ((!m && s == ts) || (m && c == tc)) {
p[n + 1] = i;
bestn = solve(p, n + 1, to ? m : !m, bestn);
}
} else {
break;
}
}
}
}
return bestn;
}
int
main(void)
{
int path[30] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2018-04.c
#include <stdio.h>
#define W 5
#define H 5
static const unsigned long grid = 0x848824;
static const int moves[] = {+0, -1, +0, +1, +1, +0, -1, +0};
static int
solve(int *p, int n, int d, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (d > 0 && n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
for (int m = 0; m < 4; m++) {
int xx = x + d * moves[m * 2 + 0];
int yy = y + d * moves[m * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
int i = yy * W + xx;
int f = (grid >> i) & 1UL;
int dd;
p[n + 1] = i;
if (i == 0)
dd = 1;
else
dd = f ? d + 1: d - 1;
bestn = solve(p, n + 1, dd, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[20] = {0};
solve(path, 0, 1, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2018-05.c
#include <stdio.h>
enum {NN, NE, EE, SE, SS, SW, WW, NW};
#define W 6
#define H 6
static const char grid[] = {
EE, SS, WW, SW, NW, WW,
SE, NE, NE, EE, WW, NE,
WW, NN, SS, NE, NN, WW,
SE, SW, NN, NN, NW, EE,
EE, SW, WW, SE, NW, EE,
NN, SS, NN, WW, NE, 0
};
static const int moves[] = {
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int a = grid[p[n]];
int r = n % 2 ? -1 : 1;
for (int d = 1; ; d++) {
int xx = x + r * d * moves[a * 2 + 0];
int yy = y + r * d * moves[a * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = yy * W + xx;
bestn = solve(p, n + 1, bestn);
} else {
break;
}
}
}
return bestn;
}
int
main(void)
{
int path[31] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2018-06.c
#include <stdio.h>
enum {EE = 0, NL = 1, SS = 2, NR = 3};
#define W 6
#define H 6
static const char grid[] = {
EE, NL, NR, SS, SS, NR,
NL, NL, NR, NR, SS, NR,
NL, NL, NL, NR, NR, NR,
SS, NL, NL, NL, NR, NR,
NL, SS, SS, NL, NL, NL,
NR, NL, SS, NL, NL, EE
};
static const int moves[] = {
+0, -1, +1, +0, +0, +1, -1, +0,
};
static int
solve(int *p, int n, int v, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
for (int d = 1; ; d++) {
int xx = x + d * moves[v * 2 + 0];
int yy = y + d * moves[v * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
int a = grid[yy * W + xx];
if (a != SS) {
p[n + 1] = yy * W + xx;
bestn = solve(p, n + 1, (v + a) % 4, bestn);
}
} else {
break;
}
}
}
return bestn;
}
int
main(void)
{
int path[25] = {0};
solve(path, 0, 1, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2018-07.c
#include <stdio.h>
enum {B=0x01, R=0x02, S=0x10, D=0x20, X=0x30, T=0x40, C=0x80};
#define BEG 2
#define END 22
#define W 5
#define H 5
static const unsigned char grid[] = {
0|0|0, 0|0|0, 0|B|S, 0|0|0, 0|0|0,
0|0|0, 0|R|T, C|B|X, C|R|D, 0|0|0,
0|B|X, 0|B|T, 0|R|D, C|B|D, C|B|S,
0|0|0, C|B|S, 0|R|X, 0|R|S, 0|0|0,
0|0|0, 0|0|0, 0|0|D, 0|0|0, 0|0|0
};
static const int moves[] = {
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1
};
static int
solve(int *p, int n, int d, int bestn)
{
if (p[n] == END) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int o = d % 2;
int a = grid[p[n]];
int c = a & 0x07;
int s = a & 0x70;
if (a & C)
o = !o;
for (int i = 0; i < 4; i++) {
int j = i * 2 + o;
if (j != (d + 4) % 8) { // no u-turns
for (int v = 1; ; v++) {
int xx = x + v * moves[j * 2 + 0];
int yy = y + v * moves[j * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
int ti = yy * W + xx;
int ta = grid[ti];
int tc = ta & 0x07;
int ts = ta & 0x70;
if (tc == c || ts == s) {
p[n + 1] = ti;
bestn = solve(p, n + 1, j, bestn);
}
} else {
break;
}
}
}
}
}
return bestn;
}
int
main(void)
{
int path[14] = {BEG};
solve(path, 0, 3, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2018-08.c
#include <stdio.h>
#include <stdlib.h>
#define W 6
#define H 5
static const signed char grid[] = {
+9, +1, -2, -2, -1, +1,
-1, +1, +1, +1, +1, +3,
-2, -1, +0, +1, +3, -1,
+1, -1, -3, +1, -1, -3,
-2, -3, +2, +1, +3, +0
};
static const signed char moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1,
};
static int
solve(int *p, int n, int d, int bestn)
{
if (p[n] == H * W - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int j = d + grid[p[n]];
if (j > 0) {
for (int i = 0; i < 4; i++) {
int xx = x + j * moves[i * 2 + 0];
int yy = y + j * moves[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = xx + yy * W;
bestn = solve(p, n + 1, j, bestn);
}
}
}
}
return bestn;
}
int
main(void)
{
int path[34] = {0};
solve(path, 0, -6, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2018-09.c
#include <stdio.h>
#define W 6
#define H 6
enum {P, R, B, K, X};
static const char grid[] = {
R, P, P, B, B, R,
B, R, B, R, B, R,
R, B, P, P, B, B,
P, P, B, R, B, P,
B, B, P, B, K, P,
B, R, B, R, P, X,
};
static const signed char moves[] = {
0, 0, 8, 4, 16, 4, 24, 8,
-1, +0, +1, +0, +0, -1, +0, +1,
-1, -1, +1, +1, -1, +1, +1, -1,
-2, -1, -2, +1, +2, -1, +2, +1,
-1, -2, -1, +2, +1, -2, +1, +2,
};
static int
solve(int *p, int n, int last, int bestn)
{
if (grid[p[n]] == X) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int c = grid[p[n]] ? grid[p[n]] : last;
int off = moves[c * 2 + 0];
int len = moves[c * 2 + 1];
const signed char *m = moves + off;
for (int i = 0; i < len; i++) {
int xx = x + m[i * 2 + 0];
int yy = y + m[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = xx + yy * W;
int loop = 0;
if (grid[p[n + 1]])
for (int j = 0; !loop && j < n; j++)
if (p[j] == p[n + 1])
loop = 1;
if (!loop)
bestn = solve(p, n + 1, c, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[26] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2018-10.c
#include <stdio.h>
#define C 0x80
enum {NN, NE, EE, SE, SS, SW, WW, NW};
enum {B = 0x10, R = 0x20, G = 0x40};
#define W 6
#define H 6
static const unsigned char grid[] = {
0|G|EE, 0|G|NW, 0|R|EE, 0|B|SE, 0|B|NN, 0|G|SW,
0|G|EE, 0|R|NE, 0|R|SS, 0|B|NN, 0|R|EE, 0|R|EE,
0|G|WW, C|G|EE, 0|B|SW, 0|R|NE, 0|B|NE, 0|B|SW,
0|R|WW, 0|R|EE, 0|B|NE, 0|R|SE, 0|G|SE, C|G|EE,
0|G|SW, 0|B|SW, 0|G|SS, 0|G|NN, 0|G|SE, 0|R|EE,
0|B|NN, 0|G|SS, 0|G|NN, 0|R|EE, 0|R|SE, 0
};
static const int moves[] = {
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1
};
static int
solve(int *p, int n, int r, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int v = grid[p[n]] & 0x0f;
int c = grid[p[n]] & 0x70;
if (r)
v = (v + 4) % 8;
for (int d = 1; ; d++) {
int xx = x + d * moves[v * 2 + 0];
int yy = y + d * moves[v * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
int i = yy * W + xx;
int cc = grid[i] & 0x70;
if (cc != c) {
int rr = r;
if (grid[i] & 0x80)
rr = !rr;
p[n + 1] = i;
bestn = solve(p, n + 1, rr, bestn);
}
} else {
break;
}
}
}
return bestn;
}
int
main(void)
{
int path[32] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2018-11.c
#include <stdio.h>
enum {A=0x01, E=0x02, X=0x03, C=0x04, P=0x05, S=0x06};
enum {R=0x10, Y=0x20, B=0x30, V=0x40, O=0x50, G=0x60};
#define W 6
#define H 6
static const unsigned char grid[] = {
R|C, B|E, O|S, O|X, V|C, G|E,
V|C, B|P, Y|X, G|X, Y|S, V|P,
O|A, V|A, V|S, G|E, V|C, B|E,
O|E, O|P, R|X, R|S, V|A, B|A,
Y|C, O|X, B|C, Y|S, B|A, G|A,
B|E, R|X, B|A, V|A, R|S, V|C
};
static const int moves[] = {
+0, -1, +0, +1, +1, +0, -1, +0
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int s = grid[p[n]] & 0x07;
int c = grid[p[n]] & 0x70;
for (int v = 0; v < 4; v++) {
for (int d = 1; ; d++) {
int tx = x + d * moves[v * 2 + 0];
int ty = y + d * moves[v * 2 + 1];
if (tx >= 0 && tx < W && ty >= 0 && ty < H) {
int i = ty * W + tx;
int ts = grid[i] & 0x07;
int tc = grid[i] & 0x70;
if ((!(n % 2) && s == ts) || ((n % 2) && c == tc)) {
p[n + 1] = i;
bestn = solve(p, n + 1, bestn);
}
} else {
break;
}
}
}
}
return bestn;
}
int
main(void)
{
int path[17] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2018-12.c
#include <stdio.h>
#include <stdlib.h>
#define W 5
#define H 5
static const signed char grid[] = {
+0, -24, +36, +1, +9,
+27, -5, -11, -11, +32,
+1, +9, -4, -21, -20,
-9, -1, -20, +9, +16,
-7, +24, -27, +12, +15
};
static const int moves[] = {
+0, -1, +0, +1, +1, +0, -1, +0
};
static int
isqrt(int v)
{
if (v == 0) {
return 0;
} else if (v == 1) {
return 1;
} else if (v < 0) {
return -1;
} else {
int g = v / 2;
while (g * g != v) {
int n = (g + v / g) / 2;
if (abs(n - g) <= 1)
return n * n == v ? n : -1;
g = n;
}
return g;
}
}
static int
solve(int *p, int n, int bestn, int sum)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", grid[p[i]], " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
for (int v = 0; v < 4; v++) {
for (int d = 1; ; d++) {
int tx = x + d * moves[v * 2 + 0];
int ty = y + d * moves[v * 2 + 1];
if (tx >= 0 && tx < W && ty >= 0 && ty < H) {
int i = ty * W + tx;
int s = grid[i];
if (isqrt(sum + s) != -1) {
p[n + 1] = i;
bestn = solve(p, n + 1, bestn, sum + s);
}
} else {
break;
}
}
}
}
return bestn;
}
int
main(void)
{
int path[13] = {0};
solve(path, 0, sizeof(path) / sizeof(*path), 0);
}
Raw
mazelog-2019-01.c
#include <stdio.h>
enum {NN, NE, EE, SE, SS, SW, WW, NW, RR};
#define W 6
#define H 6
static const char grid[] = {
EE, SW, SE, SE, SS, SW,
EE, NE, RR, SE, EE, WW,
SE, NE, EE, SE, RR, SW,
EE, RR, SE, NE, SW, NW,
SE, SS, NN, RR, NE, SW,
NE, WW, WW, EE, NN, 0
};
static const int moves[] = {
+0, -1,
+1, -1,
+1, +0,
+1, +1,
+0, +1,
-1, +1,
-1, +0,
-1, -1
};
static int
solve(int *p, int n, int bestn, int dir)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int v = grid[p[n]];
if (v == RR) v = (dir + 4) % 8;
for (int d = 1; ; d++) {
int xx = x + d * moves[v * 2 + 0];
int yy = y + d * moves[v * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = yy * W + xx;
bestn = solve(p, n + 1, bestn, v);
} else {
break;
}
}
}
return bestn;
}
int
main(void)
{
int path[15] = {0};
solve(path, 0, sizeof(path) / sizeof(*path), 0);
}
Raw
mazelog-2019-02.c
#include <stdio.h>
#include <stdlib.h>
#define W 6
#define H 6
static const char grid[] = {
4, 4, 2, 3, 1, 0,
4, 3, 3, 3, 3, 1,
3, 4, 0, 2, 5, 1,
3, 3, 4, 0, 3, 3,
4, 2, 2, 4, 3, 1,
0, 3, 4, 4, 2, 0
};
static const signed char moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1,
};
static int
solve(int *p, int n, int j, int bestn)
{
if (p[n] == H * W - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int d = grid[p[n]] ? grid[p[n]] : j;
for (int i = 0; i < 4; i++) {
int xx = x + d * moves[i * 2 + 0];
int yy = y + d * moves[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = xx + yy * W;
bestn = solve(p, n + 1, d, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[22] = {0};
solve(path, 0, grid[0], sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2019-03.c
#include <stdio.h>
enum {NN, SS, EE, WW, SE, NW, NE, SW};
enum {B = 0x00, R = 0x10};
#define W 6
#define H 6
static const char grid[] = {
B|EE, R|EE, B|SE, R|SE, R|SS, B|SW,
R|SE, R|EE, B|WW, R|SW, B|NN, R|SW,
R|EE, R|SE, R|NE, B|SS, B|NN, B|WW,
R|NN, R|NE, B|WW, R|EE, R|EE, R|NW,
R|EE, R|SW, R|SE, B|SS, R|NW, B|NN,
R|EE, B|NN, B|EE, B|NE, B|NE, 0
};
static const int moves[] = {
+0, -1, +0, +1, +1, +0, -1, +0,
+1, +1, -1, -1, +1, -1, -1, +1
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int v = grid[p[n]] & 0x0f;
int t = n % 3 < 2;
for (int d = 1; ; d++) {
int xx = x + d * moves[v * 2 + 0];
int yy = y + d * moves[v * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
int i = yy * W + xx;
int c = grid[i] >> 4;
if (i == W * H - 1 || c == t) {
/* No looping */
int valid = 1;
for (int j = n - 2; valid && j >= 0; j -= 3)
if (p[j] == i)
valid = 0;
if (valid) {
p[n + 1] = i;
bestn = solve(p, n + 1, bestn);
}
}
} else {
break;
}
}
}
return bestn;
}
int
main(void)
{
int path[28] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2019-04.c
#include <stdio.h>
#include <stdlib.h>
#define W 8
#define H 8
static const char grid[] = {
2, 3, 3, 2, 3, 2, 3, 2,
3, 2, 2, 3, 2, 4, 2, 2,
3, 2, 3, 2, 3, 2, 3, 2,
2, 3, 3, 3, 2, 3, 2, 3,
3, 2, 3, 3, 3, 2, 3, 2,
2, 1, 2, 3, 2, 4, 2, 2,
1, 3, 3, 2, 3, 3, 2, 2,
2, 2, 2, 3, 2, 3, 2, 0
};
static const signed char moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1, -1, -1, -1, +1, +1, -1, +1, +1
};
static int
solve(int *p, int n, char *seen, int bestn)
{
if (p[n] == H * W - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int j = grid[p[n]];
seen[p[n]] = 1;
for (int i = 0; i < 8; i++) {
int xx = x + j * moves[i * 2 + 0];
int yy = y + j * moves[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
int t = xx + yy * W;
if (!seen[t]) {
p[n + 1] = t;
bestn = solve(p, n + 1, seen, bestn);
}
}
}
seen[p[n]] = 0;
}
return bestn;
}
int
main(void)
{
char seen[W * H] = {0};
int path[8] = {0};
solve(path, 0, seen, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2019-05.c
#include <stdio.h>
#include <stdlib.h>
enum {A, B, C, X};
#define W 7
#define H 6
static const char grid[] = {
A, B, B, C, B, A, B,
C, X, A, C, B, X, C,
A, A, B, A, C, B, A,
B, B, C, A, B, A, A,
C, X, B, C, A, X, C,
A, A, B, C, A, B, A
};
static const signed char moves[] = {
+1, +0, +0, +1, -1, +0, +0, -1
};
static int
solve(int *p, int n, int last, int bestn)
{
if (p[n] == H * W - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int b = (last + 2) % 4;
int v = (n + 1) % 3;
for (int i = 0; i < 4; i++) {
if (i != b) {
int xx = x + moves[i * 2 + 0];
int yy = y + moves[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
int t = xx + yy * W;
int d = grid[t];
if (d == X || d == v) {
p[n + 1] = t;
bestn = solve(p, n + 1, i, bestn);
}
}
}
}
}
return bestn;
}
int
main(void)
{
int path[34] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2019-06.c
#include <stdio.h>
#include <stdlib.h>
enum {A, B, C, X};
#define W 6
#define H 6
static const char grid[] = {
A, X, A, C, B, C,
C, X, X, X, X, B,
X, B, B, B, C, X,
X, B, B, A, B, C,
C, X, B, X, X, X,
A, X, X, C, A, C,
};
static const signed char moves[] = {
+1, +0, +0, +1, -1, +0, +0, -1
};
static int
solve(int *p, int n, int last, int bestn)
{
if (p[n] == H * W - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int b = (last + 2) % 4;
int v = (n + 1) % 3;
for (int i = 0; i < 4; i++) {
if (i != b) {
int xx = x + moves[i * 2 + 0];
int yy = y + moves[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
int t = xx + yy * W;
int d = grid[t];
if (d == X || d == v) {
p[n + 1] = t;
bestn = solve(p, n + 1, i, bestn);
}
}
}
}
}
return bestn;
}
int
main(void)
{
int path[45] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2019-07.c
#include <stdio.h>
#define W 4
#define H 4
enum {P, R, B, K, X};
static const char grid[] = {
R, B, R, P,
B, P, B, K,
K, P, K, P,
R, R, B, X,
};
static const signed char moves[] = {
0, 0, 8, 4, 16, 4, 24, 8,
-1, +0, +1, +0, +0, -1, +0, +1,
-1, -1, +1, +1, -1, +1, +1, -1,
-2, -1, -2, +1, +2, -1, +2, +1,
-1, -2, -1, +2, +1, -2, +1, +2,
};
static int
solve(int *p, int n, int last, int bestn)
{
if (grid[p[n]] == X) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int c = grid[p[n]] ? grid[p[n]] : last;
int off = moves[c * 2 + 0];
int len = moves[c * 2 + 1];
const signed char *m = moves + off;
for (int i = 0; i < len; i++) {
int xx = x + m[i * 2 + 0];
int yy = y + m[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = xx + yy * W;
bestn = solve(p, n + 1, c, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[15] = {0};
solve(path, 0, grid[0], sizeof(path) / sizeof(*path));
}
Raw
mazelog-2019-08.c
#include <stdio.h>
#define W 5
#define H 5
enum {R = 0x10, G = 0x20, B = 0x30, V = 0x40, Y = 0x50};
enum {C = 0x01, D = 0x02, X = 0x03, S = 0x04, E = 0x05};
static const char grid[] = {
R|C, B|D, B|E, G|S, G|C,
G|S, 0|0, B|E, V|C, R|X,
V|E, R|X, G|C, B|E, B|X,
Y|C, B|E, V|D, R|S, G|C,
B|E, 0|0, 0|0, R|X, Y|S
};
static const int moves[] = {+0, -1, +0, +1, +1, +0, -1, +0};
static int
solve(int *p, int n, int prev, long seen, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int v = grid[p[n]] ? grid[p[n]] : prev;
int s = v & 0x0f;
int c = v & 0xf0;
for (int i = 0; i < 4; i++) {
for (int d = 1; ; d++) {
int xx = x + d * moves[i * 2 + 0];
int yy = y + d * moves[i * 2 + 1];
int j = yy * W + xx;
if (xx < 0 || xx >= W || yy < 0 || yy >= H)
break;
long bit = 1L << j;
if (grid[j] && (bit & seen))
continue;
int t = grid[j];
if (!t || (t & 0x0f) == s || (t & 0xf0) == c) {
p[n + 1] = yy * W + xx;
bestn = solve(p, n + 1, v, seen | bit, bestn);
}
}
}
}
return bestn;
}
int
main(void)
{
int path[31] = {0};
solve(path, 0, 0, 1L << 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2019-09.c
#include <stdio.h>
enum {S = 0x01, C = 0x02, D = 0x03, X = 0x04, P = 0x05};
enum {V = 0x10, O = 0x20, Y = 0x30, R = 0x40, B = 0x50};
#define W 5
#define H 5
static const char grid[] = {
V|S, O|D, Y|X, R|S, B|D,
V|D, B|X, O|D, Y|X, O|D,
B|X, O|D, R|C, O|P, R|D,
R|S, Y|D, O|C, O|P, O|D,
R|D, O|D, O|S, O|D, Y|X,
};
static const int moves[] = {
+0, -1, +0, +1, +1, +0, -1, +0,
+1, +1, -1, -1, +1, -1, -1, +1
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int s = grid[p[n]] & 0x0f;
int c = grid[p[n]] & 0xf0;
int t = n % 6 < 3 ? 0 : 8;
for (int i = 0; i < 4; i++) {
for (int d = 1; ; d++) {
int xx = x + d * moves[t + i * 2 + 0];
int yy = y + d * moves[t + i * 2 + 1];
if (xx < 0 || xx >= W || yy < 0 || yy >= H) {
break;
}
int i = yy * W + xx;
int ts = grid[i] & 0x0f;
int tc = grid[i] & 0xf0;
if (s == ts || c == tc) {
p[n + 1] = i;
bestn = solve(p, n + 1, bestn);
}
}
}
}
return bestn;
}
int
main(void)
{
int path[11] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2019-10.c
#include <stdio.h>
enum {NN, NE, EE, SE, SS, SW, WW, NW};
#define W 7
#define H 5
static const char grid[] = {
SE, SE, EE, NN, EE, SS, NE,
EE, SW, WW, WW, WW, WW, WW,
SE, SW, SS, WW, SS, SS, EE,
SE, EE, SW, NN, NE, NN, NN,
WW, NN, SE, NW, NE, NW, 0
};
static const int moves[] = {
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1
};
static int
solve(int *p, int n, int bestn)
{
static char mark[W * H];
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int b = 1 << (n % 6);
if (mark[p[n]] & b)
return bestn;
mark[p[n]] ^= b;
int x = p[n] % W;
int y = p[n] / W;
int a = grid[p[n]];
int r = n / 3 % 2 ? -1 : 1;
for (int d = 1; ; d++) {
int xx = x + r * d * moves[a * 2 + 0];
int yy = y + r * d * moves[a * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = yy * W + xx;
bestn = solve(p, n + 1, bestn);
} else {
break;
}
}
mark[p[n]] ^= b;
}
return bestn;
}
int
main(void)
{
int path[23] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2019-11.c
#include <stdio.h>
#define W 5
#define H 5
enum {R = 0x10, G = 0x20, B = 0x30, V = 0x40, Y = 0x50};
enum {C = 0x01, D = 0x02, X = 0x03, P = 0x04, A = 0x05, S = 0x06};
static const char grid[] = {
B|D, Y|A, V|C, B|C, R|P,
R|A, G|P, R|A, R|X, V|X,
V|P, R|A, V|P, R|A, B|A,
G|A, B|A, R|A, G|A, B|A,
V|S, R|A, B|S, B|P, Y|X,
};
static const int moves[] = {
+0, -1, +0, +1, +1, +0, -1, +0,
+1, +1, -1, -1, +1, -1, -1, +1,
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int v = grid[p[n]];
int s = v & 0x0f;
int c = v & 0xf0;
const int *m = moves + (n / 3 % 2) * 8;
for (int i = 0; i < 4; i++) {
for (int d = 1; ; d++) {
int xx = x + d * m[i * 2 + 0];
int yy = y + d * m[i * 2 + 1];
if (xx < 0 || xx >= W || yy < 0 || yy >= H)
break;
int t = grid[yy * W + xx];
if ((t & 0x0f) == s || (t & 0xf0) == c) {
p[n + 1] = yy * W + xx;
bestn = solve(p, n + 1, bestn);
}
}
}
}
return bestn;
}
int
main(void)
{
int path[15] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2019-12.c
#include <stdio.h>
#define C 0x80
enum {NN, NE, EE, SE, SS, SW, WW, NW};
enum {B=0x10, R=0x20, P=0x40};
#define W 6
#define H 6
static const unsigned char grid[] = {
0|B|EE, 0|R|SE, 0|R|NE, 0|B|EE, 0|R|EE, 0|P|SW,
0|R|SE, 0|B|WW, 0|B|SS, 0|P|NN, 0|B|SW, 0|B|NW,
0|P|NN, C|B|EE, 0|P|SW, 0|R|NW, 0|P|SW, 0|B|NN,
0|R|WW, 0|R|NW, 0|B|SS, 0|B|SE, 0|R|SS, 0|B|NW,
0|B|SE, 0|R|NE, C|R|EE, 0|P|NE, C|R|NE, 0|B|NE,
0|B|NE, 0|R|WW, 0|R|NE, 0|P|SW, 0|R|EE, 0
};
static const int moves[] = {
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1
};
static int
solve(int *p, int n, int r, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int v = grid[p[n]] & 0x0f;
int c = grid[p[n]] & 0x70;
if (r) v = (v + 4) % 8;
for (int d = 1; ; d++) {
int xx = x + d * moves[v * 2 + 0];
int yy = y + d * moves[v * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
static char seen[2][W*H];
int i = yy * W + xx;
int cc = grid[i] & 0x70;
if (!seen[r][i] && cc != c) {
int rr = grid[i] & 0x80 ? !r : r;
p[n + 1] = i;
seen[r][i] = 1;
bestn = solve(p, n + 1, rr, bestn);
seen[r][i] = 0;
}
} else {
break;
}
}
}
return bestn;
}
int
main(void)
{
int path[23] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2020-01.c
#include <stdio.h>
#define W 6
#define H 6
enum {P, R, B, K};
enum {D, L = 0x10};
static const char grid[] = {
D|B, L|K, L|K, L|B, D|K, D|B,
L|K, D|K, L|B, L|B, D|K, D|R,
D|K, L|K, L|K, L|K, D|K, D|K,
L|B, L|K, L|K, L|K, D|K, L|K,
L|K, D|B, D|B, L|B, D|K, D|K,
L|B, L|B, L|K, D|K, L|K, L|K
};
static const signed char moves[] = {
0, 0, 8, 4, 16, 4, 24, 8,
-1, +0, +1, +0, +0, -1, +0, +1,
-1, -1, +1, +1, -1, +1, +1, -1,
-2, -1, -2, +1, +2, -1, +2, +1,
-1, -2, -1, +2, +1, -2, +1, +2,
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int g = (n+1) / 2 % 2;
int x = p[n] % W;
int y = p[n] / W;
int v = grid[p[n]] & 0x0f;
int off = moves[v * 2 + 0];
int len = moves[v * 2 + 1];
const signed char *m = moves + off;
for (int i = 0; i < len; i++) {
int xx = x + m[i * 2 + 0];
int yy = y + m[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
int t = yy * W + xx;
if (grid[t] >> 4 == g) {
p[n + 1] = t;
bestn = solve(p, n + 1, bestn);
}
}
}
}
return bestn;
}
int
main(void)
{
int path[27] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2020-02.c
#include <stdio.h>
#define H 5
#define W 5
static const signed char grid[] = {
+2, -1, -1, -2, +1,
-1, +9, +1, +9, -1,
-2, +0, +1, +1, -1,
+0, +9, +1, +9, +1,
-1, -1, -1, -1, +0
};
static const signed char moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1
};
static int
solve(int *p, int n, int v, int bestn)
{
if (p[n - 1] == W * H - 1) {
for (int i = 0; i < n; i++)
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n');
bestn = n;
} else if (n < bestn - 1) {
int x = p[n - 1] % W;
int y = p[n - 1] / W;
for (int i = 0; i < 4; i++) {
if (x % 2 == 1 && i > 1) continue;
if (y % 2 == 1 && i < 2) continue;
int tx = x + moves[i * 2 + 0] * v;
int ty = y + moves[i * 2 + 1] * v;
if (tx >= 0 && tx < W && ty >= 0 && ty < H) {
int t = ty * W + tx;
if (grid[t] + v >= 0) {
p[n] = t;
bestn = solve(p, n + 1, grid[t] + v, bestn);
}
}
}
}
return bestn;
}
int
main(void)
{
int path[26] = {0};
solve(path, 1, grid[0], sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2020-03.c
#include <stdio.h>
#include <stdlib.h>
enum {A, B, C, X};
#define W 6
#define H 5
static const char grid[] = {
A, B, X, X, A, X,
C, C, C, X, X, A,
X, X, C, B, C, X,
X, A, C, X, B, A,
X, X, B, X, B, X
};
static const signed char moves[] = {
+1, +0, +0, +1, -1, +0, +0, -1
};
static int
solve(int *p, int n, int last, int bestn)
{
if (p[n] == H * W - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int b = (last + 2) % 4;
int v = (n + 1) % 3;
for (int i = 0; i < 4; i++) {
if (i != b) {
int xx = x + moves[i * 2 + 0];
int yy = y + moves[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
int t = xx + yy * W;
int d = grid[t];
if (d == X || d == v) {
p[n + 1] = t;
bestn = solve(p, n + 1, i, bestn);
}
}
}
}
}
return bestn;
}
int
main(void)
{
int path[24] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2020-04.c
#include <stdio.h>
#define W 7
#define H 5
enum {NN, NE, EE, SE, SS, SW, WW, NW};
static const char grid[] = {
SE, SE, EE, NN, EE, SE, SS,
SE, EE, EE, WW, WW, WW, EE,
SS, WW, WW, NN, WW, WW, EE,
NN, WW, NE, NN, WW, WW, EE,
SS, NN, WW, NN, SS, WW, 0
};
static const int moves[] = {
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int v = grid[p[n]];
if (n % 6 > 2) v = (v + 4) % 8;
for (int d = 1; ; d++) {
int xx = x + d * moves[v * 2 + 0];
int yy = y + d * moves[v * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = yy * W + xx;
bestn = solve(p, n + 1, bestn);
} else {
break;
}
}
}
return bestn;
}
int
main(void)
{
int path[23] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2020-05.c
#include <stdio.h>
#define W 7
#define H 7
enum {NN, NE, EE, SE, SS, SW, WW, NW, XX};
static const char grid[] = {
XX, SW, NW, NW, SE, NE, XX,
SE, SE, SW, SW, NE, SS, NW,
NE, NW, SW, SE, NE, NW, NE,
SW, NE, NE, NN, SW, SW, WW,
NE, NE, SW, NE, NE, NE, SW,
WW, SS, NW, SW, SE, NW, NE,
XX, NW, SE, NE, SE, SW, XX
};
static const int moves[] = {
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1
};
static int
solve(int *p, int n, int bestn)
{
if (grid[p[n]] == XX) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int v = grid[p[n]];
if (n % 2) v = (v + 4) % 8;
for (int d = 1; ; d++) {
int xx = x + d * moves[v * 2 + 0];
int yy = y + d * moves[v * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = yy * W + xx;
bestn = solve(p, n + 1, bestn);
} else {
break;
}
}
}
return bestn;
}
int
main(void)
{
int path[12] = {24};
solve(path, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2020-06.c
#include <stdio.h>
#include <stdlib.h>
#define W 5
#define H 5
static const char grid[] = {
0, 0, 0, 0, 0,
0, 0, 2, 0, 1,
0, 1, 0, 0, 2,
1, 0, 0, 1, 1,
1, 0, 2, 2, 0
};
static const signed char moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1,
};
static int
solve(int *p, int n, int d, int bestn)
{
if (p[n] == H * W - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
d += grid[p[n]];
for (int i = 0; i < 4; i++) {
int xx = x + d * moves[i * 2 + 0];
int yy = y + d * moves[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = xx + yy * W;
bestn = solve(p, n + 1, d, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[16] = {0};
solve(path, 0, 1, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2020-07.c
#include <stdio.h>
#define C 0x80
enum {N=0x01, Q=0x02, X=0x03, D=0x04, T=0x05, S=0x06};
enum {R=0x10, Y=0x20, B=0x30, V=0x40, O=0x50, G=0x60};
#define W 6
#define H 6
static const unsigned char grid[] = {
0|N|V, C|N|Y, 0|X|Y, C|T|Y, C|T|B, C|N|B,
C|Q|V, 0|S|Y, C|S|G, 0|X|V, C|D|B, 0|X|R,
0|T|Y, 0|T|Y, C|N|V, C|T|V, 0|T|R, 0|D|V,
C|D|R, C|Q|V, C|D|G, 0|D|R, C|D|O, C|D|B,
C|Q|R, 0|S|B, C|Q|R, 0|X|Y, C|T|V, C|X|R,
C|Q|R, 0|S|R, C|D|B, 0|Q|Y, C|S|Y, 0|X|O
};
static const int moves[] = {
+0, -1, +0, +1, +1, +0, -1, +0,
+1, +1, -1, -1, +1, -1, -1, +1,
};
static int
solve(int *p, int n, int m, int bestn)
{
static char seen[W*H][W*H];
if (p[n] == W * H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int s = grid[p[n]] & 0x07;
int c = grid[p[n]] & 0x70;
const int *o = moves + 8*m;
for (int v = 0; v < 4; v++) {
for (int d = 1; ; d++) {
int tx = x + d*o[v*2 + 0];
int ty = y + d*o[v*2 + 1];
if (tx >= 0 && tx < W && ty >= 0 && ty < H) {
int i = ty*W + tx;
int ts = grid[i] & 0x07;
int tc = grid[i] & 0x70;
int to = grid[i] & 0x80;
int nm = to ? !m : m;
if (!seen[p[n]][i] && ((s == ts) || (c == tc))) {
p[n+1] = i;
seen[p[n]][i] = 1;
bestn = solve(p, n + 1, nm, bestn);
seen[p[n]][i] = 0;
}
} else {
break;
}
}
}
}
return bestn;
}
int
main(void)
{
int path[33] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2020-08.c
#include <stdio.h>
enum {G=0x10, B=0x20, R=0x30, V=0x40};
enum {D=0x01, S=0x02, C=0x03, P=0x04, X=0x05};
#define H 5
#define W 5
static const signed char grid[] = {
G|D, G|C, G|C, B|C, B|D,
B|S, 0, B|C, 0, R|S,
B|D, R|D, R|C, R|X, R|C,
V|D, 0, V|C, 0, B|D,
B|X, B|X, V|C, B|C, R|P,
};
static const signed char moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1
};
static int
solve(int *p, int n, int bestn)
{
if (p[n - 1] == W * H - 1) {
for (int i = 0; i < n; i++)
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n');
bestn = n;
} else if (n < bestn - 1) {
int x = p[n - 1] % W;
int y = p[n - 1] / W;
int m = n % 2 ? 0x0f : 0xf0;
for (int i = 0; i < 4; i++) {
if (x % 2 == 1 && i > 1) continue;
if (y % 2 == 1 && i < 2) continue;
for (int v = 1; ; v++) {
int tx = x + v * moves[i * 2 + 0];
int ty = y + v * moves[i * 2 + 1];
if (tx >= 0 && tx < W && ty >= 0 && ty < H) {
int t = ty * W + tx;
if ((grid[t] & m) == (grid[p[n-1]] & m)) {
p[n] = t;
bestn = solve(p, n + 1, bestn);
}
} else {
break;
}
}
}
}
return bestn;
}
int
main(void)
{
int path[16] = {0};
solve(path, 1, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2020-09.c
#include <stdio.h>
#include <stdlib.h>
enum {A, B, C, X};
#define W 5
#define H 5
static const char grid[] = {
A, X, X, C, X,
X, B, X, X, C,
C, B, A, B, X,
B, X, C, C, C,
X, X, X, B, X
};
static const signed char moves[] = {
+1, +0, +0, +1, -1, +0, +0, -1
};
static int
solve(int *p, int n, int last, int bestn)
{
if (p[n] == H * W - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int b = (last + 2) % 4;
int v = (n + 1) % 3;
for (int i = 0; i < 4; i++) {
if (i != b) {
int xx = x + moves[i * 2 + 0];
int yy = y + moves[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
int t = xx + yy * W;
int d = grid[t];
if (d == X || d == v) {
p[n + 1] = t;
bestn = solve(p, n + 1, i, bestn);
}
}
}
}
}
return bestn;
}
int
main(void)
{
int path[33] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2020-10.c
#include <stdio.h>
#define W 6
#define H 6
enum {P, R, B, K, X};
static const char grid[] = {
K, P, R, P, R, B,
P, R, B, R, B, B,
B, B, R, R, P, B,
P, R, B, P, B, R,
P, B, R, B, K, P,
P, K, P, B, B, X,
};
static const signed char moves[] = {
0, 0, 8, 4, 16, 4, 24, 8,
-1, +0, +1, +0, +0, -1, +0, +1,
-1, -1, +1, +1, -1, +1, +1, -1,
-2, -1, -2, +1, +2, -1, +2, +1,
-1, -2, -1, +2, +1, -2, +1, +2,
};
static int
solve(int *p, int n, int last, int bestn)
{
if (grid[p[n]] == X) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int c = grid[p[n]] ? grid[p[n]] : last;
int off = moves[c * 2 + 0];
int len = moves[c * 2 + 1];
const signed char *m = moves + off;
for (int i = 0; i < len; i++) {
int xx = x + m[i * 2 + 0];
int yy = y + m[i * 2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n + 1] = xx + yy * W;
int loop = 0;
if (grid[p[n + 1]])
for (int j = 0; !loop && j < n; j++)
if (p[j] == p[n + 1])
loop = 1;
if (!loop)
bestn = solve(p, n + 1, c, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[30] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2020-11.c
#include <stdio.h>
enum {D, S, E, C};
#define H 5
#define W 5
static const signed char grid[] = {
D, D, C, D, D,
C, S, C, S, D,
D, S, C, E, D,
E, S, E, E, E,
D, S, D, D, D,
};
static const signed char moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1
};
static int
solve(int *p, int n, int bestn)
{
if (p[n - 1] == W * H - 1) {
for (int i = 0; i < n; i++)
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n');
bestn = n;
} else if (n < bestn - 1) {
int x = p[n-1] % W;
int y = p[n-1] / W;
for (int i = 0; i < 4; i++) {
for (int v = 1; ; v++) {
int tx = x + v*moves[i*2+0];
int ty = y + v*moves[i*2+1];
if (tx >= 0 && tx < W && ty >= 0 && ty < H) {
p[n] = ty*W + tx;
if ((n < 1 || grid[p[n-1]] != grid[p[n]]) &&
(n < 2 || grid[p[n-2]] != grid[p[n]])) {
bestn = solve(p, n + 1, bestn);
}
} else {
break;
}
}
}
}
return bestn;
}
int
main(void)
{
int path[13] = {0};
solve(path, 1, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2020-12.c
#include <stdio.h>
enum {C=1, V, A, X};
#define H 7
#define W 7
static const signed char grid[] = {
0, V, V, V, A, A, C,
V, A, A, V, A, 0, C,
A, 0, A, 0, C, V, C,
V, V, V, X, V, A, 0,
A, 0, 0, A, C, C, C,
A, 0, 0, A, A, 0, A,
A, C, A, V, C, A, C,
};
static const signed char moves[] = {
+1, +0, +0, +1, -1, +0, +0, -1,
};
static int
solve(int *p, int n, int d, int bestn)
{
if (p[n - 1] == W * H / 2) {
for (int i = 0; i < n; i++)
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n');
bestn = n;
} else if (n < bestn - 1) {
int x = p[n-1] % W;
int y = p[n-1] / W;
for (int v = 1; ; v++) {
int tx = x + v*moves[d*2+0];
int ty = y + v*moves[d*2+1];
if (tx >= 0 && tx < W && ty >= 0 && ty < H) {
int ti = ty*W + tx;
int g = grid[ti];
if (!g || (d%2 && g == V)) continue;
p[n] = ti;
bestn = solve(p, n + 1, (d + g + d%2*2) % 4, bestn);
} else {
break;
}
}
}
return bestn;
}
int
main(void)
{
int path[30] = {0};
solve(path, 1, 0, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2021-01.c
#include <stdio.h>
enum {D=1, S, C};
#define BEG 3
#define END 45
#define W 7
#define H 7
static const unsigned char grid[] = {
0, 0, 0, D, 0, 0, 0,
0, 0, D, D, S, 0, 0,
0, S, C, D, D, D, 0,
D, S, D, C, D, C, D,
0, D, C, D, D, D, 0,
0, 0, D, D, S, 0, 0,
0, 0, 0, D, 0, 0, 0,
};
static const int moves[] = {
+0, +1, -1, +1, -1, +0, -1, -1, +0, -1, +1, -1, +1, +0, +1, +1,
};
static int
solve(int *p, int n, int d, int bestn)
{
if (p[n] == END) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int a = grid[p[n]];
int b = n ? grid[p[n-1]] : 0;
for (int i = 0; i < 8; i++) {
if (i == (d + 4) % 8) continue; // no u-turns
for (int v = 1; ; v++) {
int tx = x + v*moves[i*2 + 0];
int ty = y + v*moves[i*2 + 1];
if (tx >= 0 && tx < W && ty >= 0 && ty < H) {
int ti = ty*W + tx;
int c = grid[ti];
if (c && c != a && c != b) {
p[n+1] = ti;
bestn = solve(p, n+1, i, bestn);
}
} else {
break;
}
}
}
}
return bestn;
}
int
main(void)
{
int path[10] = {BEG};
solve(path, 0, 0, sizeof(path)/sizeof(*path));
}
Raw
mazelog-2021-02.c
#include <stdio.h>
#define H 5
#define W 5
static const signed char grid[] = {
+0, +2, -1, -1, -1,
+2, -1, +0, +1, -3,
+0, +0, +1, -1, -1,
-1, -1, +0, -1, +2,
-1, +0, -1, -1, +0,
};
static const signed char moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1
};
static int
solve(int *p, int n, int v, int bestn)
{
if (p[n - 1] == W*H - 1) {
for (int i = 0; i < n; i++)
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n');
bestn = n;
} else if (n < bestn - 1) {
int x = p[n-1] % W;
int y = p[n-1] / W;
for (int i = 0; i < 4; i++) {
int tx = x + v*moves[i*2 + 0];
int ty = y + v*moves[i*2 + 1];
if (tx >= 0 && tx < W && ty >= 0 && ty < H) {
int t = ty * W + tx;
if (grid[t] + v >= 0) {
p[n] = t;
bestn = solve(p, n + 1, grid[t] + v, bestn);
}
}
}
}
return bestn;
}
int
main(void)
{
int path[12] = {0};
solve(path, 1, 3, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2021-03.c
#include <stdio.h>
#include <stdlib.h>
#define W 7
#define H 7
static const char grid[] = {
3, 1, 3, 4, 3, 4, 0,
2, 4, 1, 2, 1, 3, 0,
1, 1, 1, 4, 3, 4, 0,
2, 1, 1, 2, 1, 2, 0,
1, 4, 3, 1, 4, 4, 0,
3, 2, 4, 2, 1, 2, 0,
3, 1, 1, 4, 1, 4, 0,
};
static const signed char moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1,
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] % W == W - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int d = grid[p[n]];
for (int i = 0; i < 4; i++) {
int xx = x + d*moves[i*2 + 0];
int yy = y + d*moves[i*2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n+1] = xx + yy*W;
bestn = solve(p, n+1, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[19] = {21};
solve(path, 0, sizeof(path)/sizeof(*path));
return 0;
}
Raw
mazelog-2021-04.c
#include <stdio.h>
enum {G=0x10, B=0x20, R=0x30, V=0x40, Y=0x50, K=0x60};
enum {D=0x01, S=0x02, C=0x03, P=0x04, X=0x05, A=0x06};
#define H 5
#define W 5
static const signed char grid[] = {
B|C, K|A, R|A, G|C, K|C,
R|P, K|P, B|D, B|A, R|A,
V|C, V|X, Y|X, G|X, K|P,
Y|S, K|C, Y|P, R|A, R|P,
G|S, R|C, R|D, B|D, G|X,
};
static const signed char moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1
};
static int
solve(int *p, int n, int bestn)
{
if (p[n - 1] == W * H - 1) {
for (int i = 0; i < n; i++)
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n');
bestn = n;
} else if (n < bestn - 1) {
int x = p[n - 1] % W;
int y = p[n - 1] / W;
int m = n % 2 ? 0x0f : 0xf0;
for (int i = 0; i < 4; i++) {
for (int v = 1; ; v++) {
int tx = x + v*moves[i*2 + 0];
int ty = y + v*moves[i*2 + 1];
if (tx >= 0 && tx < W && ty >= 0 && ty < H) {
int t = ty * W + tx;
if ((grid[t] & m) == (grid[p[n-1]] & m)) {
p[n] = t;
bestn = solve(p, n + 1, bestn);
}
} else {
break;
}
}
}
}
return bestn;
}
int
main(void)
{
int path[14] = {0};
solve(path, 1, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2021-05.c
#include <stdio.h>
#define W 5
#define H 5
#define T 13
static const struct {
enum { M, A } op;
int value;
} grid[] = {
{M, +0}, {A, +1}, {M, +2}, {A, +2}, {A, +0},
{A, +1}, {M, +4}, {A, +2}, {A, -2}, {A, +2},
{M, +3}, {M, +2}, {A, +2}, {M, +2}, {M, +3},
{A, +2}, {A, +2}, {A, -2}, {M, +4}, {A, -3},
{A, -2}, {A, -2}, {M, +2}, {A, +1}, {A, +1},
};
static const int moves[] = {-1, +0, +1, +0, +0, -1, +0, +1};
static int
solve(int *p, int n, int v, int bestn)
{
switch (grid[p[n]].op) {
case M: v *= grid[p[n]].value; break;
case A: v += grid[p[n]].value; break;
}
if (p[n] == H*W - 1 && v == T) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (p[n] != H*W - 1 && n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
for (int i = 0; i < 4; i++) {
int xx = x + moves[i*2 + 0];
int yy = y + moves[i*2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n+1] = xx + yy * W;
bestn = solve(p, n+1, v, bestn);
}
}
}
return bestn;
}
int
main(void)
{
int path[15] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2021-06.c
#include <stdio.h>
enum {G=0x10, B=0x20, R=0x30, V=0x40, Y=0x50, O=0x60};
enum {D=0x01, S=0x02, C=0x03, E=0x04};
#define H 6
#define W 6
static const signed char grid[] = {
E|Y, D|G, D|O, D|V, C|V, S|O,
C|O, C|G, S|G, E|B, C|R, C|G,
E|R, C|B, E|V, C|R, D|B, S|O,
D|G, E|R, D|G, E|B, S|V, C|B,
D|G, E|G, C|G, S|R, E|O, S|B,
D|B, C|V, E|G, S|B, C|G, D|R,
};
static const signed char moves[] = {
-1, +0, +1, +0, +0, -1, +0, +1,
-1, -1, +1, +1, -1, +1, +1, -1,
};
static int
solve(int *p, int n, int bestn)
{
if (p[n-1] == W*H - 1) {
for (int i = 0; i < n; i++)
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n');
bestn = n;
} else if (n < bestn - 1) {
int x = p[n-1] % W;
int y = p[n-1] / W;
int m = n % 2 ? 0x0f : 0xf0;
for (int i = 0; i < 8; i++) {
for (int v = 1; ; v++) {
int tx = x + v*moves[i*2 + 0];
int ty = y + v*moves[i*2 + 1];
if (tx >= 0 && tx < W && ty >= 0 && ty < H) {
int t = ty * W + tx;
if ((grid[t] & m) == (grid[p[n-1]] & m)) {
p[n] = t;
bestn = solve(p, n + 1, bestn);
}
} else {
break;
}
}
}
}
return bestn;
}
int
main(void)
{
int path[23] = {0};
solve(path, 1, sizeof(path) / sizeof(*path));
return 0;
}
Raw
mazelog-2021-07.c
#include <stdio.h>
#define W 5
#define H 5
enum {NN, NE, EE, SE, SS, SW, WW, NW};
static const char grid[] = {
SS, SE, SW, SS, WW,
SE, EE, NN, SW, EE,
SS, WW, NN, EE, WW,
NN, NN, SW, SW, NN,
SE, NE, EE, SE, 0,
};
static const int moves[] = {
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1
};
static int
solve(int *p, int n, int bestn)
{
if (p[n] == W*H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int v = grid[p[n]];
for (int d = 1; ; d++) {
int xx = x + d*moves[v*2 + 0];
int yy = y + d*moves[v*2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n+1] = yy*W + xx;
bestn = solve(p, n + 1, bestn);
} else {
break;
}
}
}
return bestn;
}
int
main(void)
{
int path[18] = {0};
solve(path, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2021-08.c
#include <stdio.h>
#define W 4
#define H 4
enum {NN, NE, EE, SE, SS, SW, WW, NW};
static const char grid[] = {
EE, SW, SS, SW,
SE, SE, NN, WW,
SE, EE, NW, NN,
NN, WW, WW, 0,
};
static const int moves[] = {
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1
};
static int
solve(int *p, int n, int m, int bestn)
{
if (p[n] == W*H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int v = grid[p[n]];
for (int d = m ? m : 1; ; d += m ? 3 : 1) {
int xx = x + d*moves[v*2 + 0];
int yy = y + d*moves[v*2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n+1] = yy*W + xx;
bestn = solve(p, n + 1, m ? 0 : d, bestn);
} else {
break;
}
}
}
return bestn;
}
int
main(void)
{
int path[12] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2021-09.c
#include <stdio.h>
#define W 6
#define H 6
enum {P, R, B, K, Q, X};
static const char grid[] = {
Q, B, K, B, K, P,
B, P, B, R, P, P,
K, B, R, B, K, P,
P, R, B, R, P, K,
P, B, R, B, P, B,
P, K, P, K, B, X,
};
static const signed char moves[] = {
0, 0, 10, 4, 18, 4, 26, 8, 42, 8,
-1, +0, +1, +0, +0, -1, +0, +1,
-1, -1, +1, +1, -1, +1, +1, -1,
-2, -1, -2, +1, +2, -1, +2, +1,
-1, -2, -1, +2, +1, -2, +1, +2,
-1, +0, +1, +0, +0, -1, +0, +1,
-1, -1, +1, +1, -1, +1, +1, -1,
};
static int
solve(int *p, int n, int last, int bestn)
{
if (grid[p[n]] == X) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int c = grid[p[n]] ? grid[p[n]] : last;
int off = moves[c*2 + 0];
int len = moves[c*2 + 1];
const signed char *m = moves + off;
for (int i = 0; i < len; i++) {
int xx = x + m[i*2 + 0];
int yy = y + m[i*2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n+1] = xx + yy*W;
int loop = 0;
if (grid[p[n+1]]) {
for (int j = 0; !loop && j < n; j++) {
if (p[j] == p[n+1]) {
loop = 1;
}
}
}
if (!loop) {
bestn = solve(p, n+1, c, bestn);
}
}
}
}
return bestn;
}
int
main(void)
{
int path[25] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2021-10.c
#include <stdio.h>
#define W 5
#define H 4
enum {D, U, V, Z};
static const char grid[] = {
D, Z, U, V, Z,
V, U, U, U, V,
D, D, V, U, Z,
D, U, V, Z, 0,
};
static const int moves[] = {+1, +1, +1, -1, +0, +1, +1, +0};
static int
solve(int *p, int n, int last, int bestn)
{
if (p[n] == W*H - 1) {
for (int i = 0; i <= n; i++)
printf("%d%c", p[i] + 1, " \n"[i == n]);
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
int a = n&1 ? last : 1;
int b = n&1 ? last : 4;
int c = grid[p[n]];
for (int d = a; d <= b; d++) {
for (int v = -1; v <= +1; v += 2) {
int xx = x + v*d*moves[c*2 + 0];
int yy = y + v*d*moves[c*2 + 1];
if (xx >= 0 && xx < W && yy >= 0 && yy < H) {
p[n+1] = xx + yy*W;
bestn = solve(p, n+1, d, bestn);
}
}
}
}
return bestn;
}
int
main(void)
{
int path[26] = {0};
solve(path, 0, 0, sizeof(path) / sizeof(*path));
}
Raw
mazelog-2021-11.c
#include <stdio.h>
enum {H, D, V, U, X};
#define H 7
#define W 7
static const signed char grid[] = {
D, U, V, H, U, U, D,
U, H, U, H, H, D, H,
U, H, H, H, D, D, H,
V, V, V, X, V, V, H,
V, V, D, U, V, V, V,
D, D, H, H, U, V, D,
D, U, H, H, U, U, X,
};
static const signed char moves[] = {
+1, +0, +0, +1, -1, +0, +0, -1,
};
static int
solve(int *p, int n, int d, int bestn)
{
if (p[n] == W*H - 1) {
for (int i = 0; i < n; i++)
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n');
bestn = n;
} else if (n < bestn - 1) {
int x = p[n] % W;
int y = p[n] / W;
for (int v = 1; ; v++) {
int tx = x + v*moves[d*2+0];
int ty = y + v*moves[d*2+1];
if (tx >= 0 && tx < W && ty >= 0 && ty < H) {
int ti = ty*W + tx;
int td = d;
switch (grid[ti]) {
case H: if (d%2 == 0) continue; td += 2; break;
case V: if (d%2 == 1) continue; td += 2; break;
case D: td += 1 + d%2*2; break;
case U: td += 3 + d%2*2; break;
}
p[n+1] = ti;
bestn = solve(p, n+1, td%4, bestn);
} else {
break;
}
}
}
return bestn;
}
int
main(void)
{
int path[14] = {24};
solve(path, 0, 1, sizeof(path) / sizeof(*path));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment