具有回溯功能的Peg纸牌解决方案

Question

我目前正在尝试写一个程序，将能够找到解决方案的游戏挂纸牌使用回溯。

我的程序接受一个包含起始板的txt文件。除了包含实际回溯部分的solve()函数之外，一切都完成了，这在概念上对我来说是非常困难的。我已经在一张纸上写了一段时间了，但我认为我没有取得太大进展。任何帮助都将不胜感激。下面的示例txt文件，* = peg，. =打开位置，2 =行3 =列

2 3

 .**

 **.

头文件

 #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);

 };

实现文件

 #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
}

Answer 1

由于某些原因，您的solve仅尝试按特定顺序创建单元格。

solve最好具有以下结构(更高级的伪代码)：

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

到目前为止，您缺少的是for all x: for all y:部件和跳转撤消。

Answer 2

我可以理解理解回溯算法的困难。然而，一旦你理解了几个关键点，一切就会变得清晰起来。回溯是在备份之前尽可能走得更远的过程。回溯是解决四皇后问题和迷宫的常用技术。下面是一些用于表示回溯算法的伪代码。

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

在回溯过程中，你会尽可能地沿着解决方案走下去，直到你找到解决方案或走入死胡同。然后，您后退一步，尝试另一条路径。拒绝函数是回溯算法效率的关键。reject功能允许您拒绝已探索或满足条件的节点。此条件指示节点是否没有作为解决方案的子代。此外，重要的是要理解回溯函数是一个递归函数，这意味着它是一个调用自身的函数。直到最内部的回溯调用完成，FOR循环才会继续。一旦你理解了上面的基础知识，然后尝试重写你的算法。如果你被卡住了，那就在这里问另一个问题，或者回顾一下我写的回溯算法，以找到钉住游戏问题的解决方案：http://peggamesolutions.com/programming.html。祝你编码愉快！