Resolucion de Sudoku

[mihina]

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++:

#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++:

#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++:

#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++:

using 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);
    }