Created
July 30, 2012 00:23
-
-
Save danielSanchezQ/3202860 to your computer and use it in GitHub Desktop.
Backtrack puzzle solve algorith
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <fstream> | |
#include "puzzle.h" | |
using namespace std; | |
Puzzle_game::Puzzle_game() | |
{ | |
Solve = false; | |
for(int i = 0; i < 4; i++) | |
for(int e = 0; e < 4; e++) | |
{ | |
Try_solution[i][e] = 0; | |
} | |
load_solution("first_solution.txt"); | |
for(int i = 0; i < 16; i++) | |
Piezas.push_back(i+1); | |
m_Y = 0; | |
m_E = 0; | |
//print_Solution(); | |
} | |
void Puzzle_game::load_solution(const string name) | |
{ | |
fstream myfile; | |
myfile.open(name); | |
int i = 0; | |
int e = 0; | |
while(!myfile.eof()) | |
{ | |
if(e == 4) | |
{ | |
e = 0; | |
i++; | |
} | |
int chr = ' '; | |
int tmp; | |
myfile>>tmp; | |
if(tmp != chr) | |
Solution[i][e] = tmp; | |
e++; | |
} | |
} | |
void Puzzle_game::print_Solution() | |
{ | |
cout<<"Real solution"<<endl; | |
for(int i = 0; i < 4; i++) | |
for(int e = 0; e < 4; e++) | |
{ | |
cout<<Solution[i][e]<<" "; | |
if(e == 3) | |
cout<<endl; | |
} | |
} | |
void Puzzle_game::print_Try_solution() | |
{ | |
cout<<"Tryed solution"<<endl; | |
for(int i = 0; i < 4; i++) | |
for(int e = 0; e < 4; e++) | |
{ | |
cout<<Try_solution[i][e]<<" "; | |
if(e == 3) | |
cout<<endl; | |
} | |
} | |
void Puzzle_game::solve(vector<int> &piezas, int &Y, int &E) | |
{ | |
int y = Y; | |
int e = E; | |
while(Solve != true) | |
{ | |
if(e == 4) | |
{ | |
e = 0; | |
y++; | |
} | |
for(int i = 0; i < piezas.size(); i++) | |
{ | |
vector<int> copia = piezas; | |
int tmpY = y; | |
int tmpE = e; | |
if(piezas[i] == Solution[y][e]) | |
{ | |
Try_solution[y][e] = piezas[i]; | |
piezas.erase(piezas.begin()+i); | |
solve(piezas,y,e); | |
if(piezas.size() == 0) | |
{ | |
Solve = true; | |
//print_Solution(); | |
//print_Try_solution(); | |
cout<<"Puzzle solve"<<endl; | |
break; | |
} | |
if(Solve == true) | |
{ | |
break; | |
} | |
} | |
else if(piezas.size() > 0) | |
{ | |
piezas = copia; | |
y = tmpY; | |
e = tmpE; | |
} | |
} | |
e++; | |
if((e > 3 && y > 3) && Solve == false) | |
{ | |
cout<<"Imposible to solve....sorry..."<<endl; | |
break; | |
} | |
} | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <string> | |
#include <vector> | |
using namespace std; | |
class Puzzle_game | |
{ | |
private: | |
bool Solve; | |
int Solution[4][4]; | |
int Try_solution[4][4]; | |
public: | |
vector<int> Piezas; | |
int m_Y; | |
int m_E; | |
Puzzle_game(); | |
void load_solution(const string name); | |
void solve(vector<int> &piezas, int &Y, int &E); | |
void print_Solution(); | |
void print_Try_solution(); | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment