// A brute-force algorithm for finding solutions to the 15 Peg Puzzle.
// Plays 50,000 games with random valid moves and reports all successful games.

import java.util.*;
import java.io.*;

public class PegGameSolve {
  // enumerates all possible moves (from, to, over)	
  private int jumpTable[][] = { {1,4,2},    {1,6,3},                          //  0
                                {2,7,4},    {2,9,5},                          //  2
                                {3,8,5},    {3,10,6},                         //  4
                                {4,6,5},    {4,1,2},    {4,11,7},  {4,13,8},  //  6
                                {5,14,9},   {5,12,8},                         // 10
                                {6,4,5},    {6,13,9},   {6,15,10}, {6,1,3},   // 12
                                {7,2,4},    {7,9,8},                          // 16
                                {8,3,5},    {8,10,9},                         // 18
                                {9,2,5},    {9,7,8},                          // 20
                                {10,8,9},   {10,3,6},                         // 22
                                {11,13,12}, {11,4,7},                         // 24
                                {12,5,8},   {12,14,13},                       // 26
                                {13,11,12}, {13,15,14}, {13,6,9},  {13,4,8},  // 28
                                {14,12,13}, {14,5,9},                         // 32
                                {15,13,14}, {15,6,10}};                       // 34

  private boolean[]  pegPresent = new boolean[15];
  private Random     rn = new Random();
  private List       moveList = new ArrayList();
  private int        pegCount  = 0;
  
  private void reset() {
    for (int i=0; i < pegPresent.length; i++)
      pegPresent[i] = true;
    moveList.clear();
    pegCount = pegPresent.length;
  }
  private void pickHole() {
    int num = rn.nextInt( pegPresent.length );
    pegPresent[num] = false;
    moveList.add( (num < 9 ? " " : "") + (num+1) );
    pegCount--;
  }
  private boolean legalMove( int n ) {
    if (pegPresent[ jumpTable[n][0]-1 ]  &&  pegPresent[ jumpTable[n][2]-1 ]
               &&  ( ! pegPresent[ jumpTable[n][1]-1 ])) {
      pegPresent[ jumpTable[n][0]-1 ] = false;
      pegPresent[ jumpTable[n][2]-1 ] = false;
      pegPresent[ jumpTable[n][1]-1 ] = true;
      pegCount--;
      moveList.add( "" + jumpTable[n][0] + "-" + jumpTable[n][1] );
      return true;
    }
    return false;
  }
  private boolean findMove() {
    for (int i=0, num; i < 15; i++) {
      num = rn.nextInt( jumpTable.length );
      if (legalMove( num ))
        return true;
    }
    for (int i=0; i < jumpTable.length; i++)
      if (legalMove( i ))
        return true;
    return false;     
  }
  public PegGameSolve() throws IOException {
    int          gameCount = 0;
    Set          solutions = new TreeSet();
    FileWriter   fw = new FileWriter( "PegGameSolve.out" );
    StringBuffer sb = new StringBuffer();

    while (true) {
      reset();
      pickHole();
      while (findMove())
        ;
      if (pegCount == 1) {
        sb.setLength( 0 );
        for (int i=0; i < moveList.size(); i++) {
          sb.append( moveList.get(i) );
          sb.append( " " );
        }
        System.out.println( sb.toString() );
        solutions.add( sb.toString() );
        fw.write( sb.toString() + "\r\n" );
      }
      gameCount++;
      if (gameCount % 1000 == 0) {
        sb.setLength( 0 );
        sb.append( "count is " + gameCount + ", pegs left is " + pegCount );
        System.out.println( sb.toString() );
        fw.write( sb.toString() + "\r\n" );
        fw.flush();
        if (gameCount == 50000)
          break;
    } }

    System.out.println();
    fw.write( "\r\n" );
    Object obj;
    for (Iterator it = solutions.iterator(); it.hasNext(); ) {
      obj = it.next();
      System.out.println( obj );
      fw.write( obj + "\r\n" );
    }
    fw.close();
  }
  public static void main( String[] args ) throws IOException {
    new PegGameSolve();
} }