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:

376dc6dd28649dd49ee987fbaf913b75

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

Edited 2 Years Ago by johnroach1985

First, use the threading module instead of thread, so start a thread with

t = threading.Thread(target = runner, args = (list(previous_moves), processing, i))
t.start()

I wrote list(previous_moves) because this creates a clone of the list. I don't think all the threads can share the same list object, or may be I'm missing something.

What is the point of using threads to solve this problem ? There is a risk that your program encounters a limit on the maximal number of possible threads.

Edited 2 Years Ago by Gribouillis

This article has been dead for over six months. Start a new discussion instead.