crooks

combinatorial rooks
git clone https://a3nm.net/git/crooks/
Log | Files | Refs

commit 675ac9eea9a69d27bc84bad4f5a7f70df0a1d093
parent 2ed29b3e942132d9a3b732f9e5a71d5c6b7d527d
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Sat, 31 May 2014 23:38:14 +0200

cleanup, comments

Diffstat:
main.c | 168++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------------------
1 file changed, 115 insertions(+), 53 deletions(-)

diff --git a/main.c b/main.c @@ -2,25 +2,51 @@ #include <stdlib.h> #include <time.h> +// usage: +// ./a.out N K [SEED] +// SEED is used to seed the RNG, otherwise time is used; +// used seed is always printed first +// N is grid size, K is number of rooks (program will increase K when it +// succeeded) + +// general idea: always take one of the rooks with most violations and move to a +// cell with least violations; when stuck for UBOUND steps, do a totally random +// move +// in all intermediate configurations there are never two rooks in direct +// attack, the program tries to minimize the number of cells attacked by wrong +// number of rooks +// TODO: optimize +// TODO: profile +// TODO: plot asymptotics to make conjectures +// TODO: optimize UBOUND + +// upper bound on grid size (N) for static allocation #define MAXN 20 +// number of useless steps to make before doing a random move #define UBOUND 10 -int debug = 0; +const int debug = 0; +// N: grid size +// K: number of rooks int N, K; -// z, x, y -// height, line, col +// stores if a cell is taken by a rook or not +// coordinates are z, x, y +// corresponding to height, line, col unsigned char G[MAXN][MAXN][MAXN]; -// attack patterns +// stores a number indicating by which directions the cell is attacked +// same coordinates +// numbers are in [0, 8[:, LSB is z, 2nd LSB is x, 3rd LSB is y unsigned char A[MAXN][MAXN][MAXN]; -// rook positions (z, x, y) +// stores the coordinates of each rook +// 0 is z (height), 1 is x (line), 2 is y (col) unsigned char R[MAXN*MAXN][3]; -// rook violations -//char V[MAXN*MAXN]; -// putative violations +// stores the number of violations (number of attacked cells attacked by two +// other rooks) for each cell (no matter whether it contains a rook or not) unsigned char V[MAXN][MAXN][MAXN]; void print() { + // print the current grid and also rook positions when debug for (int x = 0; x < N; x++) { for (int y = 0; y < N; y++) { int pos = -1; @@ -48,6 +74,7 @@ void print() { } void print_attacks() { + // print the attack pattern in each cell for (int z = 0; z < N; z++) { printf("== %d ==\n", z); for (int x = 0; x < N; x++) { @@ -62,6 +89,7 @@ void print_attacks() { } void print_all_violations() { + // print the number of violation in each cell for (int z = 0; z < N; z++) { printf("== %d ==\n", z); for (int x = 0; x < N; x++) { @@ -76,6 +104,7 @@ void print_all_violations() { } void print_violations() { + // print the number of violations of the rooks int tot = 0; for (int i = 0; i < K; i++) { int val = V[R[i][0]][R[i][1]][R[i][2]]; @@ -87,17 +116,19 @@ void print_violations() { } void upd_atk_rm(int i) { + // update A to reflect the fact that rook i is about to be removed int z = R[i][0]; int x = R[i][1]; int y = R[i][2]; for (int p = 0; p < N; p++) { - A[p][x][y] &= ~(1 << 0); - A[z][p][y] &= ~(1 << 1); - A[z][x][p] &= ~(1 << 2); + A[p][x][y] &= ~(1 << 0); // p x y attacked by z x y along direction z + A[z][p][y] &= ~(1 << 1); // z p y attacked by z x y along direction x + A[z][x][p] &= ~(1 << 2); // z x p attacked by z x y along direction y } } void upd_atk_add(int i) { + // update A to reflect the fact that rook i was just added int z = R[i][0]; int x = R[i][1]; int y = R[i][2]; @@ -110,6 +141,7 @@ void upd_atk_add(int i) { void num_attacks() { + // generate A from scratch for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) @@ -121,8 +153,9 @@ void num_attacks() { } - void check_attacks() { + // debug: regenerate A from scratch + // and check that the previous version was already correct int backup[MAXN][MAXN][MAXN]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) @@ -141,21 +174,26 @@ void check_attacks() { int num_violations() { + // regenerate V from scratch + // returns total number of violations + // TODO: find a way to update this rather than recompute int tot = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) - V[i][j][k] = 0; + V[i][j][k] = 0; // clear for (int z = 0; z < N; z++) for (int x = 0; x < N; x++) for (int y = 0; y < N; y++) { for (int p = 0; p < N; p++) { + // must count cells that have already two attack directions and are + // missing the attack direction from the current cell if (p != z && (A[p][x][y] | (1 << 0)) == 7) - {V[z][x][y]++;} + {V[z][x][y]++;} // putting rook in z x y would attack p x y thrice if (p != x && (A[z][p][y] | (1 << 1)) == 7) - {V[z][x][y]++;} + {V[z][x][y]++;} // putting rook in z x y would attack z p y thrice if (p != y && (A[z][x][p] | (1 << 2)) == 7) - {V[z][x][y]++;} + {V[z][x][y]++;} // putting rook in z x y would attack z x p thrice } if (G[z][x][y]) { tot += V[z][x][y]; @@ -165,24 +203,8 @@ int num_violations() { return tot; } -// int tot = 0; -// for (int i = 0; i < K; i++) { -// V[i] = 0; -// int z = R[i][0]; -// int x = R[i][1]; -// int y = R[i][2]; -// for (int p = 0; p < N; p++) { -// if (p != z && A[p][x][y] == 7) -// {V[i]++; tot++;} -// if (p != x && A[z][p][y] == 7) -// {V[i]++; tot++;} -// if (p != y && A[z][x][p] == 7) -// {V[i]++; tot++;} -// } -// } - void init_pos() { - // initial position + // create initial position for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) @@ -207,6 +229,11 @@ void init_pos() { } int choose_rook(int prev) { + // choose the next rook to move: a random one among the ones with maximal + // violations, forbiding prev (the previously moved rook) + // TODO: better notion including "age" of rook to favor moving old rooks (?) + // and small probability to move rooks with not exactly maximal num of viols + // TODO: make it faster (priority queue?) int best = -1; int nvs[MAXN*MAXN]; int nnvs = 0; @@ -218,6 +245,7 @@ int choose_rook(int prev) { best = nv; } } + // best is now the maximal num of violations for (int i = 0; i < K; i++) { if (i == prev) continue; @@ -225,10 +253,12 @@ int choose_rook(int prev) { nvs[nnvs++] = i; } } + // choose random rook among the optimal ones return nvs[rand() % nnvs]; } -void random_move() { +int random_move() { + // make a totally random move (when we are stuck) int rook = (rand() % K); //printf("move %d at random\n", rook); int z = R[rook][0]; @@ -242,17 +272,24 @@ void random_move() { ny = (rand() % N); nz = (rand() % N); if (!A[nz][nx][ny] && !G[nz][nx][ny]) - break; + break; // found a spot that's both empty and not in direct attack + // TODO: nothing tests if this loop stands a chance of terminating, it would + // be neater to exit the program then } G[nz][nx][ny] = 1; R[rook][0] = nz; R[rook][1] = nx; R[rook][2] = ny; - num_attacks(); - num_violations(); + // recompute everything + upd_atk_add(rook); + return num_violations(); } void position(int i) { + // position rook i that was just removed + // TODO: more efficient (pqueue?) + // TODO more clever (chance to select cell with non-optimal number of + // violations) int best = N*N*N+1; int bs[MAXN*MAXN*MAXN][3]; int nbs = 0; @@ -263,6 +300,7 @@ void position(int i) { if (V[z][x][y] < best) { best = V[z][x][y]; } + // best is now the minimal number of violations for (int z = 0; z < N; z++) for (int x = 0; x < N; x++) for (int y = 0; y < N; y++) @@ -274,6 +312,7 @@ void position(int i) { nbs++; if (debug) printf("%d %d %d is a fitting position\n", z, x, y); } + // choose random cell among optimal ones int npos = rand() % nbs; int bz = bs[npos][0]; int bx = bs[npos][1]; @@ -287,6 +326,7 @@ void position(int i) { } void spawn_rook() { + // add a new rook to the problem position(K-1); } @@ -304,51 +344,71 @@ int main(int argc, char **argv) { } printf("using random seed %d\n", seed); srand(seed); + int tot; for (K = oK; K < N*N; K++) { printf("try %d rooks\n", K); + // starting position if we just started, otherwise add the rook to the + // existing position if (first) { init_pos(); first = 0; } else { spawn_rook(); } + + // compute number of attacks and violations num_attacks(); tot = num_violations(); print(); - //print_attacks(); - //print_violations(); - int useless1 = 0, useless2 = 0; - int prev_raw = -1; + + int useless = 0; + int prev_rook = -1; + + // improve while violations remain while (tot > 0) { if (debug) print_violations(); - int rook = choose_rook(prev_raw); - prev_raw = rook; + + // choose a rook + int rook = choose_rook(prev_rook); + prev_rook = rook; + // when doing a useless step, offset the choice //rook = (rook + useless1) % K; - if(debug) printf("chosen rook %d yields %d\n", prev_raw, rook); + if(debug) printf("chosen rook %d\n", rook); if(debug) print(); if(debug) print_attacks(); int z = R[rook][0]; int x = R[rook][1]; int y = R[rook][2]; + + // remove the rook G[z][x][y] = 0; upd_atk_rm(rook); R[rook][0] = MAXN; R[rook][1] = MAXN; R[rook][2] = MAXN; + if(debug) print_attacks(); - if(debug) check_attacks(); + //check_attacks(); + + // recompute V without the rook num_violations(); + + // choose next position position(rook); + int otot = tot; int pred = V[R[rook][0]][R[rook][1]][R[rook][2]]; if(debug) print(); if(debug) print_all_violations(); + + // recompute number of violations tot = num_violations(); + if(debug) print_all_violations(); int npred = V[R[rook][0]][R[rook][1]][R[rook][2]]; - if (npred != pred) { + if (debug && npred != pred) { printf("violation mispredict: thought %d and had %d!\n", pred, npred); exit(1); } @@ -356,18 +416,20 @@ int main(int argc, char **argv) { if(debug) print_attacks(); if(debug) print(); //printf("total viol %d\n", tot); + if (tot >= otot) { - // no improvement - useless1++; - useless2++; + // no improvement at this round + useless++; } else { - useless1 = useless2 = 0; + useless = 0; } - if (useless1 > UBOUND || useless2 > UBOUND) { - useless1 = useless2 = 0; - random_move(); + if (useless > UBOUND) { + // too many useless steps, do a random move + useless = 0; + tot = random_move(); } } + // we have found a configuration for K rooks; display it printf("!!! DONE %d rooks\n", K); print(); }