Author: Matt Liegel
Date: 14:39:44 11/20/04
Go up one level in this thread
On November 20, 2004 at 03:35:17, Dann Corbit wrote:
>On November 20, 2004 at 01:20:02, Dan Andersson wrote:
>
>> If I remember correctly there was a fast knights tour solver using zero
>>supressed BDDs?
>>
>>MvH Dan Andersson
>
>/* 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;
>}
Hi, could someone please explain to me what the Knight Tour problem is and what
this program does?
Thanks
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.