Simulating the Knight Sequence Tour
I am currently trying to write a simple multi-threading program using Python. However I have run on to a bug I think I am missing. I am trying to simply write a program that uses a brute force approach the problem below:
As can be seen from the image there is a chess board where the knight travels all respective squares.
My approach is simply try each possible way where each possible way is a new thread. If in the end of the thread there is no possible moves count how many squares has been visited if it is equal to 63 write solution on a simple text file...
The code is as below:
from thread import start_new_thread
import sys
i=1
coor_x = raw_input("Please enter x[0-7]: ")
coor_y = raw_input("Please enter y[0-7]: ")
coordinate = int(coor_x), int(coor_y)
def checker(coordinates, previous_moves):
possible_moves = [(coordinates[0]+1, coordinates[1]+2), (coordinates[0]+1, coordinates[1]-2),
(coordinates[0]-1, coordinates[1]+2), (coordinates[0]-1, coordinates[1]-2),
(coordinates[0]+2, coordinates[1]+1), (coordinates[0]+2, coordinates[1]-1),
(coordinates[0]-2, coordinates[1]+1), (coordinates[0]-2, coordinates[1]-1)]
to_be_removed = []
for index in possible_moves:
(index_x, index_y) = index
if index_x < 0 or index_x > 7 or index_y < 0 or index_y > 7:
to_be_removed.append(index)
for index in previous_moves:
if index in possible_moves:
to_be_removed.append(index)
if not to_be_removed:
for index in to_be_removed:
possible_moves.remove(index)
if len(possible_moves) == 0:
if not end_checker(previous_moves):
print "This solution is not correct"
else:
return possible_moves
def end_checker(previous_moves):
if len(previous_moves) == 63:
writer = open("knightstour.txt", "w")
writer.write(previous_moves)
writer.close()
return True
else:
return False
def runner(previous_moves, coordinates, i):
if not end_checker(previous_moves):
process_que = checker(coordinates, previous_moves)
for processing in process_que:
previous_moves.append(processing)
i = i+1
print "Thread number:"+str(i)
start_new_thread(runner, (previous_moves, processing, i))
else:
sys.exit()
previous_move = []
previous_move.append(coordinate)
runner(previous_move, coordinate, i)
c = raw_input("Type something to exit !")
I am open to all suggestions... My sample output is as below:
Please enter x[0-7]: 4
Please enter y[0-7]: 0
Thread number:2
Thread number:3
Thread number:4
Thread number:5Thread number:4
Thread number:5
Thread number:6Thread number:3Thread number:6Thread number:5Thread number:6
Thread number:7
Thread number:6Thread number:8
Thread number:7
Thread number:8Thread number:7
Thread number:8
Thread number:4
Thread number:5
Thread number:6Thread number:9Thread number:7Thread number:9
Thread number:10
Thread number:11
Thread number:7
Thread number:8
Thread number:9
Thread number:10
Thread number:11
Thread number:12
Thread number:5Thread number:5
Thread number:6
Thread number:7
Thread number:8
Thread number:9
Thread number:6
Thread number:7
Thread number:8
Thread number:9
If seems for some reason the number of threads are stuck at 12... Any help would be most welcomed...
Thank you
I am the intern of John Roach and he gave me this as a homework, i was unable to solve it. I used his account to ask the question. The following is my answer; I found its solution by using a heuristic known as Warnsdorff's rule. But the code I found online has an output like this:
boardsize: 5
Start position: c3
19,12,17, 6,21
2, 7,20,11,16
13,18, 1,22, 5
8, 3,24,15,10
25,14, 9, 4,23
Because of that i changed it a little bit, instead of using the standard output, i used P because P's format is tuple. I created a list of tuples named moves and return it.
def knights_tour(start, boardsize=boardsize, _debug=False):
board = {(x,y):0 for x in range(boardsize) for y in range(boardsize)}
move = 1
P = chess2index(start, boardsize)
moves.append(P)
board[P] = move
move += 1
if _debug:
print(boardstring(board, boardsize=boardsize))
while move <= len(board):
P = min(accessibility(board, P, boardsize))[1]
moves.append(P)
board[P] = move
move += 1
if _debug:
print(boardstring(board, boardsize=boardsize))
input('\n%2i next: ' % move)
return moves
Now that i had the list of moves i wrote the following program to create a GIF that animated those moves. The code is below;
import sys
import pygame
import knightmove
import os
pygame.init()
square_list = []
line_list = []
i = 0
j = 1
def make_gif():
os.system("convert -delay 40 -loop 0 Screenshots/screenshot*.png knights_tour.gif")
def get_moves(start_move):
return knightmove.knights_tour(start_move, 8)
def scratch(move):
move_x, move_y = move
x = int(move_x) * 50
y = int(move_y) * 50
line_list.append([x+25, y+25])
square_list.append([x, y])
for index in range(len(square_list)):
screen.blit(square, square_list[index])
def draw_line():
for index in range(len(line_list)-1):
pygame.draw.line(screen, black, (line_list[index]), (line_list[index+1]), 2)
def draw_dot():
return pygame.draw.circle(screen, red, (line_list[i]), 3, 0)
def screenshot():
if j <= 9:
c = "0"+str(j)
else:
c = j
pygame.image.save(screen, "/home/renko/PycharmProjects/pygame_tut1/Screenshots/screenshot"+str(c)+".png")
size = width, height = 400, 400
white = 255, 255, 255
black = 0, 0, 0, 0
red = 255, 0, 0
screen = pygame.display.set_mode(size)
square = pygame.image.load("Untitled.png")
start = raw_input("Enter the start position:")
moves = get_moves(start)
while 1:
for event in pygame.event.get():
if event.type == pygame.QUIT:
sys.exit()
screen.fill(white)
pygame.draw.line(screen, black, (0, 50), (400, 50), 3)
pygame.draw.line(screen, black, (0, 100), (400, 100), 3)
pygame.draw.line(screen, black, (0, 150), (400, 150), 3)
pygame.draw.line(screen, black, (0, 200), (400, 200), 3)
pygame.draw.line(screen, black, (0, 250), (400, 250), 3)
pygame.draw.line(screen, black, (0, 300), (400, 300), 3)
pygame.draw.line(screen, black, (0, 350), (400, 350), 3)
pygame.draw.line(screen, black, (50, 0), (50, 400), 3)
pygame.draw.line(screen, black, (100, 0), (100, 400), 3)
pygame.draw.line(screen, black, (150, 0), (150, 400), 3)
pygame.draw.line(screen, black, (200, 0), (200, 400), 3)
pygame.draw.line(screen, black, (250, 0), (250, 400), 3)
pygame.draw.line(screen, black, (300, 0), (300, 400), 3)
pygame.draw.line(screen, black, (350, 0), (350, 400), 3)
scratch(moves[i])
draw_line()
draw_dot()
screenshot()
i += 1
j += 1
pygame.display.flip()
if i == 64:
make_gif()
print "GIF was created"
break
Just so you know the imported knight move library is the library that I created using the rosettacode.org algorithm.
And yes... I was sent on a snipe hunt... :(