Big Moose Saloon
 Search | Java FAQ | Recent Topics Register / Login

# The Knight's Tour

Manuel Diaz
Ranch Hand

Joined: Apr 22, 2005
Posts: 79
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.

THANKS!.
[ May 05, 2005: Message edited by: Manuel Diaz ]

Note: I love programming.
Steve Morrow
Ranch Hand

Joined: May 22, 2003
Posts: 657

Manuel Diaz
Ranch Hand

Joined: Apr 22, 2005
Posts: 79
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.
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Originally posted by Manuel Diaz:
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.

THANKS!.

[ May 05, 2005: Message edited by: Manuel Diaz ]

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.

Layne
[ May 05, 2005: Message edited by: Layne Lund ]

Steve Morrow
Ranch Hand

Joined: May 22, 2003
Posts: 657

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.
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
When working this by hand, you will probably find it easier to work with a smaller board, say 5x5.

Layne
Steven Bell
Ranch Hand

Joined: Dec 29, 2004
Posts: 1071
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)."
Michael Dunn
Ranch Hand

Joined: Jun 09, 2003
Posts: 4632
here's a recent thread at Sun's forums.
see reply #8 for a working GUI version - it might give you some ideas

[ May 07, 2005: Message edited by: Michael Dunn ]
Manuel Diaz
Ranch Hand

Joined: Apr 22, 2005
Posts: 79
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!
Manuel Diaz
Ranch Hand

Joined: Apr 22, 2005
Posts: 79
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.
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Originally posted by Manuel Diaz:
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!

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
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Originally posted by Manuel Diaz:
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.

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
Hentay Duke
Ranch Hand

Joined: Oct 27, 2004
Posts: 198

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.
Manuel Diaz
Ranch Hand

Joined: Apr 22, 2005
Posts: 79
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").
Michael Dunn
Ranch Hand

Joined: Jun 09, 2003
Posts: 4632
>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...."
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 17629

33

Originally posted by Michael Dunn:
[QB
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

Giovanni De Stefano
Ranch Hand

Joined: Aug 17, 2004
Posts: 144
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

SCJP 1.4

It is sorta covered in the JavaRanch Style Guide.

subject: The Knight's Tour