jQuery in Action, 2nd edition*
The moose likes Beginning Java and the fly likes In Dire Need of Data Structure Advice Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "In Dire Need of Data Structure Advice" Watch "In Dire Need of Data Structure Advice" New topic
Author

In Dire Need of Data Structure Advice

Joe Kain
Greenhorn

Joined: Nov 28, 2008
Posts: 3
Ok, so I am beginning to think that I'm hopeless with data structures.

I am writing a knight's tour program that begins in the top left of an mxn board and tries to travel to each square by making moves that are legal for knights in chess. The process is not my problem, its the data structures that are killing me.

I would like to hold all the legal moves that can be made from a square in a data object. Each data object would hold and row and column position, so a 1x2 array. My problem has been in creating and adding to a list of arrays. I'll post a couple key lines of my code then the all of it at the bottom.
I CAN'T TELL YOU HOW MUCH I WOULD APPRECIATE ANY HELP!
Whether its with this issue or just critique in general of my program.




public List getMoves(int i, int j, int rows, int cols, boolean[][] isTaken)
{
List<int[]> moves = new ArrayList< int[] >();

if (this.isValid(i-2, j+1, rows, cols, isTaken))
moves.add({i-2, j-1});
......


List<int[]> possMoves = this.getMoves(currMove[0], currMove[1], rows, cols, isTaken);
if (possMoves.size() == 0)
moreMoves = false;
else
{
int randomIndex = generator.nextInt( possMoves.size() );
currMove = possMoves.get(randomIndex);
moveCount++;
}
}




....


HERE IS ALL OF THE CODE



// Knights Tour app

import java.io.*;
import java.util.*;

public class kTour
{
public boolean isValid(int i, int j, int rows, int cols, boolean[][] isTaken)
{
if (i < 0 || j < 0 || i >= rows || j >= cols || isTaken[i][j])
return false;
else
return true;
}


public List getMoves(int i, int j, int rows, int cols, boolean[][] isTaken)
{
List<int[]> moves = new ArrayList< int[] >();

if (this.isValid(i-2, j+1, rows, cols, isTaken))
moves.add({i-2, j-1});
if (this.isValid(i-1, j+2, rows, cols, isTaken))
moves.add({i-2, j-1});
if (this.isValid(i+1, j+2, rows, cols, isTaken))
moves.add({i-2, j-1});
if (this.isValid(i+2, j+1, rows, cols, isTaken))
moves.add({i-2, j-1});
if (this.isValid(i+2, j-1, rows, cols, isTaken))
moves.add({i-2, j-1});
if (this.isValid(i+1, j-2, rows, cols, isTaken))
moves.add({i-2, j-1});
if (this.isValid(i-1, j-2, rows, cols, isTaken))
moves.add({i-2, j-1});
if (this.isValid(i-2, j-1, rows, cols, isTaken))
moves.add({i-2, j-1});

return moves;

}


public static void main(String argv[])
{
int rows = Integer.parseInt(argv[0]);
int cols = Integer.parseInt(argv[1]);
int trys = Integer.parseInt(argv[2]);

int moveCount;
boolean moreMoves;
boolean[][] isTaken = new boolean[rows][cols];

int[] startPos = {0,0}
int[] currMove = startPos;

for ( int count = 0; count < trys; ++count)
{
moreMoves = true;
moveCount = 0;
for(int i = 0; i < rows; ++i)
{
for(int j = 0; j < cols; ++j)
isTaken[i][j] = false;
}

while(moreMoves)
{
isTaken[currMove[0]][currMove[1]] = true;
List<int[]> possMoves = this.getMoves(currMove[0], currMove[1], rows, cols, isTaken);
if (possMoves.size() == 0)
moreMoves = false;
else
{
int randomIndex = generator.nextInt( possMoves.size() );
currMove = possMoves.get(randomIndex);
moveCount++;
}
}

if (moveCount == rows*cols)
System.out.println("Victory");
else
System.out.println("Failure");

}
}
}
Joe Kain
Greenhorn

Joined: Nov 28, 2008
Posts: 3
I know now that an arraylist must hold objects. I am still confused then how to handle this situation. I have an unknown amount of 1x2 arrays that I need to somehow store.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39408
    
  28
Haven't been through the whole of your posts, but an array is implicitly an object in its own right.
Joe Kain
Greenhorn

Joined: Nov 28, 2008
Posts: 3
Ok, I went back in and change my list types to <Integer[]>

It compiles but when I try to run it I get this error

ption in thread "main" java.lang.NoClassDefFoundError: 4
Caused by: java.lang.ClassNotFoundException: 4
at java.net.URLClassLoader$1.run(URLClassLoader.java:200)
at java.security.AccessController.doPrivileged(Native Method)
at java.net.URLClassLoader.findClass(URLClassLoader.java:188)
at java.lang.ClassLoader.loadClass(ClassLoader.java:306)
at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:276)
at java.lang.ClassLoader.loadClass(ClassLoader.java:251)
at java.lang.ClassLoader.loadClassInternal(ClassLoader.java:319)


here is my source...







[edit]Add code tags. CR[/edit]
[ November 28, 2008: Message edited by: Campbell Ritchie ]
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39408
    
  28
Please use the code button; I have edited your last post so you can see how much better it looks.

You can simplify your isValid method; look in the code conventions �10.5.2.
You want to add something like this to the main methodand the remainder of the method goes in the "else." That way you get a warning if the user doesn't enter the right command-line arguments, rather than an exception.

I ran your app and didn't get any Exception about class not found. Are you writing

java kTour 1 2 3

at the command line? Did you put the 4 in first? 4 is not an approved name for a Java class in the first place; names are not allowed to start with a number.
[ November 28, 2008: Message edited by: Campbell Ritchie ]
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39408
    
  28
I think the change to Integer[] is harmless, but unnecessary; it would work with int[] arrays.
Piet Verdriet
Ranch Hand

Joined: Feb 25, 2006
Posts: 266
Here's a applet of it, including the source:
http://www.iruimte.nl/knightstour/
I'm not saying you should blindly copy it, but perhaps you'd like to look at the code to see how it's written.

Good luck.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: In Dire Need of Data Structure Advice