Как видно из названия, у меня возникли проблемы с поиском ошибки в способе заполнения моей очереди.Он должен содержать каждый посещенный узел состояния, пока они не будут обработаны.но очередь не заполняется так, как должно быть.Может кто-нибудь помочь мне найти ошибку?Ниже приведен мой файл реализации для класса PuzzleStateNode и source.cpp
EDIT: после дополнительной отладки может показаться, что проблема заключается в следующем фрагменте кода из функции solvePuzzle.Предметы никогда не помещаются в мою очередь, и я не понимаю, почему.Может ли это быть проблемой с моим unordered_set?
void solvePuzzle(string stateArray[3][3]) {
ofstream oFile("output.txt");
PuzzleStateNode pState(stateArray);
queue<PuzzleStateNode> puzzleQueue;
unordered_set<string> visitedPuzzleStateSet;
if (pState.parityCheck() == true) {
puzzleQueue.push(pState);
for(int i = 0; i < 31; i++){
PuzzleStateNode myTempState(puzzleQueue.front());
//puzzleQueue.pop();
if (visitedPuzzleStateSet.find(myTempState.getPuzzleID()) == visitedPuzzleStateSet.end()) { // is our value in the set? if not then do the following
visitedPuzzleStateSet.emplace(myTempState.getPuzzleID()); // add to the list of visited states.
if (myTempState.getEmptyXArrayPos() == 0 || myTempState.getEmptyXArrayPos() == 1) { // if a move to the right is available
PuzzleStateNode tempState;
tempState = PuzzleStateNode(myTempState);
tempState.moveEmptySquareRight(tempState.getEmptyXArrayPos(), tempState.getEmptyYArrayPos());
if (tempState.checkForSolve() == true) {
tempState.printState(oFile);
oFile << "Puzzle Solved in " << tempState.getMoveCounter() << " movements of the emtpy tile which are listed below." << endl;
tempState.printMoves(oFile);
cout << "Puzzle Solved!" << endl << endl << endl;
oFile.close();
return;
}
else if (tempState.checkForSolve() != true && visitedPuzzleStateSet.find(tempState.getPuzzleID()) == visitedPuzzleStateSet.end()) {
puzzleQueue.push(tempState);
}
else {
cout << "you have visited this already" << endl;
system("pause");
}
}
END EDIT:
PuzzleStateNode.h
#pragma once
#include<queue>
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<string>
using namespace std;
class PuzzleStateNode
{
public:
PuzzleStateNode();
PuzzleStateNode(string tempArray[3][3]);
PuzzleStateNode(const PuzzleStateNode &other);
int getEmptyXArrayPos();
int getEmptyYArrayPos();
int getMoveCounter();
string getPuzzleID();
bool parityCheck();
bool checkForSolve();
void setPuzzleID();
void setEmptyXArrayPos(int x);
void setEmptyYArrayPos(int y);
void incrimentMoveCounter();
void pushToMoveQueue(string move);
void moveEmptySquareDown(int xEmptyPos, int yEmptyPos);
void moveEmptySquareUp(int xEmptyPos, int yEmptyPos);
void moveEmptySquareRight(int xEmptyPos, int yEmptyPos);
void moveEmptySquareLeft(int xEmptyPos, int yEmptyPos);
void printState(ofstream &oFile);
void printMoves(ofstream &oFile);
~PuzzleStateNode();
private:
string puzzleStateArray[3][3];
int moveCounter;
queue<string> moveQueue;
int emptyXArrayPos;
int emptyYArrayPos;
string puzzleID;
};
PuzzleStateNode.cpp
#include "PuzzleStateNode.h"
using namespace std;
PuzzleStateNode::PuzzleStateNode()
{
}
PuzzleStateNode::PuzzleStateNode(string tempArray[3][3])
{
puzzleID = "";
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
puzzleStateArray[i][j] = tempArray[i][j];
puzzleID += tempArray[i][j];
if (puzzleStateArray[i][j] == "E") {
emptyXArrayPos = j;
emptyYArrayPos = i;
}
}
}
moveCounter = 0;
moveQueue.push("The following lists the movement of the Empty or 'E' square until the puzzle is solved: ");
}
PuzzleStateNode::PuzzleStateNode(const PuzzleStateNode &other) {
{ puzzleID = "";
moveCounter = other.moveCounter;
moveQueue = other.moveQueue;
emptyXArrayPos = other.emptyXArrayPos;
emptyYArrayPos = other.emptyYArrayPos;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
puzzleStateArray[i][j] = other.puzzleStateArray[i][j];
puzzleID += other.puzzleStateArray[i][j];
}
}
}
}
int PuzzleStateNode::getEmptyXArrayPos() {
return emptyXArrayPos;
}
int PuzzleStateNode::getEmptyYArrayPos() {
return emptyYArrayPos;
}
int PuzzleStateNode::getMoveCounter() {
return moveCounter;
}
string PuzzleStateNode::getPuzzleID() {
return puzzleID;
}
bool PuzzleStateNode::checkForSolve() {
if (puzzleStateArray[0][0] == "1" && puzzleStateArray[0][1] == "2" && puzzleStateArray[0][2] == "3" && puzzleStateArray[1][0] == "4" && puzzleStateArray[1][1] == "5" && puzzleStateArray[1][2] == "6" && puzzleStateArray[2][0] == "7" && puzzleStateArray[2][1] == "8" && puzzleStateArray[2][2] == "E") {
return true;
}
return false;
}
void PuzzleStateNode::setPuzzleID() {
puzzleID = "";
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
puzzleID += puzzleStateArray[i][j];
}
}
}
void PuzzleStateNode::setEmptyXArrayPos(int x) {
emptyXArrayPos = x;
}
void PuzzleStateNode::setEmptyYArrayPos(int y) {
emptyXArrayPos = y;
}
void PuzzleStateNode::incrimentMoveCounter() {
moveCounter++;
}
void PuzzleStateNode::pushToMoveQueue(string move) {
moveQueue.push(move);
}
void PuzzleStateNode::printMoves(ofstream &oFile) {
string tempString;
for (int i = 0; i < moveQueue.size(); i++) {
cout << moveQueue.front() << endl;
moveQueue.push(moveQueue.front());
moveQueue.pop();
}
cout << endl << endl;
}
void PuzzleStateNode::printState(ofstream &oFile) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cout << puzzleStateArray[i][j];
}
cout << endl;
}
cout << endl;
}
void PuzzleStateNode::moveEmptySquareDown(int xEmptyPos, int yEmptyPos) {
puzzleStateArray[yEmptyPos][xEmptyPos] = puzzleStateArray[yEmptyPos + 1][xEmptyPos];
puzzleStateArray[yEmptyPos + 1][xEmptyPos] = "E";
moveQueue.push("Down");
moveCounter++;
cout << "Moving Down" << endl;
emptyYArrayPos = yEmptyPos + 1;
}
void PuzzleStateNode::moveEmptySquareUp(int xEmptyPos, int yEmptyPos) {
puzzleStateArray[yEmptyPos][xEmptyPos] = puzzleStateArray[yEmptyPos - 1][xEmptyPos];
puzzleStateArray[yEmptyPos - 1][xEmptyPos] = "E";
moveQueue.push("Up");
moveCounter++;
cout << "Moving Up" << endl;
emptyYArrayPos = yEmptyPos - 1;
}
void PuzzleStateNode::moveEmptySquareLeft(int xEmptyPos, int yEmptyPos) {
puzzleStateArray[yEmptyPos][xEmptyPos] = puzzleStateArray[yEmptyPos][xEmptyPos - 1];
puzzleStateArray[yEmptyPos][xEmptyPos - 1] = "E";
moveQueue.push("Left");
moveCounter++;
cout << "Moving Left" << endl;
emptyXArrayPos = xEmptyPos - 1;
}
void PuzzleStateNode::moveEmptySquareRight(int xEmptyPos, int yEmptyPos) {
puzzleStateArray[yEmptyPos][xEmptyPos] = puzzleStateArray[yEmptyPos][xEmptyPos + 1];
puzzleStateArray[yEmptyPos][xEmptyPos + 1] = "E";
moveQueue.push("Right");
moveCounter++;
cout << "Moving Right" << endl;
emptyXArrayPos = xEmptyPos + 1;
}
bool PuzzleStateNode::parityCheck() // counts number of swaps for a bubble sort excluding swaps involving the empty space
{
enter code here
// Puzzles with odd swaps have odd parity and are unsolvable.
string parityCheckString = "";
char tempChar;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
parityCheckString += puzzleStateArray[i][j];
}
}
int counter = 0;
for (int j = 0; j < 8; j++) {
for (int i = 0; i < 8; i++) {
if (parityCheckString[i] > parityCheckString[i + 1]) {
if (parityCheckString[i] == 'E') {
tempChar = parityCheckString[i];
parityCheckString[i] = parityCheckString[i + 1];
parityCheckString[i + 1] = tempChar;
}
else {
tempChar = parityCheckString[i];
parityCheckString[i] = parityCheckString[i + 1];
parityCheckString[i + 1] = tempChar;
counter += 1;
}
}
}
}
if (counter % 2 == 0) {
cout << "Even Parity, solving the 8 puzzle!" << endl;
return true;
}
else {
cout << "Parity is odd and puzzle is unsolvable. Skipping to next Puzzle." << endl;
return false;
}
}
PuzzleStateNode::~PuzzleStateNode()
{
}
source.cpp
#include"PuzzleStateNode.h"
#include<string>
#include<fstream>
#include<iostream>
#include<unordered_set>
using namespace std;
int main() {
void solvePuzzle(string stateArray[3][3]);
ifstream inFile("input.txt");
ofstream outFile("output.txt");
string puzNum;
int numberOfPuzzles;
string junk;
getline(inFile, puzNum); // read number of puzzles
numberOfPuzzles = stoi(puzNum); // convert value to int.
for (int i = 0; i < numberOfPuzzles; i++) {
string stateArray[3][3]; // populates a temporary puzzle state.
string temp;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
while (temp != "1" && temp != "2" && temp != "3" && temp != "4" && temp != "5" && temp != "6" && temp != "7" && temp != "8" && temp != "E") {
temp = inFile.get();
}
stateArray[i][j] = temp;
temp = inFile.get();
}
}
solvePuzzle(stateArray);
}
system("pause");
return 0;
}
void solvePuzzle(string stateArray[3][3]) {
ofstream oFile("output.txt");
PuzzleStateNode pState(stateArray);
queue<PuzzleStateNode> puzzleQueue;
unordered_set<string> visitedPuzzleStateSet;
if (pState.parityCheck() == true) {
puzzleQueue.push(pState);
for(int i = 0; i < 31; i++){
PuzzleStateNode myTempState(puzzleQueue.front());
//puzzleQueue.pop();
if (visitedPuzzleStateSet.find(myTempState.getPuzzleID()) == visitedPuzzleStateSet.end()) { // is our value in the set? if not then do the following
visitedPuzzleStateSet.emplace(myTempState.getPuzzleID()); // add to the list of visited states.
if (myTempState.getEmptyXArrayPos() == 0 || myTempState.getEmptyXArrayPos() == 1) { // if a move to the right is available
PuzzleStateNode tempState;
tempState = PuzzleStateNode(myTempState);
tempState.moveEmptySquareRight(tempState.getEmptyXArrayPos(), tempState.getEmptyYArrayPos());
if (tempState.checkForSolve() == true) {
tempState.printState(oFile);
oFile << "Puzzle Solved in " << tempState.getMoveCounter() << " movements of the emtpy tile which are listed below." << endl;
tempState.printMoves(oFile);
cout << "Puzzle Solved!" << endl << endl << endl;
oFile.close();
return;
}
else if (tempState.checkForSolve() != true && visitedPuzzleStateSet.find(tempState.getPuzzleID()) == visitedPuzzleStateSet.end()) {
puzzleQueue.push(tempState);
}
else {
cout << "you have visited this already" << endl;
system("pause");
}
}
if (myTempState.getEmptyXArrayPos() == 1 || myTempState.getEmptyXArrayPos() == 2) {
PuzzleStateNode tempState;
tempState = PuzzleStateNode(myTempState);
tempState.moveEmptySquareLeft(tempState.getEmptyXArrayPos(), tempState.getEmptyYArrayPos());
tempState.incrimentMoveCounter();
if (tempState.checkForSolve() == true) {
tempState.printState(oFile);
oFile << "Puzzle Solved in " << tempState.getMoveCounter() << " movements of the emtpy tile which are listed below." << endl;
tempState.printMoves(oFile);
cout << "Puzzle Solved!" << endl;
oFile.close();
return;
}
else if (tempState.checkForSolve() != true && visitedPuzzleStateSet.find(tempState.getPuzzleID()) == visitedPuzzleStateSet.end()) {
puzzleQueue.push(tempState);
}
else {
cout << "you have visited this state" << endl;
system("pause");
}
}
if (myTempState.getEmptyYArrayPos() == 0 || myTempState.getEmptyYArrayPos() == 1) {
PuzzleStateNode tempState;
tempState = PuzzleStateNode(myTempState);
tempState.moveEmptySquareDown(tempState.getEmptyXArrayPos(), tempState.getEmptyYArrayPos());
if (tempState.checkForSolve() == true) {
tempState.printState(oFile);
oFile << "Puzzle Solved in " << tempState.getMoveCounter() << " movements of the emtpy tile which are listed below." << endl;
tempState.printMoves(oFile);
cout << "Puzzle Solved!" << endl;
oFile.close();
return;
}
else if (tempState.checkForSolve() != true && visitedPuzzleStateSet.find(tempState.getPuzzleID()) == visitedPuzzleStateSet.end()) {
puzzleQueue.push(tempState);
}
else {
cout << "you have this state already" << endl;
system("pause");
}
}
if (myTempState.getEmptyYArrayPos() == 1 || myTempState.getEmptyYArrayPos() == 2) {
PuzzleStateNode tempState(myTempState);
tempState = PuzzleStateNode(myTempState);
tempState.moveEmptySquareUp(tempState.getEmptyXArrayPos(), tempState.getEmptyYArrayPos());
if (tempState.checkForSolve() == true) {
tempState.printState(oFile);
oFile << "Puzzle Solved in " << tempState.getMoveCounter() << " movements of the emtpy tile which are listed below." << endl;
tempState.printMoves(oFile);
cout << "Puzzle Solved!" << endl;
oFile.close();
return;
}
else if (tempState.checkForSolve() != true && visitedPuzzleStateSet.find(tempState.getPuzzleID()) == visitedPuzzleStateSet.end()) {
puzzleQueue.push(tempState);
}
else {
cout << "have visited this state already" << endl;
system("pause");
}
}
}
}
}
else
oFile.close();
return;
}