The Knight's Tour
Hi everyone. Im stuck in a problem, I dont even know if this is for begginers or not. Well, my actual problem is, im developing the famous Knight Tour, I dont want to draw the chessboard, I just need to list all the possibles moves. I wonder, how can I start this?. I really have no idea. What will be my first step to solve this puzzle using an algorithm?. I hope someone can help me with this, Im trying to solve this a long time ago, my my knowledge of java is not too good.
[ May 05, 2005: Message edited by: Manuel Diaz ]
Leave a comment...
- 16 Comments
- http://www.google.com/search?q=knight%27s+tour+algorithm#1; Sun, 13 Jul 2008 13:36:00 GMT
- I already search like a crazy on google. They dont show me an algorithm. Only the explanation of the problem. I need how to use an algorithm in my java code to work with it.#2; Sun, 13 Jul 2008 13:37:00 GMT
=== Original Words ===
The first step is to write out the a description of the algorithm in pseudocde. Of course, you should keep in mind the different tools you have handy in Java (like for loops and if statements), but don't worry about the exact syntax. Instead, concentrate on the content and the steps needed to solve the problem. Perhaps you should get a physical chess board, or draw one, and think how you would go about solving the problem by hand. Write the steps you use in English before trying to translate them into code.
It might also help to decide what information you need to store in order to solve this problem. For example, you might need an 8x8 grid to store the positions already moved to -- sounds like an array might be helpful here. Also figure out what inputs are needed for the algorithm to start and what the output should be.
Once you write out some pseudocode, post it here and we can help you from there.
[ May 05, 2005: Message edited by: Layne Lund ]#3; Sun, 13 Jul 2008 13:38:00 GMT
- Couldn't agree with Layne more. Forget about Java (and computers) for a minute, and think about how you personally would solve this problem, given a chessboard and a single knight. Use pencil and paper to write down your algorithm.#4; Sun, 13 Jul 2008 13:39:00 GMT
- When working this by hand, you will probably find it easier to work with a smaller board, say 5x5.
Layne#5; Sun, 13 Jul 2008 13:40:00 GMT
- The second link on Steve's google link has a few very good algorithms for solving the problem. This one would probably work for you.
"Warnsdorff (1823) proposed an algorithm that finds a path without any backtracking by computing ratings for ``successor'' steps at each position. Here, successors of a position are those squares that have not yet been visited and can be reached by a single move from the given position. The rating is highest for the successor whose number of successors is least. In this way, squares tending to be isolated are visited first and therefore prevented from being isolated (Roth). The time needed for this algorithm grows roughly linearly with the number of squares of the chessboard, but unfortunately computer implementation show that this algorithm runs into blind alleys for chessboards bigger than $76\times 76$, despite the fact that it works well on smaller boards (Roth)."#6; Sun, 13 Jul 2008 13:41:00 GMT
- here's a recent thread at Sun's forums.
see reply #8 for a working GUI version - it might give you some ideas
on developing your own algorithm
[ May 07, 2005: Message edited by: Michael Dunn ]#7; Sun, 13 Jul 2008 13:42:00 GMT
- Actually, I know how the Knight Tour works!, but I dont know how to take this into Java code, I did all this steps on paper, i know how to move my knight, but, in code, is totally different. I wonder,how do I start my code to find the possibles moves?. I dont need to draw anything, just the algorithm to random the steps!.
THANKS!#8; Sun, 13 Jul 2008 13:43:00 GMT
- OK, let's begin. How can I declare and array?. For example I want to se an array for my chessboard, and another for my moves. So in other words, how do I write this in java code?
board: array [0..64] of integer;
moves: array [0..64] of integer;
I think I should start from here.#9; Sun, 13 Jul 2008 13:44:00 GMT
=== Original Words ===
The problem is that you haven't shown us what you know already. It's difficult for us to know where to start helping you unless you give us enough information to understand what problems you've encountered. In order to help us help you, you should post what you have written down. What are the steps that you wrote on paper? Once you post that, we can more easily help you translate it into Java.
Layne#10; Sun, 13 Jul 2008 13:45:00 GMT
=== Original Words ===
You can learn about arrays by reading the this section in the Java Tutorial. You should bookmark the second link because it has some great resources for learning all about the Java programming language.
I hope this helps.
Layne#11; Sun, 13 Jul 2008 13:46:00 GMT
- Follow Layne's advice! He's trying to help you, but you aren't making it easy. Post the psuedo code you've come up with here and we can help you translate it into Java.
If you're going to be asking questions like how do I create an Array, I'd suggest you spend some time going through some tutorials or getting a book. For questions like this one and others such as "how do I make a for loop" a good reference book will be much quicker than posting it here and waiting for a reply.#12; Sun, 13 Jul 2008 13:47:00 GMT
- Ok, here is what I have so far. I already manage to get the array list.
I have the other part in C code. But I dont know how to translate it to Java. You can find the rest in the topic ("Convert into Java Code").#13; Sun, 13 Jul 2008 13:48:00 GMT
- >Actually, I know how the Knight Tour works!, but I dont know how to take this into Java code,
The link I gave had a Knights Tour solution in java, with GUI.
You just clicked on a square, the algorithm would determine a solution from
that square, then the 'Knight' moved around the board (blacking out squares already visited), until all squares had been visited.
Ah well, "you can lead a horse to water..."#14; Sun, 13 Jul 2008 13:49:00 GMT
=== Original Words ===
Ah well, "you can lead a horse to water..."[/QB]
I agree. It doesn't make sense. This thread starts off with Manuel not knowing how the algorithm works, but he quickly develops a fully functional C program. In a parallel thread, he converts this C program into Pascal, which he says works fine.
With the amount of effort that he took to (a) learn the algorithm, (b) develop a solution in C, and then (c) port that solution to Pascal, it is weird that he is really resisting even showing us some attempts at Java code, or even telling us what errors that he is getting.
Henry#15; Sun, 13 Jul 2008 13:50:00 GMT
- Hi ALL,
I don't want to be mean...but this is a double post, and maybe this Manuel is trying to have someone else do his job...I said maybe because he claims he wrote some Java code but he refuses to post it...but he has a full working C code which he wants to translate in Java...I wonder if he wrote the C code or not!
The other post is here
Giovanni#16; Sun, 13 Jul 2008 13:51:00 GMT