File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

In Dire Need of Data Structure Advice

 
Joe Kain
Greenhorn
Posts: 3
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 47222
52
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Haven't been through the whole of your posts, but an array is implicitly an object in its own right.
 
Joe Kain
Greenhorn
Posts: 3
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 47222
52
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 47222
52
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think the change to Integer[] is harmless, but unnecessary; it would work with int[] arrays.
 
Piet Verdriet
Ranch Hand
Posts: 266
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Consider Paul's rocket mass heater.
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic