Skip to content

Instantly share code, notes, and snippets.

@danielSanchezQ
Created July 30, 2012 00:23
Show Gist options
  • Save danielSanchezQ/3202860 to your computer and use it in GitHub Desktop.
Save danielSanchezQ/3202860 to your computer and use it in GitHub Desktop.
Backtrack puzzle solve algorith
#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;
}
}
}
#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