Java+VB developers project

[CAPITAL LETTERS]

hey i am taking a java programming class and we have a developers project to do

our task:
a simple chess board with a knight.
what we have to do is programm the knight to move on all squares/tiles of the board without going on the same square/tile.

now this can be done because i have seen some of the ones the last years class did
some of the methods they used were things like:

-brute force
trying every possible algorithym until prooved successful
the problem with this is that it took ages and had a total of ~3.5 million failed tries before it had found a successful path.

-or valued squares
where the tiles on the chess board had a certain value depending on the avaliable moves once on that tile. this method prooved great only it needed a certain AI for it to know what tile had the best value on the next moves.
this method got it solved it in 2.5 seconds.

as i know it can be done in java, and i am confident in visual basic, i would like to see if anyone can help me out with making this happen in visual basic. if not, try it out in java

happy coding

 

[FordGT90Concept]

The first thing you need is a chess board (an array 8x8). I would make it an array of signed bytes where -1 is a tile that hasn't been touched and 0-63 indicating moves (where the knight was).

Knights move 2 in one direction and 1 in another.

Make a method which returns an array 8 long. Every value in the array represents one of the possible places the peice could move. If the value is true, that means the peice can go there. If it is false, it can't. The conditions for returning a false value are as follows:
1) this location resides outside of the array
2) this location has already been hit (value != -1)

Loop through that method until all the values in the array are false (no legal moves). It may, or may not hit them all.

A random seed may have to be used on the order in which the possible value is chosen in order to increase the liklihood that it would eventually hit all 64 tiles (assuming it doesn't the first time).



I won't code this unless you've already gotten credit for it in the class (not gonna do the work for you ).

 

[daragez]

great project!...nice share!..

 

[FordGT90Concept]

Attempts: 858,183
Duration: 39.0312500 seconds

Mind you, it runs on a random number generator so it is possible that it succeeds on the first attempt.

Second run...
Attempts: 625,637
Duration: 28.7343750 seconds

Third run...
Attempts: 33,420
Duration: 1.5781250 seconds

Fourth run...
Attempts: 132,226
Duration: 6.125 seconds

Fifth run...
Attempts: 50,836
Duration: 2.453125 seconds
Solution:

+----+----+----+----+----+----+----+----+
|  0 | 21 | 62 | 35 |  2 | 33 | 24 |  9 |
+----+----+----+----+----+----+----+----+
| 63 | 54 |  1 | 22 |  7 | 10 |  3 | 32 |
+----+----+----+----+----+----+----+----+
| 20 | 61 | 36 | 55 | 34 | 23 |  8 | 25 |
+----+----+----+----+----+----+----+----+
| 53 | 56 | 19 |  6 | 11 | 26 | 31 |  4 |
+----+----+----+----+----+----+----+----+
| 60 | 37 | 58 | 27 | 18 |  5 | 12 | 47 |
+----+----+----+----+----+----+----+----+
| 57 | 52 | 41 | 38 | 13 | 46 | 17 | 30 |
+----+----+----+----+----+----+----+----+
| 40 | 59 | 50 | 43 | 28 | 15 | 48 | 45 |
+----+----+----+----+----+----+----+----+
| 51 | 42 | 39 | 14 | 49 | 44 | 29 | 16 |
+----+----+----+----+----+----+----+----+

Sixth run...
Attempts: 956,781
Duration: 45.03125 seconds
Solution:

+----+----+----+----+----+----+----+----+
|  0 | 57 |  8 | 53 | 10 | 55 | 40 | 43 |
+----+----+----+----+----+----+----+----+
| 37 | 52 |  1 | 56 | 39 | 42 | 11 | 18 |
+----+----+----+----+----+----+----+----+
| 58 |  7 | 38 |  9 | 54 | 19 | 44 | 41 |
+----+----+----+----+----+----+----+----+
| 51 | 36 |  5 |  2 | 29 | 12 | 17 | 20 |
+----+----+----+----+----+----+----+----+
|  6 | 59 | 50 | 13 |  4 | 27 | 30 | 45 |
+----+----+----+----+----+----+----+----+
| 35 | 62 |  3 | 28 | 47 | 16 | 21 | 24 |
+----+----+----+----+----+----+----+----+
| 60 | 49 | 14 | 33 | 26 | 23 | 46 | 31 |
+----+----+----+----+----+----+----+----+
| 63 | 34 | 61 | 48 | 15 | 32 | 25 | 22 |
+----+----+----+----+----+----+----+----+

I think that's enough for now.


My code allows to change the start location to anywhere, resize the chess board, and stop at x number of moves.

It averages 21247 attempts per second on my Core i7 920. It is only a single thread app right now but I could make it run on multiple threads and output the solution that is found first.

 

[FordGT90Concept]

I multithreaded it. The fastest result so far is:

Attempts: 3,181
Duration: 0.2031250 seconds
Seed: 110152139
Solution:

+----+----+----+----+----+----+----+----+
|  0 | 63 | 52 | 27 |  2 | 35 | 50 | 29 |
+----+----+----+----+----+----+----+----+
| 53 | 26 |  1 | 36 | 51 | 28 | 33 |  4 |
+----+----+----+----+----+----+----+----+
| 62 | 37 | 24 | 21 | 34 |  3 | 30 | 49 |
+----+----+----+----+----+----+----+----+
| 25 | 54 | 15 | 38 | 23 | 20 |  5 | 32 |
+----+----+----+----+----+----+----+----+
| 42 | 61 | 22 |  7 | 14 | 31 | 48 | 19 |
+----+----+----+----+----+----+----+----+
| 55 | 58 | 43 | 16 | 39 |  6 | 13 | 10 |
+----+----+----+----+----+----+----+----+
| 60 | 41 | 56 | 45 |  8 | 11 | 18 | 47 |
+----+----+----+----+----+----+----+----+
| 57 | 44 | 59 | 40 | 17 | 46 |  9 | 12 |
+----+----+----+----+----+----+----+----+

It is coded in C#.NET (could relatively easily be converted to VB.NET, performance about the same).

Here's the class diagram of the code:
http://img.techpowerup.org/090507/ClassDiagram1.png

I won't paste/upload any code until I know you got credit for the assignment.

 

[CAPITAL LETTERS]

hey thanks heaps this has given me a great idea how to do it.

now all i need to do is......to do it lol

we are meant to hand it in in java but my lecturer said if that i can do it in VB he'll pass me strait away. im guessing this means that it'll be harder in VB

 

[FordGT90Concept]

I would use VB.NET over Java any day. If you haven't done any VB.NET coding before though, you best stick to Java unless the due date is rather distant.


It took me an hour and a hour and a half to code the single threaded version, half an hour to make it display the results in the grid, and an hour and a half to multithread it. It took about three and a half hours total.


Of course, using my method, it could take several minutes to find a result or it might take mere seconds. It depends how good of a random seed it is working on. XD

 

[Oliver_FF]

If you don't want to brute force it as per FordGT's proposal, you can add in some logic to test for un-reachable squares.

eg- if, after making a move, an untouched square is surrounded by touched squares 2 levels deep, the previous move was invalid. Suppose you get an un-reachable square after the 10th move (54 moves left to make) then you've immediately ruled out 432 moves. You need to be clever about it though, you don't want to waste time checking for impossible squares when they are clearly possible

I suppose it all depends on how competent you are at programming and how much computer algorithms interest you

 

[FordGT90Concept]

Hmm, sounds like a node system. That would be great for systematically finding every possible solution given a start point. I doubt it would be very fast but it would be far more reliable than my "throw spaghetti at the wall and see if it sticks" solution. XD


You'd think there would be some equation/pattern that could solve it pretty much instantly but I'm no mathematical expert.

 

[Sonido]

Hmm, sounds like a node system. That would be great for systematically finding every possible solution given a start point. I doubt it would be very fast but it would be far more reliable than my "throw spaghetti at the wall and see if it sticks" solution. XD


You'd think there would be some equation/pattern that could solve it pretty much instantly but I'm no mathematical expert.

The equation would actually be quite long. The permutations possible are in the range of "A LOT". So... Yea...

Unless, are you are speaking of a static pattern? A pattern that doesn't change?

 

[FordGT90Concept]

Yeah, a static pattern. Figure out one pattern that will hit like 32 of the tiles, then another to hit another 16 or so, one that will hit another 8, and another that will hit the final 8. That way, you run those 4 algorithms in succession and the puzzle is done.

I admit, that route is kind of boring because you always know the outcome. It is interesting to see how such random paths work with my algorithm.


Edit: The fastest way to solve it would be to take one of the solutions I pasted and procedurally produce it every time. It could be somewhat entertaining to make a class which describes the eight movements he knight can make and then list the 64 moves necessary to complete the puzzle. For example:

Knight myknight = new Knight(0, 0);
myknight.MoveRightDown();
myknight.MoveRightUp();
myknight.MoveDownRight();
// etc.

Where the first direction implies two squares and the second direction implies one square. I'm not sure that would meet your class's requirements though. It would "solve" in the thousandths or hundredths of a second.

Edit: I took the liberty to add this functionality to my code. Here is a result:

+----+----+----+----+----+----+----+----+
|  0 | 57 | 40 | 59 | 24 | 49 | 42 | 47 |
+----+----+----+----+----+----+----+----+
| 39 | 60 |  1 | 52 | 41 | 46 | 25 | 50 |
+----+----+----+----+----+----+----+----+
| 56 | 53 | 58 | 23 | 12 | 51 | 48 | 43 |
+----+----+----+----+----+----+----+----+
| 61 | 38 | 55 |  2 | 45 | 22 | 11 | 26 |
+----+----+----+----+----+----+----+----+
| 54 |  3 | 34 | 13 | 10 | 27 | 44 | 21 |
+----+----+----+----+----+----+----+----+
| 37 | 62 |  5 | 32 | 15 | 18 |  9 | 28 |
+----+----+----+----+----+----+----+----+
|  4 | 33 | 14 | 35 | 30 |  7 | 20 | 17 |
+----+----+----+----+----+----+----+----+
| 63 | 36 | 31 |  6 | 19 | 16 | 29 |  8 |
+----+----+----+----+----+----+----+----+

The move list...

RightDown
DownRight
LeftDown
DownLeft
RightUp
DownRight
RightUp
RightDown
UpLeft
LeftUp
RightUp
LeftUp
DownLeft
DownLeft
RightUp
DownRight
RightUp
LeftUp
DownLeft
RightUp
UpRight
LeftUp
LeftUp
UpRight
RightDown
DownRight
LeftDown
RightDown
DownLeft
LeftUp
LeftDown
UpRight
LeftDown
UpRight
DownRight
LeftDown
UpLeft
UpRight
UpLeft
RightUp
RightDown
RightUp
DownRight
DownLeft
LeftUp
UpRight
RightUp
DownLeft
UpLeft
RightDown
LeftDown
LeftUp
LeftDown
DownLeft
RightUp
LeftUp
UpRight
DownRight
UpRight
LeftDown
DownLeft
DownRight
DownLeft

 

[Sonido]

TBH, you are right. It would be boring, but it's also safe. e-condom?

 

[FordGT90Concept]

LMAO, yeah. XD

 

[Sonido]

If you don't want to brute force it as per FordGT's proposal, you can add in some logic to test for un-reachable squares.

eg- if, after making a move, an untouched square is surrounded by touched squares 2 levels deep, the previous move was invalid. Suppose you get an un-reachable square after the 10th move (54 moves left to make) then you've immediately ruled out 432 moves. You need to be clever about it though, you don't want to waste time checking for impossible squares when they are clearly possible

I suppose it all depends on how competent you are at programming and how much computer algorithms interest you

Hmm, sounds like a node system. That would be great for systematically finding every possible solution given a start point. I doubt it would be very fast but it would be far more reliable than my "throw spaghetti at the wall and see if it sticks" solution. XD

I just thought about something... Oliver's solution would take a lot more time to code, but it would take less time to solve. While Ford's concept takes less time to code, it take a lot more time to solve. Hmmm, I just blew my own mind!

 

[FordGT90Concept]

Actually, I doubt a node system would take too long to code--just needs some OOP. The only difference is that, instead of restarting from scratch, it would move back in the move list, try a different solution, and failing that solution, move back and try again. It might be faster, it might not be. I'm not sure if I'll code it though as the OP hasn't come back.