/**
 * Solves some instances of Peg Solitaire.
 * 
 * @author (Stefan Edelkamp) 
 * @version (2013)
 */
public class Peg
{
    final int PEGS = 5; // 25;
    final int XDIM = 4; // 7;
    final int YDIM = 5; // 6;
    private int [] solx = new int [PEGS];
    private int [] soly = new int [PEGS];

    private char B[][] = {
     {'-','-','o','-','o'},
     {'o','o','x','x','o'},
     {'o','x','x','x','o'},
     {'-','o','o','o','o'} };
/* 
    final int PEGS = 25;
    final int XDIM = 7;
    final int YDIM = 6;
    private int [] solx = new int [PEGS];
    private int [] soly = new int [PEGS];
  
    private char B[][] = {
        {'-','-','x','x','-','-'},
        {'-','-','x','x','-','-'},
        {'x','x','x','x','x','x'},
        {'x','x','o','x','x','x'},
        {'x','x','x','x','x','x'},
        {'-','-','x','x','-','-'},
        {'-','-','x','x','-','-'} };
 */       
      

        
    /**
     * Constructor for objects of class Peg
     */
    public Peg() {
        solve(PEGS);
    }
    /**
     * Solution method
     * 
     * @param  pegs   number of remaining pegs
     */
    public void solve(int pegs) {
      if (pegs == 1) {
        for (int i=PEGS-1;i>0;i--) 
          System.out.print("("+solx[i]+","+soly[i]+")"); 
        System.exit(1);
      }
      for (int i=0;i<XDIM;i++)    
        for (int j=2;j<YDIM;j++)  
          if (B[i][j] == 'o' && B[i][j-1] == 'x' && B[i][j-2] == 'x') {
	        B[i][j-2] = B[i][j-1] = 'o'; B[i][j] = 'x';
	        solx[pegs-1] = i; soly[pegs-1] = j;
	        solve (pegs-1);
	        B[i][j-2] = B[i][j-1] = 'x'; B[i][j] = 'o';
          }
      for (int i=0;i<XDIM;i++)    
        for (int j=0;j<YDIM-2;j++) 
          if (B[i][j] == 'o' && B[i][j+1] == 'x' && B[i][j+2] == 'x') {
	        B[i][j+2] = B[i][j+1] = 'o'; B[i][j] = 'x';
	        solx[pegs-1] = i; soly[pegs-1] = j;
	        solve (pegs-1);
	        B[i][j+2] = B[i][j+1] = 'x'; B[i][j] = 'o';
          }
      for (int i=2;i<XDIM;i++)     
        for (int j=0;j<YDIM;j++)    
          if (B[i][j] == 'o' && B[i-1][j] == 'x' && B[i-2][j] == 'x') {
	        B[i-2][j] = B[i-1][j] = 'o'; B[i][j] = 'x';
	        solx[pegs-1] = i; soly[pegs-1] = j;
	        solve (pegs-1);
	        B[i-2][j] = B[i-1][j] = 'x'; B[i][j] = 'o';
          }
      for (int i=0;i<XDIM-2;i++) 
        for (int j=0;j<YDIM;j++)    
          if (B[i][j] == 'o' && B[i+1][j] == 'x' && B[i+2][j] == 'x') {
	        B[i+2][j] = B[i+1][j] = 'o'; B[i][j] = 'x';
	        solx[pegs-1] = i; soly[pegs-1] = j;
	        solve (pegs-1);
	        B[i+2][j] = B[i+1][j] = 'x'; B[i][j] = 'o';
          }
    }
}