1. Welcome to TechPowerUp Forums, Guest! Please check out our forum guidelines for info related to our community.

Java+VB developers project

Discussion in 'Programming & Webmastering' started by CAPITAL LETTERS, May 7, 2009.

  1. CAPITAL LETTERS

    CAPITAL LETTERS New Member

    Joined:
    Jan 4, 2009
    Messages:
    136 (0.07/day)
    Thanks Received:
    13
    Location:
    Ninja's Dont Need Homes
    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
  2. FordGT90Concept

    FordGT90Concept "I go fast!1!11!1!"

    Joined:
    Oct 13, 2008
    Messages:
    12,958 (6.44/day)
    Thanks Received:
    3,074
    Location:
    IA, USA
    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 :p).
    Crunching for Team TPU
  3. daragez New Member

    Joined:
    Apr 17, 2009
    Messages:
    155 (0.08/day)
    Thanks Received:
    16
    great project!...nice share!..
  4. FordGT90Concept

    FordGT90Concept "I go fast!1!11!1!"

    Joined:
    Oct 13, 2008
    Messages:
    12,958 (6.44/day)
    Thanks Received:
    3,074
    Location:
    IA, USA
    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:
    Code:
    +----+----+----+----+----+----+----+----+
    |  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:
    Code:
    +----+----+----+----+----+----+----+----+
    |  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. :p


    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. ;)
    Last edited: May 7, 2009
    Crunching for Team TPU
  5. FordGT90Concept

    FordGT90Concept "I go fast!1!11!1!"

    Joined:
    Oct 13, 2008
    Messages:
    12,958 (6.44/day)
    Thanks Received:
    3,074
    Location:
    IA, USA
    I multithreaded it. The fastest result so far is:

    Attempts: 3,181
    Duration: 0.2031250 seconds
    Seed: 110152139
    Solution:
    Code:
    +----+----+----+----+----+----+----+----+
    |  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. ;)
    Last edited: May 7, 2009
    CAPITAL LETTERS says thanks.
    Crunching for Team TPU
  6. CAPITAL LETTERS

    CAPITAL LETTERS New Member

    Joined:
    Jan 4, 2009
    Messages:
    136 (0.07/day)
    Thanks Received:
    13
    Location:
    Ninja's Dont Need Homes
    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
  7. FordGT90Concept

    FordGT90Concept "I go fast!1!11!1!"

    Joined:
    Oct 13, 2008
    Messages:
    12,958 (6.44/day)
    Thanks Received:
    3,074
    Location:
    IA, USA
    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
    Last edited: May 7, 2009
    Crunching for Team TPU
  8. Oliver_FF

    Oliver_FF New Member

    Joined:
    Oct 15, 2006
    Messages:
    546 (0.20/day)
    Thanks Received:
    65
    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 :)
  9. FordGT90Concept

    FordGT90Concept "I go fast!1!11!1!"

    Joined:
    Oct 13, 2008
    Messages:
    12,958 (6.44/day)
    Thanks Received:
    3,074
    Location:
    IA, USA
    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.
    Crunching for Team TPU
  10. Sonido

    Sonido New Member

    Joined:
    Aug 25, 2008
    Messages:
    357 (0.17/day)
    Thanks Received:
    86
    Location:
    USA
    The equation would actually be quite long. The permutations possible are in the range of "A LOT". So... Yea... :D

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

    FordGT90Concept "I go fast!1!11!1!"

    Joined:
    Oct 13, 2008
    Messages:
    12,958 (6.44/day)
    Thanks Received:
    3,074
    Location:
    IA, USA
    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:

    Code:
    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:
    Code:
    +----+----+----+----+----+----+----+----+
    |  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...
    Code:
    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
    Last edited: May 8, 2009
    Crunching for Team TPU
  12. Sonido

    Sonido New Member

    Joined:
    Aug 25, 2008
    Messages:
    357 (0.17/day)
    Thanks Received:
    86
    Location:
    USA
    TBH, you are right. It would be boring, but it's also safe. e-condom?
  13. FordGT90Concept

    FordGT90Concept "I go fast!1!11!1!"

    Joined:
    Oct 13, 2008
    Messages:
    12,958 (6.44/day)
    Thanks Received:
    3,074
    Location:
    IA, USA
    LMAO, yeah. XD
    Crunching for Team TPU
  14. Sonido

    Sonido New Member

    Joined:
    Aug 25, 2008
    Messages:
    357 (0.17/day)
    Thanks Received:
    86
    Location:
    USA
    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!
  15. FordGT90Concept

    FordGT90Concept "I go fast!1!11!1!"

    Joined:
    Oct 13, 2008
    Messages:
    12,958 (6.44/day)
    Thanks Received:
    3,074
    Location:
    IA, USA
    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. :(
    Crunching for Team TPU

Currently Active Users Viewing This Thread: 1 (0 members and 1 guest)

Share This Page