My colleague at work mentioned that there is some puzzle where we have 33 holes in shape of cross and 32 bullets in all the holes but central. To move you should skip one bullet with it's neighbor into empty hole and remove the skipped one. The goal is to clean all but last bullet. He mentioned that it would be interesting to find solution with computer.
And we didn't knew the name of the game. Now it took me almost an hour to find it out for purpose of this article. So now when you know the name of the puzzle, you can easily find the solution on Internet. Actually quite interesting reading.
But I enjoyed brute force search for solution. Below is solution I found after few hours of coding and 6 minutes of intensive computing.
XXX XXX XXX XXX XXX XXX XX0 XX0 XXX XXX 0XX 0XX 0XX 0XX 0X0 0XX XXXXXXX XXXXXXX XX0XXXX 00XXXXX 0X00XXX 0X0X00X 0X0XX0X 0X0X00X XXX0XXX X00XXXX X0XXXXX X0XXXXX X0XXXXX X0XXXXX X0XXXXX X0XX0XX XXXXXXX XXXXXXX XXXXXXX XXXXXXX XXXXXXX XXXXXXX XXXXXXX XXXXXXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XX0 XX0 XX0 XX0 XX0 XX0 XX0 XX0 0XX 0XX 0XX 0XX 0XX 0XX 0XX 0XX 0X0X00X 0X0X00X 0X0X00X 0X0X000 0X0X000 0X0X000 XX0X000 00XX000 X0XXXXX X0XXXXX X0XXXXX X0XXXX0 X0XXXX0 X0XX0X0 00XX0X0 00XX0X0 XXXX0XX XXXXX00 XXX00X0 XXX00XX XXX0X00 XXX0000 0XX0000 0XX0000 XX0 XX0 XX0 XX0 XX0 XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XX0 XX0 00X 00X 000 000 000 000 0XX 0XX 0XX 0XX 0X0 XX0 XX0 XX0 00XX000 00XX000 00XX000 00XX000 00XXX00 000XX00 00X0000 00X0000 00XX0X0 00XX0X0 00XX0X0 00XX0X0 00XX0X0 000X0X0 000X0X0 000X0X0 0XX0X00 0XXXX00 0XXXX00 0XX00X0 0XX00X0 0XX00X0 0XX00X0 000X0X0 XX0 X00 X00 X00 X00 X00 X00 X00 XX0 X00 X00 X00 X00 X00 X00 X00 000 000 000 000 000 000 000 000 XX0 0X0 0X0 0X0 0X0 0X0 0X0 000 00XX000 000X000 000X000 00XX000 00XX0X0 0000XX0 000X000 0000000 00000X0 00X00X0 00X00X0 00000X0 0000000 0000000 0000000 000X000 00000X0 00000X0 00X00X0 00000X0 0000000 0000000 0000000 0000000 X00 X00 000 000 000 000 000 000 X00 X00 000 000 000 000 000 000
And there is the code. I renamed it to peg solitaire afterwards. I used C5 library for HashDictionary, but I'm not sure whether it was really necessary. And yes it takes some memory to compute the results as do breadth-first search. I don't even try any clever heuristics or cutting the tree.
My Linkedin profile
3 comments:
Hi,
My solitaire board is different, it has 4 extra holes. Instead of a 2x2 square missing from each corner, it has the corner hole and the two holes adjacent to the corner missing.
ooxxxoo
oxxxxxo
xxxxxxx
xxxxxxx
xxxxxxx
oxxxxxo
ooxxxoo
Can your program solve this one too? :-)
John
You have European version.
Not at the moment. Feel free to take the opportunity and change it to do so ;-)
Another interesting variation is as follows:
If you move the same peg on two or more consecutive turns, it only counts as one move. What is the minimum number of moves to solve the puzzle?
Post a Comment