Knight's Tour in C - Tom Wells

Finally, presenting the Knight's Tour in C - code by Tom Wells of tomwells.org.

Get the source from gitgub - git://github.com/drshade/knights-tour.git

#include 
#include 
#include 
#include 
#include 

#define BOARDSIZE 5
#define THREADS 4

char referenceboard[BOARDSIZE * BOARDSIZE];

int solutions = 0, attempts = 0;

typedef struct { int x; int y; int valid; } position;
position new_position(int x, int y) { position p; p.x = x; p.y = y; p.valid = 1; return p; }

/* Code below unashamedly stolen from 'somewhere' to calculate difference (delta) between 2 timeval's */
int timeval_subtract (result, x, y) struct timeval *result, *x, *y;
{
    if (x->tv_usec < y->tv_usec) {
        int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;
        y->tv_usec -= 1000000 * nsec;
        y->tv_sec += nsec;
    }
    if (x->tv_usec - y->tv_usec > 1000000) {
        int nsec = (x->tv_usec - y->tv_usec) / 1000000;
        y->tv_usec += 1000000 * nsec;
        y->tv_sec -= nsec;
    }
    result->tv_sec = x->tv_sec - y->tv_sec;
    result->tv_usec = x->tv_usec - y->tv_usec;
    return x->tv_sec < y->tv_sec;
}

void hunt(position start, int depth, const char board[BOARDSIZE*BOARDSIZE])
{
    attempts++;
    
    char my_board[BOARDSIZE * BOARDSIZE];
    memcpy(my_board, board, sizeof(my_board));
    
    my_board[(start.x * BOARDSIZE) + start.y] = 1;
    
    if (depth + 1 == BOARDSIZE * BOARDSIZE)
    {
        // Solution found
        //
        solutions++;
        printf(".");
        fflush(stdout);
        if (solutions % 10000 == 0) printf("Found %d solutions so far...\n", solutions);
        return;
    }
    
    // Determine possible moves
    //
    position possibles[8] = { 
        new_position(start.x - 1, start.y - 2), new_position(start.x - 2, start.y - 1),
        new_position(start.x + 1, start.y - 2), new_position(start.x + 2, start.y - 1),
        new_position(start.x + 1, start.y + 2), new_position(start.x + 2, start.y + 1),
        new_position(start.x - 1, start.y + 2), new_position(start.x - 2, start.y + 1),
    };
    
    int x;
    for (x = 0; x < 8; ++x)
    {
        // If position is within the bounds of the board, and not already taken, then hunt some more!
        //
        position* p = &possibles[x];
        if (p->x >= 0 && p->y >= 0 && p->x < BOARDSIZE && p->y < BOARDSIZE && board[(p->x * BOARDSIZE) + p->y] == 0)
            hunt(*p, depth + 1, my_board);
    }
}

void* thread_start_function(void* arg)
{
    int thread_num = (int)arg;
    printf("[%d]", thread_num);
    
    int skip = 0;
    
    int x, y;
    for (x = 0; x < BOARDSIZE; ++x)
        for (y = 0; y < BOARDSIZE; ++y)
        {
            if (skip == thread_num)
            {
                printf("(%d,%d)", x, y);
                hunt (new_position(x, y), 0, referenceboard);
            }
            
            skip++;
            if (skip >= THREADS) skip = 0;
        }
    
    printf("<%d>", thread_num);
    return 0;
}

int main(int argc, const char * argv[])
{
    struct timeval start;
    gettimeofday(&start, 0);
    
    // Set board to zero
    // 
    memset(referenceboard, 0, sizeof(referenceboard));
    
#if THREADS > 1
    printf("[Multithreaded (%d)]\n", THREADS);
    pthread_t threads[THREADS];
    int x;
    for (x = 0; x < THREADS; ++x)
        pthread_create(&threads[x], NULL, thread_start_function, x);
    for (x = 0; x < THREADS; ++x)
        pthread_join(threads[x], NULL);
#else
    printf("[Single threaded]\n");
    int x, y;
    for (x = 0; x < BOARDSIZE; ++x)
        for (y = 0; y < BOARDSIZE; ++y)
        {
            printf("(%d,%d)", x, y);
            hunt (new_position(x, y), 0, referenceboard);
        }
#endif
    
    struct timeval end;
    gettimeofday(&end, 0);
    
    struct timeval delta;
    timeval_subtract(&delta, &end, &start);
    
    printf("Found %d solutions in %ld.%ds (%d moves)\n", solutions, delta.tv_sec, delta.tv_usec, attempts);
    return 0;
}

Dynamite Knight's Tour in F# - Tom Wells

An Ungodly Fast Solution in F# to the Knights Tour

I would suggest that you consider coding the solution up in F#, as my friend Tom Wells has done.  His solution finds all solutions for the 5x5 board in under 5 minutes.

let boardsize = 7

// Setup board in 2d array setting all elements to true
//  ___________________
// |0,4|1,4|2,4|3,4|4,4| (x,y)
// |0,3|1,3|2,3|3,3|4,3|
// |0,2|1,2|2,2|3,2|4,2|
// |0,1|1,1|2,1|3,1|4,1|
// |0,0|1,0|2,0|3,0|4,0|
//  -------------------
//
let referenceboard = Array2D.init boardsize boardsize (fun x y -> true)

let legalmoves x y =
    // Generate every move (impossible or not)
    //
    let possibles = [(x - 1, y - 2); (x - 2, y - 1);
                     (x + 1, y - 2); (x + 2, y - 1);
                     (x + 1, y + 2); (x + 2, y + 1);
                     (x - 1, y + 2); (x - 2, y + 1);]
    
    // Prune the ones falling outside of the board
    //
    possibles |> List.filter (fun (x, y) -> x >= 0 && y >= 0 && x < boardsize && y < boardsize)

// Is a particular move still available to us? ie not already used
//
let availablemove x y (board : bool[,]) =
    board.[x,y] = true

let rec hunt startx starty (board : bool[,]) (history : List<(int*int)>) foundsolutionfunc = 
    // Mark the position we're at as being taken
    //
    board.[startx,starty] <- false

    // Check if we have a solution (ie we've covered the entire board)
    //
    if history.Length = boardsize * boardsize then
        foundsolutionfunc (history) |> ignore
    else
        // Calculate the set of available moves from this point, filtering by positions which we've already used
        //
        let availablemoves = legalmoves startx starty |> List.filter (fun (x,y) -> availablemove x y board)

        // For each available move, recurse
        //
        for (x,y) in availablemoves do
            hunt x y (Array2D.copy board) ((x,y) :: history) foundsolutionfunc

[<EntryPoint>]
let main args =
    
    let starttime = System.DateTime.Now

    let solutions = new System.Collections.Generic.List<System.Tuple<int,int>>()
    for x in seq { 0 .. Array2D.length1 referenceboard - 1 } do
        for y in seq { 0 .. Array2D.length2 referenceboard - 1 } do
            printf "(%d,%d)" x y

            hunt x y (Array2D.copy referenceboard) [(x,y)] (fun solution ->
                solutions.Add(new System.Tuple<int,int>(x,y))
                printf "."
            )    

    let endtime = System.DateTime.Now

    printfn "\nFound %d solutions (took %03f seconds)" solutions.Count (endtime - starttime).TotalSeconds
    
    printfn "Enter to quit"
    System.Console.In.ReadLine() |> ignore

    0