Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, 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 */
}

more than 5 years ago

Submissions

JoZZ hasn't submitted any stories.

Journals

JoZZ has no journal entries.

Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>