Simulating the Knight Sequence Tour

Question

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

Answer 1

Your so-called Quest of the Knights Who Say Ni problem, while a clever rephrasing for asking a Python question, is more widely known as the Knights Tour mathematical problem. Given that and the fact you're a math teacher, I suspect your question's likely a fool's errand (aka snipe hunt) and that you're fully aware of the following fact:

According to a section of Wikipedia's article on the Knights Tour problem:

5.1 Brute force algorithms

A brute-force search for a knight's tour is impractical on all but the
smallest boards; for example, on an 8x8 board there are approximately
4x10⁵¹ possible move sequences^∗, and it is well beyond the capacity
of modern computers (or networks of computers) to perform operations
on such a large set.

^∗ Exactly 3,926,356,053,343,005,839,641,342,729,308,535,057,127,083,875,101,072 of them according to a footnote link.