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:

![How the knight must move...](http://i.stack.imgur.com/u2VOw.gif)

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: Your so-called _Quest of the[Knights Who Say
Ni_](https://en.wikipedia.org/wiki/Knights_who_say_Ni) problem, while a clever
rephrasing for asking a Python question, is more widely known as the [_Knights
Tour_](https://en.wikipedia.org/wiki/Knights_tour
"https://en.wikipedia.org/wiki/Knights_tour") mathematical problem. Given that
and the fact you're a [math
teacher](http://www.daniweb.com/members/5504/johnroach1985), I suspect your
question's likely a fool's errand (aka [snipe
hunt](https://en.wikipedia.org/wiki/Snipe_hunt)) and that you're fully aware
of the following fact:

According to a
[section](https://en.wikipedia.org/wiki/Knights_tour#Brute_force_algorithms
"click to go directly to that section of article") 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  
>  4x1051 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](http://www.josiahland.com/archives/781 "Enumerating
the Kight’s Tour - http://www.josiahland.com/archives/781") link.

