horse in the chess
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#define SIDE 8
int chess[SIDE][SIDE]; // chess[i][j] = counter++
void print_chess() {
for (int i = 0; i < SIDE; ++i) {
for (int j = 0; j < SIDE; ++j) {
printf("%3d", chess[i][j]);
}
printf("\n");
}
printf("\n");
}
#define MAXDIRS 8
int dirs[MAXDIRS][2] = { { +1, -2 }, { +2, -1 }, { +2, +1 }, { +1, +2 },
{ -1, +2 }, { -2, +1 }, { -2, -1 }, { -1, -2 } };
#define MAXSTEP (SIDE * SIDE)
int path[MAXSTEP][2]; // { { x1, y1 }, { x2, y2 }, ... }
bool is_passable(int i, int j) {
return 0 <= i && i < SIDE && 0 <= j && j < SIDE && chess[i][j] == 0;
}
int steps_at(int i, int j) {
int steps = 0;
for (int k = 0; k < MAXDIRS; ++k) {
int x = i + dirs[k][0];
int y = j + dirs[k][1];
is_passable(x, y) && steps++;
}
return steps;
}
void solve(int i, int j, int counter) {
chess[i][j] = counter;
int nextx = -1, nexty, minsteps = MAXSTEP;
for (int k = 0; k < MAXDIRS; ++k) {
int x = i + dirs[k][0];
int y = j + dirs[k][1];
if (is_passable(x, y) && steps_at(x, y) <= minsteps) {
minsteps = steps_at(x, y);
nextx = x, nexty = y;
}
}
if (nextx != -1) {
solve(nextx, nexty, counter + 1);
}
}
int main() {
srand((unsigned int)time(NULL));
solve(rand() % SIDE, rand() % SIDE, 1);
print_chess();
}
C
INFO