Hola llevo dias calentandome la cabeza creando un programa que resuelva un sudoku a partir de un fichero...
Sobre la recolecta de informacion de la matriz etc.. todo es correcto pero a la hora de crear el bactraking me falla y ya nose donde tocar para que este me funcione.
Haber si me podeis ayudar. Gracias de antemano.
Main:
Código C++:
Ver original#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>
#include "solucio.h"
#include "solucionador.h"
using namespace std;
int n=9;
int main()
{
int **sudoku;
sudoku=new int*[9];
for(int i=0; i<9; i++){
sudoku[i]=new int[9];
}
//Inicializacion del tablero a cero:
for(int i=0;i<9;i++) {
for(int j=0;j<9;j++) {
sudoku[i][j]=0;
}
}
ifstream f_ent;
f_ent.open("matriz2.txt", ifstream:: in);
//Rellenamos la matriz con los valores del fichero.
int fil, col, valor;
while (!f_ent.eof()) {
f_ent >>fil;
f_ent >>col;
f_ent >>valor;
sudoku[fil-1][col-1]=valor;
}
f_ent.close();
//Mostrar Matriz por pantalla
cout<<"-------------"<< endl;
for(int i=0;i<9;i++) {
if(i==3 or i==6) cout<<"-------------"<< endl;
for(int j=0;j<9;j++) {
if(j==0 or j==3 or j==6) cout<<"|";
cout << sudoku[i][j];
if(j==8) cout<<"|";
}
cout <<" "<<endl;
}
cout<<"-------------"<< endl;
Solucio s(sudoku),sFinal;
Solucionador s1;
sFinal=s1.solucionar(s);
sFinal=s1.obtenirSolucio();
sFinal.MostrarSolucio();
return 0;
}
Clase solucionador donde hago el backtraking
Código C++:
Ver original#include <iostream>
#include <cstdlib>
#include <vector>
#include "solucionador.h"
using namespace std;
Solucionador::Solucionador(){
}
Solucio Solucionador::solucionar(Solucio & s){
sol=s;
solucioBona=s;
cert=false;
backtracking(s);
return(this->sol);
}
void Solucionador::backtracking(Solucio & s){
Iterador it=s.crearCandidats();
while(!it.fi() && !cert) {
if(s.acceptable(it)) {
s.anotarCandidat(it);
if(s.solucioCompleta()) {
cert=true;
solucioBona = s;
} else {
backtracking(s);
if (!cert){
s.desanotarCandidat();
}
}
}
it.seguent();
}
}
Solucio Solucionador::obtenirSolucio() const{
return(solucioBona);
}
bool Solucionador::getCert(){
return cert;
}
Clase para solucionarlo:
con los atributos:
bool usadosCuadrado[mida][mida];
bool usadosLinea[mida][mida];
bool usadosColumna[mida][mida];
int tauler[mida][mida];
bool EsPotModif[mida][mida];
Código C++:
Ver original#include <iostream>
#include <vector>
#include "solucio.h"
#include <cstdlib>
using namespace std;
Solucio::Solucio(){
}
Solucio::Solucio(int **sudoku){
int valor;
posicio=0;
for(int f=0; f<9; f++){
for(int c=0; c<9; c++){
tauler[f][c]=sudoku[f][c];
valor=tauler[f][c];
if(tauler[f][c] != 0){
usadosCuadrado[f/3*3+c/3][valor-1]=true;
usadosLinea[f][valor-1]=true;
usadosColumna[c][valor-1]=true;
EsPotModif[f][c]=false;
} else {
usadosCuadrado[f/3*3+c/3][valor-1]=false;
usadosLinea[f][valor-1]=false;
usadosColumna[c][valor-1]=false;
EsPotModif[f][c]=true;
}
}
}
}
Iterador Solucio::crearCandidats(){
return(Iterador());
}
bool Solucio::acceptable(Iterador it){
int f=getFila();
int c=getColumna();
return((!usadosCuadrado[f/3*3+c/3][it.actual()-1])&&(!usadosLinea[f][it.actual()-1])&&(!usadosColumna[c][it.actual()-1])&&(EsPotModif[f][c]));
}
void Solucio::anotarCandidat(Iterador it){
int f=getFila();
int c=getColumna();
if(EsPotModif[f][c]!=2) {
int valor=it.actual();
usadosCuadrado[f/3*3+c/3][valor-1]=true;
usadosLinea[f][valor-1]=true;
usadosColumna[c][valor-1]=true;
tauler[f][c]=it.actual();
}
posicio++;
}
bool Solucio::solucioCompleta(){
return(posicio==81);
}
void Solucio::desanotarCandidat(Iterador it){
int f=getFila();
int c=getColumna();
if(EsPotModif[f][c]!=2) {
int valor=it.actual();
usadosCuadrado[f/3*3+c/3][valor-1]=false;
usadosLinea[f][valor-1]=false;
usadosColumna[c][valor-1]=false;
tauler[f][c]=0;
}
posicio--;
}
int Solucio::contingut(){
return(tauler[getFila()][getColumna()]);
}
int Solucio::getFila()
{
int fila=posicio%9;
if(fila==0)
fila=9;
return (fila);
}
int Solucio::getColumna()
{
int col=(posicio/9)+1;
if(posicio%9==0)
col--;
return (col);
}
void Solucio::MostrarSolucio()
{
if(solucioCompleta()) {
cout <<"SOLUCIO Tauler"<<endl;
cout<<"-------------"<< endl;
for(int i=0;i<9;i++) {
if(i==3 or i==6) cout<<"-------------"<< endl;
for(int j=0;j<9;j++) {
if(j==0 or j==3 or j==6) cout<<"|";
cout << tauler[i][j];
if(j==8) cout<<"|";
}
cout <<" "<<endl;
}
} else {
cout <<"NO TE SOLUCIO"<<endl;
}
}
Y la clase de Candidatos:
Código C++:
Ver originalusing namespace std;
Iterador::Iterador(){
valor=1;
}
void Iterador::Crear()
{
valor=1;
}
void Iterador::seguent(){
valor++;
}
void Iterador::tornar() {
valor=1;
}
int Iterador::actual(){
return valor;
}
bool Iterador::fi(){
return (valor>9);
}