#1




Knights tour problem (using brute force)Hi,
I have been trying to write a program that solves the knights tour problem using brute force, as aposed to the huristic method used in the other posts i have read on the problem. (You probably know of the basic problem, move a knight around a chess board without visiting the same square twice. Other posts that explain it better than i can!) Anyway, down to my specific problem, i have written a peice of code that starts the knight in the top left corner of the board and then randomly picks a moves to make untill the knight gets stuck or all 64 moves have been made and then simply prints how many moves have been attchived. (I intend to modify the program later to loop forever until all 64 moves are made.) However when i compile and run the program somtimes it works just fine and other times it seems to freeze as though it has got stuck in an infinite loop. I will post the code, but this is my first post so i hope it all works correctly. Please forgive all the 'if' statments, i was worried that my boolean algebra may have been at fault. CPP / C++ / C Code:


#2




Re: Knights tour problem (using brute force)That is an interesting problem. I didn't look too deeply at your code as I have a suggestion as to how I would solve it. I would represent the path of a knight as a 2D array of integers and a move number. Initially, all of the array elements will be set to 1. Then, as the knight moves to a space, the corresponding element will be changed to the move number. This will make it very easy to see the path of the knight.
Then, I would use recursion to move the knight at every possible combination until it completes the entire board. I have completed the task and would like to share some of it with you: CPP / C++ / C Code:
I'll let you think about how you would implement this. Later, I will show the rest of the code to help with any uncertain areas. I will say that with an 8x8 board, it runs for a LONG TIME. If you chose a 5x5 board, it finishes much sooner. 
#3




Re: Knights tour problem (using brute force)Quote:
You need to have some way of finding whether it is "stuck" while it is in the FindNextMove function. Note that it is possible to get into a corner (or maybe other position) where there is no next move. For example, from a starting position in the upper left corner, the following sequence of moves (as defined in your arrays) will get the Knight stuck: Code:
After these 11 moves from the original postion, the board looks like: Code:
Now the Knight is in the lower left corner with no way out. (Therefore your FindNextMove() function is, indeed, in an infinite loop.) So: the loop inside FindNextMove() should, somehow, know when to quit when it has tried all possible moves. Then FindNextMove() can return a negative value if it has tried them all without finding a valid move, and the main program will know it is stuck without calling another function. Maybe something like: CPP / C++ / C Code:
[edit]Instead of changing it the way that I showed, maybe you could just put your Stuck() test before you call FindNextMove()I haven't tested it, but this could, maybe, solve it with no significant changes to your code.[[/edit] Hmmm. I wonder if there are fewer than 11 moves that get you stuck??? I mean, I just doodled around until I came up with those (and I'm not a chess player). If it hasn't been done already, maybe someone could do an "inverse knight's tour" search to find the fewest moves that trap the knight. Just a thought. Regards, Dave Footnote: Since you have eight possible moves (and eight values in the Vertical and Horizontal arrays), you should let the move number be rand()%8, not rand()%7 Last edited by davekw7x : 18Apr2008 at 14:58.

#4




Re: Knights tour problem (using brute force)Thanks Dave for looking into the problem and i have made use of your suggestions, it seems that the silly mistake of using ran() % 7 and not rand() % 8 was a big part of the problem. Anyway, it may take hours to find out if it works!
Im up to just over 13millilon attempts at finding a route so far. Fakepoo's program looks like it would solve the problem faster, because at the moment my program doesn't garrentee every possible combination of moves is made, however your program looks to be beyond my capabilities. Anyway, thanks again. 
#5




Re: Knights tour problem (using brute force)Here is all of the code for the solution that I came up with:
CPP / C++ / C Code:
CPP / C++ / C Code:

#6




Re: Knights tour problem (using brute force)Quote:
For the Original Poster: I think the best part of trying the "brute force" method is that you may be able to get a feel for the actual complexity of the problem (computational complexity from a BigO point of view, not from a programming difficulty point of view.) Take the basic BigO complexity of the fundamental task, and add the uncertainty and nonorganized approach of trying random sequences of random moves, and I would say that you would have to be lucky, indeed, to find a solution before our sun goes nova (or before your computer expires or before your grandchildren have grandchildren, whichever comes first). On the other hand using pseudorandom number sequences (some form of Monte Carlo method) for certain classes of problems has been used extensively and successfully in lots of disciplines where the problem is not particularly amenable to mathematical or physical analysis. Regards, Dave 
«
Previous Thread

Next Thread
»
Thread Tools  Search this Thread 
Rate This Thread  



Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Problem with getting multiple solutions from Knight's Tour...  amarufox  C++ Forum  3  22Apr2006 13:08 
Knight's Tour  now with heuristics  earachefl  C++ Forum  0  09Apr2006 10:19 
Knights Tour  Reloaded .  kobi_hikri  C Programming Language  12  03Oct2005 12:15 
Network Sites: GIDNetwork · GIDApp · GIDBlog · Learning Journal by J de Silva, The
All times are GMT 6. The time now is 23:08.