带有后退功能的钉接龙解决方案 [英] Peg Solitaire Solutions with Backtracking
本文介绍了带有后退功能的钉接龙解决方案的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我目前正在尝试编写一个程序，该程序将能够使用向后跟踪功能来找到游戏钉单人纸牌的解决方案。
I'm currently trying to write a program that will be able to find the solutions for the game peg solitaire using back tracking.
我的程序接收一个包含起始板的txt文件。除了solve（）函数（包含实际的反向跟踪部分）之外，所有工作都已完成，这在概念上对我来说真的很困难。我已经在纸上进行了一段时间的研究，但我认为我没有取得太大的进步。任何帮助将不胜感激。下面的示例txt文件， * =钉，。 =开仓， 2 =行 3 =列
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
.**
**.
头文件
#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
}
推荐答案
由于某些原因，您的 solve 仅按特定顺序尝试单元格。
For some reason, your solve only attempts the cells in a particular order.
solve 最好具有以下结构（高级伪代码）：
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
到目前为止，您缺少的是所有x的：所有y：的部分，以及跳转撤消。
What yours lacks so far is for all x: for all y: part, and the jump undoing.
这篇关于带有后退功能的钉接龙解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
