Author: Dann Corbit
Date: 14:41:08 05/04/01
I thought the technique used here was fascinating. Perhaps it can be
generalized to regular chess. If so, there could possibly be a dramatic
speedup. Of course, a knight's tour is a lot simpler than playing chess. But
there are potentially enormous benefits to be reaped.
/* Knight's Tour Problem - a kind of undirected Hamiltonian circuits
Using an advanced algorithm - at least 10000 times faster than simple
backtracking
The key idea is to detect bi-degree nodes and also the art of programming
Enjoy it!
Author : Fei Lu - student of Shanghai Jiao Tong University
Email : flyland@bigfoot.com
Homepage & Research Center : flyland.bentium.net
*/
#define N 8
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <limits.h>
clock_t start,
finish;
double duration;
int board[N * N];
int (*board2D)[N] = (int (*)[N]) &board;
int degree[N * N];
int (*degree2D)[N] = (int (*)[N]) °ree;
int branch[N * N][8],
Xbranch[N * N][8];
int (*branch2D)[N][8] = (int (*)[N][8]) &branch;
int nBranch[N * N],
XnBranch[N * N];
int (*nBranc2d)[N] = (int (*)[N]) &nBranch;
int blist[N * N][9][3];
int iDir[8] =
{-2, -1, 1, 2, 2, 1, -1, -2};
int jDir[8] =
{1, 2, 2, 1, -1, -2, -2, -1};
int path[N * N + 1];
int dir[N * N + 1];
int n;
int cnt = 0;
unsigned int nSolution_High = 0,
nSolution_Low = 0;
void printBoard()
{
int i,
j;
char buf[80];
for (i = 0; i < 4 * N + 1; i++)
buf[i] = '-';
buf[i] = 0;
printf("%s\n", buf);
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
if (board2D[i][j] == 0)
printf("|%3d", N * N - 1);
else
printf("|%3d", abs(board2D[i][j]));
};
printf("|\n");
};
printf("%s\n", buf);
}
void record()
{
nSolution_Low++;
if (nSolution_Low == 0)
nSolution_High++;
if (nSolution_Low % 100000 == 0) {
finish = clock();
duration = (double) (finish - start) / CLOCKS_PER_SEC;
printf("Solved %.2le (%u) %8.1f seconds\n",
((double) nSolution_High) * UINT_MAX + nSolution_Low, nSolution_Low,
duration);
printBoard();
};
}
int re_calc_degree(int t)
{
int d,
u,
m,
count = 0;
int degree2 = 0;
int u2;
m = nBranch[t];
for (d = 0; d < m; d++) {
u = branch[t][d];
if (board[u] > 0)
continue;
if (degree[u] == 2) {
if (degree2 > 0 || u == 2 * N + 1) {
for (d = 0; d < count; d++)
degree[Xbranch[t][d]]++;
return -1;
};
degree2++;
u2 = u;
};
degree[u]--;
Xbranch[t][count++] = u;
};
if (degree2 == 0) {
XnBranch[t] = count;
} else {
Xbranch[t][0] = u2;
XnBranch[t] = 1;
};
return 0;
}
void restore_degree(int t)
{
int d,
m,
u;
m = nBranch[t];
for (d = 0; d < m; d++) {
u = branch[t][d];
if (board[u] > 0)
continue;
degree[u]++;
};
}
/*
// Precondition: Knight now stays at the n(th) grid at (i,j)
// where i*N+j=path[n] and the travel goes on ...
// before travel further backup his direction in dir[n]
*/
void Travel()
{
int m,
d;
int here,
there;
while (n > 1) {
LOOP:
here = path[n];
m = XnBranch[here];
for (d = ++dir[n]; d < m; d++) {
there = Xbranch[here][d];
if (there == 2 * N + 1)
continue;
board[there] = n + 1;
if (re_calc_degree(there) == -1) {
board[there] = 0;
continue;
};
dir[n++] = d;
path[n] = there;
dir[n] = -1;
if (n < N * N - 2)
goto LOOP;
else {
record();
restore_degree(there);
board[there] = 0;
n--;
break;
};
};
restore_degree(here);
board[here] = 0;
n--;
};
}
void init()
{
int i,
j,
ip,
jp,
k;
int count;
memset(board, 0, sizeof(board));
memset(dir, -1, sizeof(dir));
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
count = 0;
for (k = 0; k < 8; k++) {
ip = i + iDir[k];
jp = j + jDir[k];
if (ip < 0 || jp < 0 || ip >= N || jp >= N)
continue;
branch[i * N + j][count] = ip * N + jp;
count++;
};
degree[i * N + j] = nBranch[i * N + j] = count;
};
};
degree2D[2][1]++;
board2D[2][1] = -N * N;
path[1] = 0;
board2D[0][0] = 1;
re_calc_degree(0);
path[2] = 1 * N + 2;
board2D[1][2] = 2;
re_calc_degree(1 * N + 2);
n = 2;
}
int main(void)
{
start = clock();
init();
Travel();
return 0;
}
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.