From: rchappa@dcc.uchile.cl (Rodrigo Antonio Chappa Leiva)
Subject: Optimized Knight's tour
Originator: rchappa@dcc.uchile.cl
Date: Sat, 22 Aug 1992 20:41:05 GMT
Organization: Universidad de Chile, Depto. de Ciencias de la Computacion


This is my second try to solve Knight's tour. It spends one third the
time my first version does.

Here we go again :

--- tour7.c -----

# include <stdio.h>   /* Rodrigo A. Chiappa L. */

# define SIDE        8
# define TOTAL_SIZE 64

# define POS(i,j)    (i<<3) | j

int tablero[TOTAL_SIZE];

/* I'm using a table now to improve speed */
int  new_pos[TOTAL_SIZE][8] = {
 {  10, 17, -1, -1, -1, -1, -1, -1 }, /* Square  0 */ 
 {  11, 18, 16, -1, -1, -1, -1, -1 }, /* Square  1 */ 
 {  12, 19, 17,  8, -1, -1, -1, -1 }, /* Square  2 */ 
 {  13, 20, 18,  9, -1, -1, -1, -1 }, /* Square  3 */ 
 {  14, 21, 19, 10, -1, -1, -1, -1 }, /* Square  4 */ 
 {  15, 22, 20, 11, -1, -1, -1, -1 }, /* Square  5 */ 
 {  23, 21, 12, -1, -1, -1, -1, -1 }, /* Square  6 */ 
 {  22, 13, -1, -1, -1, -1, -1, -1 }, /* Square  7 */ 
 {  18, 25,  2, -1, -1, -1, -1, -1 }, /* Square  8 */ 
 {  19, 26, 24,  3, -1, -1, -1, -1 }, /* Square  9 */ 
 {  20, 27, 25, 16,  0,  4, -1, -1 }, /* Square 10 */ 
 {  21, 28, 26, 17,  1,  5, -1, -1 }, /* Square 11 */ 
 {  22, 29, 27, 18,  2,  6, -1, -1 }, /* Square 12 */ 
 {  23, 30, 28, 19,  3,  7, -1, -1 }, /* Square 13 */ 
 {  31, 29, 20,  4, -1, -1, -1, -1 }, /* Square 14 */ 
 {  30, 21,  5, -1, -1, -1, -1, -1 }, /* Square 15 */ 
 {  26, 33,  1, 10, -1, -1, -1, -1 }, /* Square 16 */ 
 {  27, 34, 32,  0,  2, 11, -1, -1 }, /* Square 17 */ 
 {  28, 35, 33, 24,  8,  1,  3, 12 }, /* Square 18 */ 
 {  29, 36, 34, 25,  9,  2,  4, 13 }, /* Square 19 */ 
 {  30, 37, 35, 26, 10,  3,  5, 14 }, /* Square 20 */ 
 {  31, 38, 36, 27, 11,  4,  6, 15 }, /* Square 21 */ 
 {  39, 37, 28, 12,  5,  7, -1, -1 }, /* Square 22 */ 
 {  38, 29, 13,  6, -1, -1, -1, -1 }, /* Square 23 */ 
 {  34, 41,  9, 18, -1, -1, -1, -1 }, /* Square 24 */ 
 {  35, 42, 40,  8, 10, 19, -1, -1 }, /* Square 25 */ 
 {  36, 43, 41, 32, 16,  9, 11, 20 }, /* Square 26 */ 
 {  37, 44, 42, 33, 17, 10, 12, 21 }, /* Square 27 */ 
 {  38, 45, 43, 34, 18, 11, 13, 22 }, /* Square 28 */ 
 {  39, 46, 44, 35, 19, 12, 14, 23 }, /* Square 29 */ 
 {  47, 45, 36, 20, 13, 15, -1, -1 }, /* Square 30 */ 
 {  46, 37, 21, 14, -1, -1, -1, -1 }, /* Square 31 */ 
 {  42, 49, 17, 26, -1, -1, -1, -1 }, /* Square 32 */ 
 {  43, 50, 48, 16, 18, 27, -1, -1 }, /* Square 33 */ 
 {  44, 51, 49, 40, 24, 17, 19, 28 }, /* Square 34 */ 
 {  45, 52, 50, 41, 25, 18, 20, 29 }, /* Square 35 */ 
 {  46, 53, 51, 42, 26, 19, 21, 30 }, /* Square 36 */ 
 {  47, 54, 52, 43, 27, 20, 22, 31 }, /* Square 37 */ 
 {  55, 53, 44, 28, 21, 23, -1, -1 }, /* Square 38 */ 
 {  54, 45, 29, 22, -1, -1, -1, -1 }, /* Square 39 */ 
 {  50, 57, 25, 34, -1, -1, -1, -1 }, /* Square 40 */ 
 {  51, 58, 56, 24, 26, 35, -1, -1 }, /* Square 41 */ 
 {  52, 59, 57, 48, 32, 25, 27, 36 }, /* Square 42 */ 
 {  53, 60, 58, 49, 33, 26, 28, 37 }, /* Square 43 */ 
 {  54, 61, 59, 50, 34, 27, 29, 38 }, /* Square 44 */ 
 {  55, 62, 60, 51, 35, 28, 30, 39 }, /* Square 45 */ 
 {  63, 61, 52, 36, 29, 31, -1, -1 }, /* Square 46 */ 
 {  62, 53, 37, 30, -1, -1, -1, -1 }, /* Square 47 */ 
 {  58, 33, 42, -1, -1, -1, -1, -1 }, /* Square 48 */ 
 {  59, 32, 34, 43, -1, -1, -1, -1 }, /* Square 49 */ 
 {  60, 56, 40, 33, 35, 44, -1, -1 }, /* Square 50 */ 
 {  61, 57, 41, 34, 36, 45, -1, -1 }, /* Square 51 */ 
 {  62, 58, 42, 35, 37, 46, -1, -1 }, /* Square 52 */ 
 {  63, 59, 43, 36, 38, 47, -1, -1 }, /* Square 53 */ 
 {  60, 44, 37, 39, -1, -1, -1, -1 }, /* Square 54 */ 
 {  61, 45, 38, -1, -1, -1, -1, -1 }, /* Square 55 */ 
 {  41, 50, -1, -1, -1, -1, -1, -1 }, /* Square 56 */ 
 {  40, 42, 51, -1, -1, -1, -1, -1 }, /* Square 57 */ 
 {  48, 41, 43, 52, -1, -1, -1, -1 }, /* Square 58 */ 
 {  49, 42, 44, 53, -1, -1, -1, -1 }, /* Square 59 */ 
 {  50, 43, 45, 54, -1, -1, -1, -1 }, /* Square 60 */ 
 {  51, 44, 46, 55, -1, -1, -1, -1 }, /* Square 61 */ 
 {  52, 45, 47, -1, -1, -1, -1, -1 }, /* Square 62 */ 
 {  53, 46, -1, -1, -1, -1, -1, -1 }};/* Square 63 */ 

 char total[TOTAL_SIZE] = {   2, 3, 4, 4, 4, 4, 3, 2,
                              3, 4, 6, 6, 6, 6, 4, 3,
                              4, 6, 8, 8, 8, 8, 6, 4,
                              4, 6, 8, 8, 8, 8, 6, 4,
                              4, 6, 8, 8, 8, 8, 6, 4,
                              4, 6, 8, 8, 8, 8, 6, 4,
                              3, 4, 6, 6, 6, 6, 4, 3,
                              2, 3, 4, 4, 4, 4, 3, 2 }; 

init()
{
    int i, j;

    for( i = 0; i < SIDE; i++ )
       for( j = 0; j < SIDE; j++ )
         tablero[ POS(i,j) ] = 0;

}

print_tablero()
{
    int i, j;

    printf( "------------------------\n" );
    for( i = 0; i < SIDE; i++ ) {
       for( j = 0; j < SIDE; j++ )
         printf( "%3d", tablero[ POS(i,j) ] );
       printf( "\n" );
    }
    printf( "------------------------\n\n" );
}

try( escaque, counter )
int escaque, counter;
{
    return( try2( escaque - 1, counter ) );
}

try2( from, counter )
int from;
int counter;
{
    int i;
    int to;
    int totals;

    totals = total[from];

    /* put a counter inside the square not to use it again */
    tablero[ from ] = counter;

    if( counter == 64 ) 
        return 1;

    for( i = 0; i < totals; i++ ) { 
         to = new_pos[from][i];
         if( tablero[ to ] ) continue; /* don't use squares already used */

         if( try2( to, counter + 1 ) )
             return 1;
    }

    /* clear bad moves */
    tablero[ from ] = 0;
    return 0;
}

main()
{
    int initial;   /* Enumerate squares from 1 to 64 then give an initial */
                   /* position to 'try' function, and wait ...            */

    init();
    initial = 1;
    if( try(  initial, 1 ) ) {
        printf( " Success ! \n" );
        print_tablero();
    }
}

--- end of tour7.c ----


Rodrigo.
rchappa@dcc.uchile.cl

Excuse me again because of my tarzan-like english  8)