×

Announcing: Slashdot Deals - Explore geek apps, games, gadgets and more. (what is this?)

Thank you!

We are sorry to see you leave - Beta is different and we value the time you took to try it out. Before you decide to go, please take a look at some value-adds for Beta and learn more about it. Thank you for reading Slashdot, and for making the site better!

Comments

top

Solving the Knight's Tour Puzzle In 60 Lines of Python

JoZZ 44 lines in commented and whitespaced C. (311 comments)

Timed with Debian on EEE 901 in HT mode (1.6 GHz Atom)

real    0m0.726s
user    0m0.724s
sys     0m0.004s

K&R (more or less), with tab-space=8 inside 79 cols. But commenting as original pyton (end of line commenting).

-----
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int startx = 0, starty=0, size=0; /* The size of the thing, is set in main */
/* How knights walk, changing this changes the time outcome :) */
int jumps[][2] = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};

int walk(int *board, const int x, const int y, const int step)
{
    board[x*size+y] = step; /* set our stamp here */
    if (step == size*size)
        return 1; /* Were done */
    for (int i=0;i<8;++i) { /* for each type of jump */
        int xx = x + jumps[i][0], yy = y + jumps[i][1]; /* set new position */
        if (xx < 0 || yy < 0 || xx >= size || yy >= size || board[xx*size+yy])
            continue; /* outch. been there or outside*/
        if (walk(board, xx, yy, step + 1))
            return 1; /* were finished, just return*/
    }
    board[x*size+y] = 0; /* we could not walk anywhere, reset and ... */
    return 0; /* move back indicating failure */
}

void draw(const int *board, int x, int y) /* Draw the board */
{
    for (int i=0;i<size*size;++i) {
        printf(" %4d", board[i]);
        if (((i+1) % size) == 0)
            printf("\n");
    }
}

int main(int argc, char *argv[])
{
    if (argc != 2 || ((size = atoi(argv[1])) == 0)) /* get size */
        return printf("use: %s <size>\n", argv[0]) + 1;
    printf("Board of size %dx%d\n", size, size);
    unsigned int board[size*size]; /* Alloc space for board */
    memset(board, 0, sizeof(int) * size * size); /* clear space */
    walk(board, startx, starty, 1); /* Start at defined start position */
    draw(board, -1, -1); /* Draw board that is done */
    return 0; /* Yay, done */
}

about 6 years ago

Submissions

JoZZ hasn't submitted any stories.

Journals

JoZZ has no journal entries.

Slashdot Login

Need an Account?

Forgot your password?