Peg Solitaire-like game solving strategy

[mugen]

Hi,

I am assigned a project that will solve a game which is based on peg solitiare (Peg solitaire - Wikipedia, the free encyclopedia) but with some different rules. Instead of having a plus sign-like table, th program will get an input, n, and there will be n x n pegs placed like a square, there will be no hole in the middle of the board and there is no boundary around the pegs, board is infinite.. Our instructor suggested to use brute force.. My strategy was at first move, to ignore the symmetrics and rotations, just to focus one corner then build tree recursively. For the input 2 and 3 there is no problem but when I try 4 x 4 it takes almost a minute than terminates with a wrong return value. I suppose it is something related to memory, I mean the program allocates too much for all possibilities at every move... I would appreciate any suggestions about strategies to solve the game in more efficient ways. Thanks.

[mugen]

Any idea?

[quzah]

If there are N pieces, there are N-2 moves.

board: **o
move: oo*

Three pieces, one move (jump left to right, over center).

board: **o*
move: oo**
move: o*oo

Four pieces, two moves (jump left over piece to the right of it, jump right over piece to the left.)

So, you should never have more than N-2 moves, which gives you a stopping point for any path you're attempting. Looks right anyway. And actually, it looks like it should be exactly N-2 moves. So if you're at a dead end at less than that, you've messed up, and can throw that out as a choice.


Quzah.

[mugen]

After some depth level, allocation failes I need to reduce the memory consumption and I am using Int to store just 0's and 1's.. I tried short but i got some errors.. Any suggestion to minimize the data type? thanks for any response

[vart]

I tried short but i got some errors..

If you got SOME errors, you'll need to make SOME changes to your code... This is the best suggestion I have looking at your error description

[quzah]

If I'm reading your original post again right, you're screwed. You're supposed to write a solve for an arbitrary number of pieces, on an infinite board (meaning you can wander off in any direction)? Did you even read the Wiki link? On a + board, with a piece missing, there are a massive number of possible moves to figure out (3 million). I don't even want to know at this point.

You're going to have to figure out rules which you can use to cull possible moves. You basically need to figure out if there is a set pattern to take with a square, which will solve it. You probably need to figure out if with even or odd sides, if that matters. Consider:

00000
01230
04560
07890
00000

Everything outside of the frame of 0s in all directions is infinity. You can go there if you really want to, and if you can figure how to stretch pieces that far. But that's now what I'd advise. I'd advise you just work around the edge, if that's even possible. Like so:

04000
0X230
0*560
07890
00000

0000
04500
00X30
00*60
07890
00000

00000
0*x40
00030
00060
07890
00000

There. That's not going to work. I can see, that but basically, that's what I think you need to do. Figure out the pattern for solving a square of even and odd sides. I think that's all you have to do. If that's even possible.

0000
0120
0340
0000

00000
02X*0
00340
00000

00000
02000
04X*0
00000

Well that works. Next move is solve. Does it work with 4x4? And how do you put that into rules? Brute force is really going to be a nightmare. So if you can see if there's a pattern to solving squares, and apply that to your solver, that's probably the best way to go.


Quzah.

[mugen]

Thanks quzah you got the problem correctly, 4x4 and 5x5 is really painfull.. The instructor himself accepts that this possibilities are really hard to deal with but he also want us to struggle Shortly, at first move I ignore the 3/4 of the board (symmetrics and rotations) and just focus on the up-left corner this reduces the memory consumption but after that the code tries recursively all the possible moves till there is no possible moves.. 3x3 is good the tree is constructed well but 4x4 kills my laptop

I thought not to pass the whole table to the function, instead I will think about passing a stack of moves maybe this will reduce the memory consumption but you are really right I need some strategies.. Actually I dont need symmetrical solutions but at the end there will be although I ignore at the first stage the symmetircs.. I am really stuck on this project.. Now I try to minimize the variables like int, mostly I only need 0s and 1s.. maybe I try a char representation..

[C_ntua]

Yes, char is the correct type for 0s and 1s.

If again it is too much (haven't thought about the problem in hand) you can use bits rather than bytes. You can store 8 0s or 1s in one char for example. Then use bitwise operators to extract each bit. Most likely the AND (&) operator and some masks. Like:

01001101 char val;
00000001 AND val = 1st bit
00000010 AND val = 2nd bit

More complicated this way, but you can create some functions to help you out. Try calculating the data if possible to see if it suits you. You can also consider storing information in HD (in a file).