aspose file tools*
The moose likes Programming Diversions and the fly likes Jumping Problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Jumping Problem" Watch "Jumping Problem" New topic
Author

Jumping Problem

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
The following thread was originally started by Sameer Jamal. I'm reposting it this way because it was accidentally deleted during the move to Programming Diversions:
***************************************************
Posted by: Sameer Jamal, 05-12-2003 09:44 AM:
You have a grid that's 5x5. Every grid square but one contains a counter. The empty grid square is determined at random.
Example:

Problem 1: to remove all the counters but one, by jumping like in checkers . Jumps can be horizontal or vertical. You can only move by jumping another counter and removing it.
Problem 2: display a solution for how the solution was achieved. Eg: in the above puzzle, assume that the first row is numbered 1-5, and the second 6-10. The first move might be 8>>10 with 9 being removed. Equally, you might decide on a 2-dimensional numbering system, in which case your first move might be (3,4)>>(5,4) with (4,4) being removed.
***************************************************
Posted by: Jason Menard, 05-27-2003 01:56 PM
Has anyone else bothered to try this? I have a solution using only bit manipulation in integers, instead of using arrays or some other data structure. The problem is, due to the number of possible moves that can be made on a 5 X 5 board, starting out with all holes having pegs in them except for one, the length of time it takes to find a solution is extreme to say the least.
By default the program will generate a proper seed board (that is one with all holes filled except one), but you can also set the seed allowing it to find a solution with a board in an other than initial state. I've run the program setting the seed to prove that my logic is correct, and it seems to be, but I have not had the patience to wait the several hours it would take to find a solution on a full board.
Now the performance problem may be in my logic or algorithms, but I'm thinking that solving this via brute force simply generates too many permutations with a board of this size. I welcome any comments regarding this. Now keeping in mind that I may have just screwed something up, can anyone else solve it?
If you run this and want to actually see some results, uncomment the commented out line in my main method. A seed of 1000091 is one of many that will produce a solution, althought the board is far from full at that point. The solution shows both the moves made to achieve the solution, as well as the states of the board from start to finish.

[ May 27, 2003: Message edited by: Jason Menard ]
***************************************************
Posted by: Joel McNary, 05-27-2003 02:21 PM
This sounds like a good candidate for a genetic Alrogithm to me. I'll see what I can come up with. (Jason: I've not looked at you your code, so it should be interesting to see what I get ).
***************************************************
Posted by: Jason Menard, 05-27-2003 02:28 PM

The least significant bit is at [0,0]. Moving right from [0,0] to [0,2], removing [0,1], would give us a board that could be represented by 1000092 (11110100001010011100):

So while it should save in terms of space by using bit manipulation of integers over some data structure containing an array representation of the board's state, is bit manipulation more performant in the manner I have used it then accessing and manipulating elements in an array, which would be the obvious alternative? Is the lack in performance due to the number of permutations, or due to some other reason?
[ May 27, 2003: Message edited by: Jason Menard ]
***************************************************
Posted by: Eric Pascarello, 05-28-2003 12:14 PM
I was playing around with this last night, got nowhere with it, but you can cut a lot of the work out with a general solution by rotating the board. The starting points of the empty element is the same at four points of the board. I coded tic tac toe this way. I had a function that transformed the board into that setup. I am playing around with it and I am trying to keep my code clean so you can understand it. I will see what this fried brain can come up with.
Eric
***************************************************
Posted by: Joel McNary, 05-28-2003 12:44 PM

I have greatly increased the performance of my code by making the following small changes:

The solution for seed 33538047 is :
Move down from [0,4] to [2,4], removing [1,4]
Move right from [0,2] to [0,4], removing [0,3]
Move right from [0,0] to [0,2], removing [0,1]
Move right from [1,2] to [1,4], removing [1,3]
Move right from [1,0] to [1,2], removing [1,1]
Move up from [3,0] to [1,0], removing [2,0]
Move up from [3,1] to [1,1], removing [2,1]
Move right from [1,1] to [1,3], removing [1,2]
Move left from [1,4] to [1,2], removing [1,3]
Move left from [2,3] to [2,1], removing [2,2]
Move down from [0,2] to [2,2], removing [1,2]
Move right from [2,1] to [2,3], removing [2,2]
Move up from [3,4] to [1,4], removing [2,4]
Move down from [0,4] to [2,4], removing [1,4]
Move left from [2,4] to [2,2], removing [2,3]
Move up from [4,3] to [2,3], removing [3,3]
Move left from [2,3] to [2,1], removing [2,2]
Move right from [4,1] to [4,3], removing [4,2]
Move left from [4,4] to [4,2], removing [4,3]
Move up from [4,2] to [2,2], removing [3,2]
Move left from [2,2] to [2,0], removing [2,1]
Move down from [1,0] to [3,0], removing [2,0]
Move up from [4,0] to [2,0], removing [3,0]
Solution found and displayed in 561ms
[ May 29, 2003: Message edited by: Jason Menard ]
***************************************************
Posted by: Jason Menard, 05-29-2003 10:45 AM
You can also find a solution for

Aside from those two and any board that is symetrical to those two, I think those are the only solutions.
[ May 29, 2003: Message edited by: Jason Menard ]
***************************************************
Posted by: Eric Pascarello, 05-29-2003 02:57 PM
I got a solution from a random number generator. It is totally random. I ran it beofre I left to work and came back home to find on game 4653 it found a solution for

Hole: (2,0)
(4,0) to (2,0)
(1,0) to (3,0)
(2,2) to (2,0)
(0,1) to (2,1)
(4,2) to (4,0)
(2,1) to (4,1)
(2,4) to (2,2)
(3,3) to (3,1)
(4,4) to (2,4)
(1,3) to (1,1)
(3,0) to (1,0)
(1,4) to (3,4)
(0,0) to (2,0)
(4,0) to (4,2)
(4,3) to (4,1)
(4,1) to (2,1)
(0,3) to (0,1)
(2,1) to (2,3)
(0,1) to (2,1)
(2,0) to (2,2)
(2,2) to (2,4)
(3,4) to (1,4)
(0,4) to (2,4)
Num Left: 1
WOHOOOO, never thought a random num. generator could hit the answer but it did.
Eric
I am working on another way to do it.
***************************************************
Posted by: Eric Pascarello, 05-29-2003 03:26 PM
If you want to see my slow code in action, you can see it here. The one I am working on now does not actually play the game like this one does
http://www10.brinkster.com/a1ien51/game/pegged2.htm
To stop the code, you just need to click on a ball.
Eric
***************************************************
Posted by: Jason Menard, 05-29-2003 03:35 PM
So ya gonna post your code/algorithm, or what?
***************************************************
Posted by: Eric Pascarello, 05-29-2003 04:08 PM Link-->, view source and you see my code,
I have no "real" algorithm..100% trial and error
All it does is this:
Looks for the avilable moves, places them into an array. Takes a random number that has the range of the length of the array and moves that peg.
And it goes like the energizer bunny.
I have a faster version here which I did not post. It includes no images, so it speeds up the process, but it is still slow. I am working on a brute force method, but not going to get it done soon.
I have to put delays into the code, so it does not hang my computer. 333 with no ram....lol
http://www10.brinkster.com/a1ien51/game/pegged3b.htm
Eric
[ May 29, 2003: Message edited by: Eric Pascarello ]
***************************************************
Posted by: Jason Menard, 05-29-2003 04:25 PM
The way I solved the performance issue when using brute force is to not try to sovle the same board state twice. By board state I mean where the pegs are placed and which holes are empty. While there are several different ways one might arrive at a particular board state, there's no need to go any further if we have already processed all the moves from that board state. So by not trying to solve duplicate board states, you tremendously cut down on the number of attempts required to exhaustively search for a solution.
Am I making sense?
***************************************************
Posted by: Eric Pascarello, 05-29-2003||05:04 PM
The code I posted was just on a whim saying hey I can use random numbers it make it play. The code I am trying to develop is going to look at it in a systematic ways so it does not repeat the same states. I can see the code in my head, but I can not get it to run the way I want to.
I just keep thinkning of ways to chop down the millions of possibilities.|
***************************************************
Posted by: Eric Pascarello, 05-30-2003 03:17 PM
I only found those two locations rotated around the board have that solution. All of the other ones can get down to 2 but that is far as they go.
Eric
[ May 31, 2003: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, Twister
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Jumping Problem