Peg Solitaire Solutions with Backtracking

Question

I'm currently trying to write a program that will be able to find the solutions for the game peg solitaire using back tracking.

My program takes in a txt file that contains a starting board. Everything is done except for the solve() function where the actual back tracking part is contained, this is proving conceptually really difficult for me. I've been working on it on a piece of paper for a while but I don't think I'm making much progress. Any help would be greatly appreciated. Sample txt file below, * = peg, . = open position, 2 = rows 3 = columns

2 3

 .**

 **.

header file

 #pragma once
 #include <string>
 #include <fstream>
 #include <iostream>
 #include <sstream>
 #include <exception>
 using namespace std;
 typedef unsigned char PegType;

class PegBoard
 {

 private:
 int numRows;
 int numCols;
 char ** pegBoard;
 enum  Direction{UP,DOWN,LEFT,RIGHT};
 PegType peg;
 PegType EMPTY;
 PegType openPosition;

public:
//constructor
PegBoard(istream &input);

//deconstructor
 ~PegBoard();

//toString
 void toString() ;

//solve
 bool solve(int x, int y);
private:
//isSolved
bool isSolved();

//canJump
bool canJump(int frmRow, int frmCol, Direction whichWay);

//jump
void jump(int frmRow, int frmCol, Direction whichWay);

//unjump
void unjump(int frmRow, int frmCol, Direction whichWay);

 };

Implementation file

 #include "PegBoard.h"

//constructor
PegBoard::PegBoard(istream &input){
 string dummyLine;
 numCols = 0;
 numRows = 0;
 peg = '*';
 EMPTY = ' ';
 openPosition = '.';

 //get rows and cols
 getline(input,dummyLine);
 numRows = dummyLine[0] - '0';
 numCols = dummyLine[2] - '0';
 pegBoard = new char* [numRows];

 //generate starting board from txt file
    while(!input.eof()){
        for(int r=0; r<numRows; r++){  
            getline(input,dummyLine);
            pegBoard[r] = new char[numCols];
            for(int c=0; c<numCols; c++){
                if(dummyLine[c] == peg || dummyLine[c] == EMPTY || dummyLine[c] == openPosition)
                    pegBoard[r][c] = dummyLine[c];
                else
                    throw out_of_range("Invalid Board Configuration");
            }//end [r][c]
        }// end [r]
    }// end file
}//end constructor

//deconstructor
PegBoard::~PegBoard(){
    for (int i=0; i < numRows; i++)
        delete [] pegBoard[i];
        delete [] pegBoard;
}//end deconstructor

//solve function the one I still need to complete
bool PegBoard::solve(int x, int y){
    //base case
    if(isSolved())
        return true;
    else{
        //attempt a jump at every direction
        for(int i=0; i < 4; i++){
        switch (i){
        case 0: jump(x,y,UP);
                break;
        case 1: jump(x,y,DOWN);
                break;
        case 2: jump(x,y,LEFT);
                break;
        case 3: jump(x,y,RIGHT);
                break;
        default: 
                break;
            }//end switch
        }//end for
    }//end else
        solve(x+1,y);
        return false;
}//end solve()

//isSolved
bool PegBoard::isSolved(){
int counter =0;
//travser through board and check to see if only one * remains. 
   for(int r=0; r<numRows; r++){
        for(int c=0; c<numCols; c++){
            if(pegBoard[r][c] == '*'){
                counter ++;
            }//end check
    }//end [r][c] 
}//end [r]
if(counter == 1)
        return true;
else
        return false;
}//end isSolved()

//canJump
bool PegBoard::canJump(int frmRow, int frmCol, Direction whichWay){
    //check inputed values are in bounds
    if(frmRow >= 0 && frmRow < numRows && frmCol >= 0 && frmCol < numCols){
        //check if inputed values contains a *
        if(pegBoard[frmRow][frmCol] == peg){
            switch (whichWay)
            {
            case PegBoard::UP:
                //check upward bounds
                if(frmRow-2 >= 0){
                    //check if next to peg and if avaiable position to jump to
                    if(pegBoard[frmRow-1][frmCol] == peg && pegBoard[frmRow-2][frmCol] == openPosition)
                        return true;
                    }
                break;
            case PegBoard::DOWN:
                //check downward bounds
                if(frmRow+2 < numRows){
                //check if next to peg and 2 spaces from open position
                    if(pegBoard[frmRow+1][frmCol] == peg && pegBoard[frmRow+2][frmCol] == openPosition)
                        return true;
                    }
                break;
            case PegBoard::LEFT:
                //check left bounds
                if(frmCol-2 >=0){
                    //check if next to peg and 2 spaces from open position
                    if(pegBoard[frmRow][frmCol-1] == peg && pegBoard[frmRow][frmCol-2] == openPosition)
                        return true;
                    }
                break;
            case PegBoard::RIGHT:
                if(frmCol+2 < numCols){
                    //check if next to peg and 2 spaces from open position
                    if(pegBoard[frmRow][frmCol+1] == peg && pegBoard[frmRow][frmCol+2] == openPosition)
                        return true;
                    }
                break;
            default: return false;
                break;
            }//end switch
        }//end peg check
    }//end starting bounds check
    return false;
}//end canJump

  //jump
void PegBoard::jump(int frmRow, int frmCol, Direction whichWay){
    /*
    *      **.
    *      ..* 
    */
    if(canJump(frmRow,frmCol,whichWay)){
    switch (whichWay)
    {
    case UP:
        // assign new position
        pegBoard[frmRow-2][frmCol] = peg;
        //delete starting position
        pegBoard[frmRow][frmCol] = openPosition;
        //delete jumped position
        pegBoard[frmRow-1][frmCol] = openPosition;
        break;
    case DOWN:
        // assign new position
        pegBoard[frmRow+2][frmCol] = peg;
        //delete starting position
        pegBoard[frmRow][frmCol] = openPosition;
        //delete jumped position
        pegBoard[frmRow+1][frmCol] = openPosition;
        break;
    case LEFT:
        // assign new position
        pegBoard[frmRow][frmCol-2] = peg;
        //delete starting position
        pegBoard[frmRow][frmCol] = openPosition;
        //delete jumped position
        pegBoard[frmRow][frmCol-1] = openPosition;
        break;
    case RIGHT:
        // assign new position
        pegBoard[frmRow][frmCol+2] = peg;
        //delete starting position
        pegBoard[frmRow][frmCol] = openPosition;
        //delete jumped position
        pegBoard[frmRow][frmCol+1] = openPosition;
        break;
    default: 
        break;
    }//end switch
    }//end canJump
}//end jump

//unjump
void PegBoard::unjump(int frmRow, int frmCol, Direction whichWay){
    //still need to do
    switch (whichWay)
    {
    case UP:
        // assign new position
        pegBoard[frmRow-2][frmCol] = openPosition;
        //delete starting position
        pegBoard[frmRow][frmCol] = peg;
        //delete jumped position
        pegBoard[frmRow-1][frmCol] = peg;
        break;
    case DOWN:
        // assign new position
        pegBoard[frmRow+2][frmCol] = openPosition;
        //delete starting position
        pegBoard[frmRow][frmCol] = peg;
        //delete jumped position
        pegBoard[frmRow+1][frmCol] = peg;
        break;
    case LEFT:
        // assign new position
        pegBoard[frmRow][frmCol-2] = openPosition;
        //delete starting position
        pegBoard[frmRow][frmCol] = peg;
        //delete jumped position
        pegBoard[frmRow][frmCol-1] = peg;
        break;
    case RIGHT:
        // assign new position
        pegBoard[frmRow][frmCol+2] = openPosition;
        //delete starting position
        pegBoard[frmRow][frmCol] = peg;
        //delete jumped position
        pegBoard[frmRow][frmCol+1] = peg;
        break;
    default: 
        break;
    }//end switch
}

Dude, no way I'm going to read that code... I think you will need to do a *lot* of work to break this down into pieces that are appropriate to ask on Stack Overflow — Niklas B., Mar 22 '14 at 23:02
I'm sorry about that, really only looking for help conceptually on figuring out the back tracking part. Just thought the code examples might be helpful if someone wanted to look at it. — user3450957, Mar 22 '14 at 23:06
Okay, I understand that. In that case, can you please remove the non-relevant code and add a more high-level question? We like *specific* questions here, so as I said, you have some work ahead of you. — Niklas B., Mar 22 '14 at 23:13
@Niklas B.: well, the code was in fact helpful. Not that I was able to read it all though. Perhaps the names of the functions other than `solve` (i.e. the header) would have sufficed, granted they do their job. — Gassa, Mar 22 '14 at 23:19
FWIW, many years ago I worked on this problem, too. The search space is so big that simple backtracking search did not find a solution in one day of running. I had to use A* with a fiddly heuristic. Of course I was doing this work 20 years ago. With a thousand times more computing power available in a PC today, you may be successful with naive search. — Gene, Mar 23 '14 at 04:01

score 4 · Answer 1 · answered Mar 22 '14 at 23:15

4

For some reason, your solve only attempts the cells in a particular order.

The solve would better have the following structure (higher-level pseudocode):

check if we already won
for all x:
    for all y:
        for all directions dir:
            if jump from (x, y) in direction dir is possible:
                (1) do that jump
                (2) recursively call solve
                (3) undo that jump

What yours lacks so far is for all x: for all y: part, and the jump undoing.

answered Mar 22 '14 at 23:15

Gassa

8,546
3
29
49

Thanks, this really helped alot. I'm a little confused about what the recursive call is going to be now. Should I do something like int level and just increment the level each time the call is made, or should I pass in the x,y,direction? My professor said to always pass in the problem and a way to make the problem smaller but I'm struggling to apply that to this situation. – user3450957 Mar 22 '14 at 23:43
@user3450957: The problem is essentially the current board, but that's too heavy to copy on a stack each time you make a move. If you are just checking solvability, perhaps you can do with `bool solve (void)` which will tell whether it succeeded or not, no arguments needed. If you want to also store the optimal solution, then yeah, a depth argument would be handy. The solution itself will be a vector `ans` of triples `(x, y, dir)`. You can make it a class variable and write to `ans[depth]` at each level of recursion. Don't forget to change line `(2)` into `if (solve (depth + 1)) return` then. – Gassa Mar 22 '14 at 23:52
Thanks again, another question hope thats okay. So I have an enum congaing the directions {up,down,left,right} is there a way when I pass in jump(x,y,direction) i can pass in i the value for the for loop instead of having a switch statement for each case of value i. When I hover over the directions they are assigned int values 0-3 but they wont accept an int value when I pass it in. – user3450957 Mar 23 '14 at 00:04
@user3450957: at the very least, you can just cast enum to int, or cast int to enum, where needed. A quick search reveals a [StackOverflow question](http://stackoverflow.com/questions/261963/how-can-i-iterate-over-an-enum) and an answer which suggests a `static_cast`. – Gassa Mar 23 '14 at 00:29
@user3450957 Or simply use the integer values instead of the enum values and have constants to give them names (`const int UP = 0` etc.) – Niklas B. Mar 23 '14 at 00:45

score 1 · Answer 2 · answered May 02 '15 at 15:06

I can empathize with the difficulty of understanding a backtracking algorithm. However, once you understand a few key points it will all become clear. Backtracking is the process of going as far as possible before backing up. Backtraking is a common solution technique for solving the four-queen's problem and mazes. Below is some psedo-code to represent a backtracking algorithm.

FUNCTION backtraking(node):
    IF reject(node) THEN return False
    IF accept(node) THEN return True
    FOR child IN children(node):
     backtraking(child)

In backtracking you go down a solution path as far as you can until you either reach a solution or a dead end. You then take a step back and try another path. The reject function is really the key to the efficiency of the backtracking algorithm. The reject function allows you to reject nodes that you have already explored or meet a criteria. This criteria tells if the node has no descendants that are solutions. Also, it is important to understand that the backtracking function is a recursive function, which means it is a function that calls itself. The FOR loop will not continue until the inner most backtracking call is finished. Once, you understand the fundamentals above then try to rewrite you algorithm. If you get stuck then ask another question here or review the backtracking algorithm I wrote to find the solutions to the peg game problem: http://peggamesolutions.com/programming.html. Happy coding!

Peg Solitaire Solutions with Backtracking

2 Answers2

Linked