April 2nd, 2007, 04:20 AM
This installment of the (semi) Weekly Programming Challenge has the participant, you, solving the old problem of the Knight's Tour (http://en.wikipedia.org/wiki/Knight's_tour):
The Knight's Tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once.
This challenge will assume a standard chess board size of 8x8. As usual, any language allowed, but no libchess please! ;)
points++ for solving the problem given a board of size nxn.
April 2nd, 2007, 08:38 AM
This is my first crack at the problem, I made an algorithm that can solve the tour for a board size nxn using back-tracing.
def find_tour(size, start_x, start_y):
moves = [[1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1], [-2, 1], [-1, 2]]
board = 
trace = 
n_move = 1
for i in range(0, size):
board.append([-1] * size)
board = 0
cur_x = start_x
cur_y = start_y
while n_move < size * size:
p = 
for move in moves:
move_x = cur_x + move
move_y = cur_y + move
if (move_x >= 0) and (move_y >= 0) and (move_x < size) and (move_y < size) and (board[move_x][move_y] == -1):
while not len(p):
cur_x, cur_y, p = trace.pop()
board[cur_x][cur_y] = -1
n_move -= 1;
cur_x, cur_y = p.pop()
board[cur_x][cur_y] = n_move
trace.append((cur_x, cur_y, p))
n_move += 1
b = find_tour(8, 0, 0)
This is pretty slow but it works so far. I plan to create a GUI to better visualize the tour tomorrow.
Here is the output for 5x5:
jmccaffrey@windy:~/mywork/knights-tour$ time ./pytour.py
[[0, 3, 8, 17, 20], [9, 16, 19, 2, 7], [4, 1, 12, 21, 18], [15, 10, 23, 6, 13], [24, 5, 14, 11, 22]]
April 2nd, 2007, 03:24 PM
i once made one that solved an nxn board using backtracing for one of my classes here at NJIT. If i have time too later today maybe I'll see if my memory still lets me throw one together!
April 4th, 2007, 01:10 AM
This installment of the (semi) Weekly Programming ChallengePoint of order, are there now two challenges per week? Or should it be semi-monthly?
April 4th, 2007, 01:26 AM
"semi", because they haven't exactly been happening on a weekly basis (if you haven't noticed). I sometimes don't find time or even an idea for a challenge to post every week, which is why some weeks don't have one. I will work on more regularly posting new challenges, at least weekly.
Certainly, more frequent challenges could be posted if the demand is high. :)
April 4th, 2007, 03:07 AM
I been down for the last month with the flu that's been going around, so didn't know if the timing had changed or not. Thanks for the effort put forth coming up with the challenges.
Powered by vBulletin® Version 4.2.2 Copyright © 2016 vBulletin Solutions, Inc. All rights reserved.