Tuesday, January 20, 2009

English peg solitaire

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.