Programming a Knights Tour
Hey everyone. Currently, I''m working on a program for a school project where I am supposed to program the Knights Tour puzzle. If those that don''t know what Knight''s Tour is, it is a puzzle where you have a chessboard and a single Knight. The goal is to move the Knight to all 64 spots on the chessboard without touching the same spot twice. If figured out the basic algorithm for it, using accessiblity (which is basically, move the knight to the hardest to reach spots first, namely the outer most ones). The board looks something like this:
1 2 3 3 3 3 2 1
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
3 4 6 6 6 6 4 3
3 4 6 6 6 6 4 3
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
1 2 3 3 3 3 2 1
Where 1 is the hardest to reach spot and 6 is the easiest to reach spot. I place all this information into an array that is 8x8 in size.
Now, my problem is trying to think of a way for the program to determine all the possible moves from a single spot on the board and then picking the best move. Does anyone out there have any tips or ideas that I could try out? Thanks a lot, and I''m looking forward to thoughts people have on this puzzle.
It''s pretty simple. You can have an array that has all of the offsets for a knight move and loop through that array. For example, if you went with an 8x8 array, then you could have an array of the row differences and the column differences for knight moves, which would be 2, 1 or 1, 2 or -1, 2, or 1, -2, or -1, -2, etc. Since knights move in L-shapes, that should work fine.
Then all you have to do is make sure the move is on the board and not off the edge, and you just loop through the possibilities and find the moves that are on the board, and that will give you all of the legal moves for the knight.
There are other methods of move generation in a chess program, but this is the simplest.
By the way, you don''t really need to have that array of square values that you talked about. If I was doing this, I would have an array of all 0''s, and once the knight had been to that square set that square to 1. And just keep moving to squares that the knight hasn''t been to. In the case where you have already been to all of the squares that are legal moves, you could search for a square you haven''t been to and do a simple distance formula and move towards the closest square. That''s one idea I had.
Of course, you could just do a recursive search for squares you haven''t been to, but judging from your comments and the fact that you are asking how to do this, I would guess that you don''t know much about recursion. I''m not trying to make you look bad, just saying that would be the obvious solution, so you might want to look into doing a recursive search.
I''ve also heard there''s a formula for this to determine which square to move to, but I don''t remember it off hand.
Then all you have to do is make sure the move is on the board and not off the edge, and you just loop through the possibilities and find the moves that are on the board, and that will give you all of the legal moves for the knight.
There are other methods of move generation in a chess program, but this is the simplest.
By the way, you don''t really need to have that array of square values that you talked about. If I was doing this, I would have an array of all 0''s, and once the knight had been to that square set that square to 1. And just keep moving to squares that the knight hasn''t been to. In the case where you have already been to all of the squares that are legal moves, you could search for a square you haven''t been to and do a simple distance formula and move towards the closest square. That''s one idea I had.
Of course, you could just do a recursive search for squares you haven''t been to, but judging from your comments and the fact that you are asking how to do this, I would guess that you don''t know much about recursion. I''m not trying to make you look bad, just saying that would be the obvious solution, so you might want to look into doing a recursive search.
I''ve also heard there''s a formula for this to determine which square to move to, but I don''t remember it off hand.
I''d look at it as a graph problem, myself... There are probably better solutions that are specific to this problem, but the graph approach is simple and general.
Consider each square on the board to be a node in a graph. Create an edge from that node to the nodes for each square a knight could move to.
Once the graph is built, you look for a Hamiltonian cycle in the graph. There is no efficient general solution for finding a Hamiltonian cycle, but for such a small problem space, an inefficient solution would probably work just fine.
Consider each square on the board to be a node in a graph. Create an edge from that node to the nodes for each square a knight could move to.
Once the graph is built, you look for a Hamiltonian cycle in the graph. There is no efficient general solution for finding a Hamiltonian cycle, but for such a small problem space, an inefficient solution would probably work just fine.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement