Hi Tim,
Enclosed are the solutions for the swapping knights on a 5x5 board problem and the two programs which generate the solution. These consist of:
knight2.c - Computes the minimum move array and writes it out to the hard disk.
extract.c - Dumps the solutions to the display.Both programs are fairly simple, in comparison to the other two programs posted. The only really complicated functions are the conversion from a state number to a 5x5 array, CreateGrid(), and back again, CalcHash().
If you ever get the time to set up a web site detailing the problem and solving it, feel free to use the source code (might be an idea to combine the two programs into a single program).
Justin
#include <stdio.h>
#include <memory.h>
#define NUMBER_STATES 67603900
// m! / n!(m-n)!
long perms(int m, int n)
{
int p;
long total;
if (m < n || n < 0)
return 0;
total = m;
for (p = 2; p <= n; p++)
total = total * --m / p;
return total;
}
long table[32][64];
void InitTable(void)
{
int m,n;
memset(table, 0, sizeof(table));
for (m=0; m<24; m++)
for (n=0; n<=m; n++)
table[m][32+n*2-m] = 25 * perms(23-m, 12-n);
}
int CreateGrid(long hash, char * grid)
{
int gap, n, nblack=0, nwhite=0;
gap = hash % 25;
for (n=0; n<25; n++) {
if (n == gap) {
grid[n] = 0;
} else if (nblack == 12) {
grid[n] = 2; // 12 black knights, rest must be white
} else if (nwhite == 12) {
grid[n] = 1; // 12 white knights, rest must be black
} else if (hash >= table[nblack+nwhite][32+nblack-nwhite]) {
hash -= table[nblack+nwhite][32+nblack-nwhite];
grid[n] = 1;
nblack++;
} else {
grid[n] = 2;
nwhite++;
}
}
return gap;
}
long CalcHash(char * grid, int gap)
{
int n, nblack=0, nwhite=0;
long hash = gap;
for (n=0; n<25; n++) {
if (grid[n] == 0 || nblack == 12 || nwhite == 12) {
// nothing
} else if (grid[n] == 1) {
hash += table[nblack+nwhite][32+nblack-nwhite];
nblack++;
} else
nwhite++;
}
return hash;
}
void DumpGrid(char * grid)
{
int x,y;
for (y=0;y<5; y++) {
for (x=0;x<5;x++) {
switch(grid[y*5+x]) {
case 0:
printf(".");
break;
case 1:
printf("B");
break;
case 2:
printf("W");
break;
}
}
printf(" ");
}
printf("\n");
}
char states[NUMBER_STATES];
void main(void)
{
int n, move, gap, newgap, dir, x, y;
char grid[5*5];
int yadd[] = {2, 1, -1, -2, 2, 1, -1, -2};
int xadd[] = {1, 2, 2, 1, -1, -2, -2, -1};
long state_number, hash;
long statesDone=0, statesToDoNext=1;
FILE * fp;
InitTable();
memset(states, 0, sizeof(states));
states[66282462] = 1; // initial state, move = 1
move = 1;
while (statesDone != statesToDoNext) {
for (n=0;n<50; n++) {
for (state_number = NUMBER_STATES/50*n; state_number < NUMBER_STATES/50*(n+1); state_number++) {
if (states[state_number] == move) {
statesDone++; // reached this state on last move, so try all possibilities
gap = CreateGrid(state_number, grid);
for (dir = 0; dir<8; dir++) {
x = (gap % 5) + xadd[dir];
y = (gap / 5) + yadd[dir];
if (y >= 0 && y <= 4 && x >= 0 && x <= 4) {
newgap = y*5+x;
grid[gap] = grid[newgap];
grid[newgap] = 0;
// add move if not done so already
hash = CalcHash(grid, newgap);
if (states[hash] == 0) {
states[hash] = move+1;
statesToDoNext++; // another state to do on next iteration
}
grid[newgap] = grid[gap];
grid[gap] = 0;
}
}
}
}
printf("%ld %ld %ld\r", state_number, statesDone, statesToDoNext);
}
printf("%d %ld %ld \n", move, statesDone, statesToDoNext);
move++;
}
fp = fopen("states", "wb+");
fwrite(states, 1, sizeof(states), fp);
fclose(fp);
}
#include <stdio.h>
#include <memory.h>
// m! / n!(m-n)!
long perms(int m, int n)
{
int p;
long total;
if (m < n || n < 0)
return 0;
total = m;
for (p = 2; p <= n; p++)
total = total * --m / p;
return total;
}
long table[32][64];
void InitTable(void)
{
int m,n;
memset(table, 0, sizeof(table));
for (m=0; m<24; m++)
for (n=0; n<=m; n++)
table[m][32+n*2-m] = 25 * perms(23-m, 12-n);
}
int CreateGrid(long hash, char * grid)
{
int gap, n, nblack=0, nwhite=0;
gap = hash % 25;
for (n=0; n<25; n++) {
if (n == gap) {
grid[n] = 0;
} else if (nblack == 12) {
grid[n] = 2;
} else if (nwhite == 12) {
grid[n] = 1;
} else if (hash >= table[nblack+nwhite][32+nblack-nwhite]) {
hash -= table[nblack+nwhite][32+nblack-nwhite];
grid[n] = 1;
nblack++;
} else {
grid[n] = 2;
nwhite++;
}
}
return gap;
}
long CalcHash(char * grid, int gap)
{
int n, nblack=0, nwhite=0;
long hash = gap;
for (n=0; n<25; n++) {
if (grid[n] == 0 || nblack == 12 || nwhite == 12) {
// nothing
} else if (grid[n] == 1) {
hash += table[nblack+nwhite][32+nblack-nwhite];
nblack++;
} else
nwhite++;
}
return hash;
}
int move_list[64][2]; // [0]=from, [1]=to
long nsolutions = 0;
FILE *fp_states;
int GetMinimumMoves(long hash)
{
fseek(fp_states, hash, SEEK_SET);
return fgetc(fp_states);
}
void recurse(long state_number, int move)
{
static int yadd[] = {2, 1, -1, -2, 2, 1, -1, -2};
static int xadd[] = {1, 2, 2, 1, -1, -2, -2, -1};
static long hash;
static int newgap, gap, x, y;
static char grid[5*5];
int dir;
for (dir = 0; dir<8; dir++) {
gap = CreateGrid(state_number, grid);
x = (gap % 5) + xadd[dir];
y = (gap / 5) + yadd[dir];
if (y >= 0 && y <= 4 && x >= 0 && x <= 4) {
newgap = y*5+x;
grid[gap] = grid[newgap];
grid[newgap] = 0;
hash = CalcHash(grid, newgap);
if (GetMinimumMoves(hash) == (move-1)) {
move_list[move][0] = gap + 1;
move_list[move][1] = newgap + 1;
if (move == 2) {
for (gap=2; move_list[gap][0] != -1; gap++)
printf(" %d", move_list[gap][0]);
// printf("(%d->%d) ", move_list[gap][0], move_list[gap][1]);
nsolutions++;
printf("\n");
} else
recurse(hash, move-1);
}
}
}
}
void main(void)
{
if ((fp_states = fopen("states", "rb")) == NULL) {
printf("Minimum states file missing!\n");
return;
}
InitTable();
memset(move_list, -1, sizeof(move_list));
recurse(1321437, GetMinimumMoves(1321437));
printf("Solutions=%d\n", nsolutions);
fclose(fp_states);
}