Beta
×

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!

top

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

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 */
}

# Slashdot: News for Nerds

"Facts are stupid things." -- President Ronald Reagan (a blooper from his speeach at the '88 GOP convention)