Skip to content

Instantly share code, notes, and snippets.

@skeeto

skeeto/rooks.c

Last active May 22, 2020
Embed
What would you like to do?
Sliding Rooks solver and animator
/* Sliding Rooks solution with animation
* $ cc -Ofast rooks.c
* $ ./a.out | mpv --no-correct-pts --fps=60 -
* $ ./a.out | x264 --fps=60 -o rooks.mp4 /dev/stdin
* Ref: https://possiblywrong.wordpress.com/2020/05/20/sliding-rooks-and-queens/
* Ref: https://nullprogram.com/video/?v=rooks
*/
#include <stdio.h>
static const unsigned char value_pal[] = {0x00, 0x67, 0x94, 0xff};
static const unsigned char value_rle[] = {
0xff, 0xff, 0xff, 0x31, 0xf8, 0x01, 0x00, 0x01, 0x01, 0x01, 0xff,
0x01, 0xf8, 0x01, 0x00, 0x02, 0x2f, 0x01, 0xff, 0x01, 0x40, 0x01,
0x00, 0x01, 0x2f, 0x01, 0xff, 0x08, 0xf8, 0x01, 0x00, 0x02, 0xff,
0x01, 0xf8, 0x01, 0x00, 0x02, 0x2f, 0x01, 0xff, 0x01, 0x00, 0x02,
0x2f, 0x01, 0xff, 0x08, 0xf8, 0x01, 0x00, 0x02, 0xff, 0x01, 0xf8,
0x01, 0x00, 0x02, 0x2f, 0x01, 0xff, 0x01, 0x00, 0x02, 0x2f, 0x01,
0xff, 0x08, 0xf8, 0x01, 0x00, 0x02, 0x55, 0x01, 0x50, 0x01, 0x00,
0x02, 0x05, 0x01, 0x55, 0x01, 0x00, 0x02, 0x2f, 0x01, 0xff, 0x08,
0xf8, 0x01, 0x00, 0x0a, 0x2f, 0x01, 0xff, 0x08, 0xf8, 0x01, 0x00,
0x0a, 0x2f, 0x01, 0xff, 0x08, 0xf8, 0x01, 0x00, 0x0a, 0x2f, 0x01,
0xff, 0x08, 0xf8, 0x01, 0x00, 0x0a, 0x2f, 0x01, 0xff, 0x08, 0xf4,
0x01, 0x00, 0x0a, 0x1f, 0x01, 0xff, 0x08, 0xf7, 0x01, 0xff, 0x0a,
0xdf, 0x01, 0xff, 0x08, 0xf6, 0x01, 0xff, 0x0a, 0x9f, 0x01, 0xff,
0x08, 0xfe, 0x01, 0x00, 0x0a, 0xbf, 0x01, 0xff, 0x09, 0xc0, 0x01,
0x00, 0x08, 0x03, 0x01, 0xff, 0x0a, 0xf4, 0x01, 0x6a, 0x01, 0xaa,
0x06, 0xa9, 0x01, 0x1f, 0x01, 0xff, 0x0a, 0xfd, 0x01, 0xff, 0x08,
0x7f, 0x01, 0xff, 0x0a, 0xfe, 0x01, 0x00, 0x08, 0xbf, 0x01, 0xff,
0x0b, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08,
0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00,
0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c,
0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff,
0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08,
0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00,
0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c, 0x00, 0x08, 0xff, 0x0c,
0x00, 0x08, 0xff, 0x0b, 0xfe, 0x01, 0x55, 0x08, 0xbf, 0x01, 0xff,
0x0a, 0xfd, 0x01, 0xff, 0x08, 0x7f, 0x01, 0xff, 0x0a, 0xfc, 0x01,
0x15, 0x01, 0x55, 0x06, 0x54, 0x01, 0x3f, 0x01, 0xff, 0x0a, 0xf4,
0x01, 0x00, 0x08, 0x1f, 0x01, 0xff, 0x0a, 0xeb, 0x01, 0xff, 0x08,
0xeb, 0x01, 0xff, 0x0a, 0x4b, 0x01, 0xff, 0x08, 0xe1, 0x01, 0xff,
0x0a, 0x00, 0x0a, 0xff, 0x0a, 0x00, 0x0a, 0xff, 0x0a, 0x00, 0x0a,
0xff, 0x0a, 0x00, 0x0a, 0xff, 0x0a, 0x00, 0x0a, 0xff, 0x0a, 0x7f,
0x01, 0xff, 0x08, 0xfd, 0x01, 0xff, 0x08, 0xfc, 0x01, 0x00, 0x01,
0x7f, 0x01, 0xff, 0x08, 0xfd, 0x01, 0x00, 0x01, 0x3f, 0x01, 0xff,
0x06, 0xfc, 0x01, 0x00, 0x0c, 0x3f, 0x01, 0xff, 0x06, 0xfc, 0x01,
0x00, 0x0c, 0x3f, 0x01, 0xff, 0x06, 0xfc, 0x01, 0x00, 0x0c, 0x3f,
0x01, 0xff, 0x06, 0xfc, 0x01, 0x00, 0x0c, 0x3f, 0x01, 0xff, 0x06,
0xfc, 0x01, 0x00, 0x0c, 0x3f, 0x01, 0xff, 0x06, 0xfc, 0x01, 0x00,
0x0c, 0x3f, 0x01, 0xff, 0x06, 0xfe, 0x01, 0xaa, 0x0c, 0xbf, 0x01,
0xff, 0xb7
};
static const unsigned char alpha_pal[] = {0x00, 0x6b, 0xa1, 0xff};
static const unsigned char alpha_rle[] = {
0x00, 0xff, 0x00, 0x31, 0x07, 0x01, 0xff, 0x01, 0xfe, 0x01, 0x00,
0x01, 0x07, 0x01, 0xff, 0x02, 0xd0, 0x01, 0x00, 0x01, 0xbf, 0x01,
0xff, 0x01, 0xd0, 0x01, 0x00, 0x08, 0x0b, 0x01, 0xff, 0x02, 0x00,
0x01, 0x0b, 0x01, 0xff, 0x02, 0xe0, 0x01, 0x00, 0x01, 0xff, 0x02,
0xe0, 0x01, 0x00, 0x08, 0x0b, 0x01, 0xff, 0x02, 0x00, 0x01, 0x0b,
0x01, 0xff, 0x02, 0xe0, 0x01, 0x00, 0x01, 0xff, 0x02, 0xe0, 0x01,
0x00, 0x08, 0x0b, 0x01, 0xff, 0x02, 0xaa, 0x01, 0xaf, 0x01, 0xff,
0x02, 0xfa, 0x01, 0xaa, 0x01, 0xff, 0x02, 0xe0, 0x01, 0x00, 0x08,
0x0b, 0x01, 0xff, 0x0a, 0xe0, 0x01, 0x00, 0x08, 0x0b, 0x01, 0xff,
0x0a, 0xe0, 0x01, 0x00, 0x08, 0x0b, 0x01, 0xff, 0x0a, 0xe0, 0x01,
0x00, 0x08, 0x0b, 0x01, 0xff, 0x0a, 0xe0, 0x01, 0x00, 0x08, 0x0b,
0x01, 0xff, 0x0a, 0xe0, 0x01, 0x00, 0x08, 0x0f, 0x01, 0xff, 0x0a,
0xf0, 0x01, 0x00, 0x08, 0x0b, 0x01, 0xff, 0x0a, 0xe0, 0x01, 0x00,
0x08, 0x01, 0x01, 0xff, 0x0a, 0x40, 0x01, 0x00, 0x09, 0x3f, 0x01,
0xff, 0x08, 0xfc, 0x01, 0x00, 0x0a, 0x0f, 0x01, 0xff, 0x08, 0xf0,
0x01, 0x00, 0x0a, 0x03, 0x01, 0xff, 0x08, 0xc0, 0x01, 0x00, 0x0a,
0x01, 0x01, 0xff, 0x08, 0x40, 0x01, 0x00, 0x0b, 0xff, 0x08, 0x00,
0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08,
0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff,
0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c,
0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00,
0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08,
0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff,
0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0c, 0xff, 0x08, 0x00, 0x0b,
0x01, 0x01, 0xff, 0x08, 0x40, 0x01, 0x00, 0x0a, 0x02, 0x01, 0xff,
0x08, 0x80, 0x01, 0x00, 0x0a, 0x03, 0x01, 0xff, 0x08, 0xc0, 0x01,
0x00, 0x0a, 0x0b, 0x01, 0xff, 0x08, 0xe0, 0x01, 0x00, 0x0a, 0x1f,
0x01, 0xff, 0x08, 0xf4, 0x01, 0x00, 0x0a, 0xbf, 0x01, 0xff, 0x08,
0xfe, 0x01, 0x00, 0x0a, 0xff, 0x0a, 0x00, 0x0a, 0xff, 0x0a, 0x00,
0x0a, 0xff, 0x0a, 0x00, 0x0a, 0xff, 0x0a, 0x00, 0x0a, 0xff, 0x0a,
0x00, 0x0a, 0xff, 0x0a, 0x00, 0x08, 0x03, 0x01, 0xff, 0x0c, 0xc0,
0x01, 0x00, 0x06, 0x03, 0x01, 0xff, 0x0c, 0xc0, 0x01, 0x00, 0x06,
0x03, 0x01, 0xff, 0x0c, 0xc0, 0x01, 0x00, 0x06, 0x03, 0x01, 0xff,
0x0c, 0xc0, 0x01, 0x00, 0x06, 0x03, 0x01, 0xff, 0x0c, 0xc0, 0x01,
0x00, 0x06, 0x03, 0x01, 0xff, 0x0c, 0xc0, 0x01, 0x00, 0x06, 0x03,
0x01, 0xff, 0x0c, 0xc0, 0x01, 0x00, 0x06, 0x01, 0x01, 0x55, 0x0c,
0x40, 0x01, 0x00, 0xb7
};
// Unpack 24-bit (4 6-bit elements) representation into a bitboard.
static unsigned long long
unpack(long state)
{
return 1ULL << (state & 0x3f) |
1ULL << (state >> 6 & 0x3f) |
1ULL << (state >> 12 & 0x3f) |
1ULL << (state >> 18 );
}
// Pack bitboard into 24-bit (4 6-bit elements) representation.
static long
pack(unsigned long long board)
{
long a = __builtin_ctzll(board); board &= ~(1ULL << a);
long b = __builtin_ctzll(board); board &= ~(1ULL << b);
long c = __builtin_ctzll(board); board &= ~(1ULL << c);
long d = __builtin_ctzll(board);
return a<<18 | b<<12 | c<<6 | d;
}
// Populate r with neighboring states.
static int
neighbors(long state, long *r)
{
unsigned long long board = unpack(state);
int c = 0;
for (int i = 0; i < 4; i++) {
int found;
int v = state>>(6*i) & 0x3f;
found = 0;
for (int d = 8; d < 64; d += 8) {
if (v - d >= 0 && !((1ULL<<(v - d)) & board)) {
unsigned long long n = board;
n |= 1ULL << (v - d);
n &= ~(1ULL << v);
r[c] = pack(n);
found = 1;
} else {
break;
}
}
c += found;
found = 0;
for (int d = 8; d < 64; d += 8) {
if (v + d < 64 && !((1ULL<<(v + d)) & board)) {
unsigned long long n = board;
n |= 1ULL << (v + d);
n &= ~(1ULL << v);
r[c] = pack(n);
found = 1;
} else {
break;
}
}
c += found;
found = 0;
for (unsigned d = 1; d < 8; d++) {
if ((v - d)>>3 == (unsigned)v>>3 && !((1ULL<<(v - d)) & board)) {
unsigned long long n = board;
n |= 1ULL << (v - d);
n &= ~(1ULL << v);
r[c] = pack(n);
found = 1;
} else {
break;
}
}
c += found;
found = 0;
for (unsigned d = 1; d < 8; d++) {
if ((v + d)>>3 == (unsigned)v>>3 && !((1ULL<<(v + d)) & board)) {
unsigned long long n = board;
n |= 1ULL << (v + d);
n &= ~(1ULL << v);
r[c] = pack(n);
found = 1;
} else {
break;
}
}
c += found;
}
return c;
}
// Raw image data
static unsigned char buf[640][640][3];
static unsigned char alpha[80][20];
static unsigned char value[80][20];
static void
uncompress(unsigned char dst[80][20], const unsigned char *rle)
{
unsigned char *p = (void *)dst;
for (int i = 0; i < 80*20;) {
int v = *rle++;
int r = *rle++;
for (int j = 0; j < r; j++, i++) {
p[i] = v;
}
}
}
static void
frame(void)
{
puts("P6\n640 640\n255");
fwrite(buf, sizeof(buf), 1, stdout);
}
static void
put(int x, int y, long c)
{
buf[y][x][0] = c >> 16;
buf[y][x][1] = c >> 8;
buf[y][x][2] = c >> 0;
}
static long
get(int x, int y)
{
return (long)buf[y][x][0] << 16 |
(long)buf[y][x][1] << 8 |
(long)buf[y][x][2] << 0;
}
static void
clear(void)
{
static const long colors[] = {0xffce9eL, 0xd18b47L};
for (int y = 0; y < 640; y++) {
for (int x = 0; x < 640; x++) {
put(x, y, colors[(x/80+y/80)%2]);
}
}
}
static long
blend(long c0, long c1, float a)
{
float r0 = ((c0 >> 16) )/255.0f;
float g0 = ((c0 >> 8) & 0xff)/255.0f;
float b0 = ( c0 & 0xff)/255.0f;
float r1 = ((c1 >> 16) )/255.0f;
float g1 = ((c1 >> 8) & 0xff)/255.0f;
float b1 = ( c1 & 0xff)/255.0f;
float r = r0*a + r1*(1-a);
float g = g0*a + g1*(1-a);
float b = b0*a + b1*(1-a);
return (long)(r*255) << 16 |
(long)(g*255) << 8 |
(long)(b*255) << 0;
}
static void
rook(int x, int y)
{
for (int py = 0; py < 80; py++) {
for (int px = 0; px < 80; px++) {
int dx = x + px;
int dy = y + py;
if (dx >= 0 && dx < 640 && dy >= 0 && dy < 640) {
long v = value_pal[value[py][px/4] >> (2*(3-px%4)) & 3];
float a = alpha_pal[alpha[py][px/4] >> (2*(3-px%4)) & 3]/255.0f;
long f = v<<16|v<<8|v;
long b = get(dx, dy);
put(dx, dy, blend(f, b, a));
}
}
}
}
static void
draw(long state)
{
unsigned long long board = unpack(state);
clear();
for (int y = 0; y < 8; y++) {
for (int x = 0; x < 8; x++) {
if (board >> (y*8 + x) & 1) {
rook(x*80, y*80);
}
}
}
}
static void
slide(long s0, long s1)
{
unsigned long long b0 = unpack(s0);
unsigned long long b1 = unpack(s1);
int src = __builtin_ctzll(b0 & (b0 ^ b1));
int dst = __builtin_ctzll(b1 & (b0 ^ b1));
int srcx = src%8*80;
int srcy = src/8*80;
int dstx = dst%8*80;
int dsty = dst/8*80;
int dx = dstx - srcx;
int speed = 8; // must evenly divide 80
if (dx < 0) dx = -speed;
if (dx > 0) dx = +speed;
int dy = dsty - srcy;
if (dy < 0) dy = -speed;
if (dy > 0) dy = +speed;
for (; srcx != dstx || srcy != dsty; srcx += dx, srcy += dy) {
clear();
unsigned long long fixed = b0 & b1;
for (int i = 0; i < 3; i++) {
int p = __builtin_ctzll(fixed);
fixed &= ~(1ULL << p);
int x = p%8*80;
int y = p/8*80;
rook(x, y);
}
rook(srcx, srcy);
frame();
}
rook(dstx, dsty);
frame();
}
int
main(void)
{
long init = 7L<<12 | 56L<<6 | 63L;
long goal = 27L<<18 | 28L<<12 | 35L<<6 | 36L;
#ifdef _WIN32
/* Set stdout to binary mode. */
int _setmode(int, int);
_setmode(1, 0x8000);
#endif
#define N (sizeof(long)*8)
#define GET(v) (seen[v/N] & 1UL<<(v%N))
#define SET(v) (seen[v/N] |= 1UL<<(v%N))
static unsigned long seen[(1L<<24)/N];
static struct {
long state;
long parent;
} queue[1L<<20];
long tail = 0;
long head = 0;
SET(init);
queue[head].state = init;
queue[head++].parent = -1;
uncompress(value, value_rle);
uncompress(alpha, alpha_rle);
clear();
draw(init);
for (int i = 0; i < 60*1; i++) {
frame();
}
while (head != tail) {
long state = queue[tail].state;
if (state == goal) {
/* Render the solution */
int n = 0;
long i = tail;
long chain[64];
do {
chain[n++] = i;
i = queue[i].parent;
} while (i >= 0);
for (n -= 2; n >= 0; n--) {
slide(queue[chain[n+1]].state, queue[chain[n]].state);
}
clear();
draw(state);
for (int i = 0; i < 60*2; i++) {
frame();
}
break;
}
long parent = tail++;
long ns[16];
int c = neighbors(state, ns);
for (int i = 0; i < c; i++) {
long n = ns[i];
if (!GET(n)) {
SET(n);
queue[head].state = n;
queue[head++].parent = parent;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.