Foros del Web » Programación para mayores de 30 ;) » C/C++ »

Resolucion de Sudoku

Estas en el tema de Resolucion de Sudoku en el foro de C/C++ en Foros del Web. 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 ...
  #1 (permalink)  
Antiguo 22/01/2012, 09:35
Avatar de mihina  
Fecha de Ingreso: mayo-2010
Ubicación: Girona
Mensajes: 32
Antigüedad: 14 años, 2 meses
Puntos: 1
Exclamación Resolucion de Sudoku

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
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cstdlib>
  4. #include <string>
  5. #include "solucio.h"
  6. #include "solucionador.h"
  7.  
  8. using namespace std;
  9.  
  10. int n=9;
  11.  
  12. int main()
  13. {
  14.     int **sudoku;
  15.     sudoku=new int*[9];
  16.     for(int i=0; i<9; i++){
  17.         sudoku[i]=new int[9];
  18.     }
  19.  
  20.     //Inicializacion del tablero a cero:
  21.     for(int i=0;i<9;i++) {
  22.         for(int j=0;j<9;j++) {
  23.             sudoku[i][j]=0;
  24.         }
  25.     }
  26.  
  27.     ifstream f_ent;
  28.     f_ent.open("matriz2.txt", ifstream:: in);
  29.  
  30.     //Rellenamos la matriz con los valores del fichero.
  31.     int fil, col, valor;
  32.     while (!f_ent.eof()) {
  33.             f_ent >>fil;
  34.             f_ent >>col;
  35.             f_ent >>valor;
  36.             sudoku[fil-1][col-1]=valor;
  37.         }
  38.     f_ent.close();
  39.  
  40.     //Mostrar Matriz por pantalla
  41.     cout<<"-------------"<< endl;
  42.     for(int i=0;i<9;i++) {
  43.         if(i==3 or i==6) cout<<"-------------"<< endl;
  44.  
  45.         for(int j=0;j<9;j++) {
  46.             if(j==0 or j==3 or j==6) cout<<"|";
  47.             cout << sudoku[i][j];
  48.             if(j==8) cout<<"|";
  49.         }
  50.         cout <<" "<<endl;
  51.     }
  52.     cout<<"-------------"<< endl;
  53.  
  54.  
  55.  
  56.     Solucio s(sudoku),sFinal;
  57.     Solucionador s1;
  58.     sFinal=s1.solucionar(s);
  59.  
  60.     sFinal=s1.obtenirSolucio();
  61.     sFinal.MostrarSolucio();
  62.  
  63.     return 0;
  64. }


Clase solucionador donde hago el backtraking
Código C++:
Ver original
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <vector>
  4. #include "solucionador.h"
  5.  
  6. using namespace std;
  7.  
  8.     Solucionador::Solucionador(){
  9.  
  10.     }
  11.  
  12.  
  13.     Solucio Solucionador::solucionar(Solucio & s){
  14.         sol=s;
  15.         solucioBona=s;
  16.  
  17.         cert=false;
  18.         backtracking(s);
  19.         return(this->sol);
  20.     }
  21.  
  22.     void Solucionador::backtracking(Solucio & s){
  23.  
  24.         Iterador it=s.crearCandidats();
  25.  
  26.         while(!it.fi() && !cert) {
  27.             if(s.acceptable(it)) {
  28.                 s.anotarCandidat(it);
  29.                 if(s.solucioCompleta()) {
  30.                     cert=true;
  31.                     solucioBona = s;
  32.                 } else {
  33.                     backtracking(s);
  34.                     if (!cert){
  35.                         s.desanotarCandidat();
  36.                     }
  37.                 }
  38.             }
  39.             it.seguent();
  40.         }
  41.     }
  42.  
  43.     Solucio Solucionador::obtenirSolucio() const{
  44.         return(solucioBona);
  45.  
  46.     }
  47.  
  48.     bool Solucionador::getCert(){
  49.         return cert;
  50.     }

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
  1. #include <iostream>
  2. #include <vector>
  3. #include "solucio.h"
  4. #include <cstdlib>
  5. using namespace std;
  6.  
  7.     Solucio::Solucio(){
  8.  
  9.     }
  10.  
  11.     Solucio::Solucio(int **sudoku){
  12.  
  13.         int valor;
  14.         posicio=0;
  15.  
  16.         for(int f=0; f<9; f++){
  17.             for(int c=0; c<9; c++){
  18.                 tauler[f][c]=sudoku[f][c];
  19.                 valor=tauler[f][c];
  20.                 if(tauler[f][c] != 0){
  21.                     usadosCuadrado[f/3*3+c/3][valor-1]=true;
  22.                     usadosLinea[f][valor-1]=true;
  23.                     usadosColumna[c][valor-1]=true;
  24.                     EsPotModif[f][c]=false;
  25.  
  26.                 } else {
  27.                     usadosCuadrado[f/3*3+c/3][valor-1]=false;
  28.                     usadosLinea[f][valor-1]=false;
  29.                     usadosColumna[c][valor-1]=false;
  30.                     EsPotModif[f][c]=true;
  31.                 }
  32.             }
  33.         }
  34.  
  35.     }
  36.  
  37.  
  38.     Iterador Solucio::crearCandidats(){
  39.         return(Iterador());
  40.     }
  41.  
  42.  
  43.     bool Solucio::acceptable(Iterador it){
  44.         int f=getFila();
  45.         int c=getColumna();
  46.  
  47.         return((!usadosCuadrado[f/3*3+c/3][it.actual()-1])&&(!usadosLinea[f][it.actual()-1])&&(!usadosColumna[c][it.actual()-1])&&(EsPotModif[f][c]));
  48.     }
  49.  
  50.  
  51.     void Solucio::anotarCandidat(Iterador it){
  52.  
  53.         int f=getFila();
  54.         int c=getColumna();
  55.  
  56.         if(EsPotModif[f][c]!=2) {
  57.  
  58.             int valor=it.actual();
  59.  
  60.             usadosCuadrado[f/3*3+c/3][valor-1]=true;
  61.             usadosLinea[f][valor-1]=true;
  62.             usadosColumna[c][valor-1]=true;
  63.             tauler[f][c]=it.actual();
  64.         }
  65.         posicio++;
  66.     }
  67.  
  68.  
  69.     bool Solucio::solucioCompleta(){
  70.         return(posicio==81);
  71.     }
  72.  
  73.  
  74.     void Solucio::desanotarCandidat(Iterador it){
  75.         int f=getFila();
  76.         int c=getColumna();
  77.  
  78.         if(EsPotModif[f][c]!=2) {
  79.  
  80.             int valor=it.actual();
  81.  
  82.             usadosCuadrado[f/3*3+c/3][valor-1]=false;
  83.             usadosLinea[f][valor-1]=false;
  84.             usadosColumna[c][valor-1]=false;
  85.             tauler[f][c]=0;
  86.         }
  87.         posicio--;
  88.     }
  89.  
  90.  
  91.     int Solucio::contingut(){
  92.         return(tauler[getFila()][getColumna()]);
  93.     }
  94.  
  95.     int Solucio::getFila()
  96.     {
  97.         int fila=posicio%9;
  98.  
  99.         if(fila==0)
  100.             fila=9;
  101.  
  102.         return (fila);
  103.     }
  104.  
  105.  
  106.     int Solucio::getColumna()
  107.     {
  108.         int col=(posicio/9)+1;
  109.  
  110.        if(posicio%9==0)
  111.             col--;
  112.  
  113.         return (col);
  114.     }
  115.  
  116.  
  117. void Solucio::MostrarSolucio()
  118. {
  119.     if(solucioCompleta()) {
  120.         cout <<"SOLUCIO Tauler"<<endl;
  121.         cout<<"-------------"<< endl;
  122.         for(int i=0;i<9;i++) {
  123.             if(i==3 or i==6) cout<<"-------------"<< endl;
  124.  
  125.             for(int j=0;j<9;j++) {
  126.                 if(j==0 or j==3 or j==6) cout<<"|";
  127.                 cout << tauler[i][j];
  128.                 if(j==8) cout<<"|";
  129.             }
  130.             cout <<" "<<endl;
  131.         }
  132.     } else {
  133.         cout <<"NO TE SOLUCIO"<<endl;
  134.     }
  135. }

Y la clase de Candidatos:
Código C++:
Ver original
  1. using namespace std;
  2.  
  3.     Iterador::Iterador(){
  4.         valor=1;
  5.     }
  6.  
  7.     void Iterador::Crear()
  8.     {
  9.         valor=1;
  10.     }
  11.  
  12.  
  13.     void Iterador::seguent(){
  14.         valor++;
  15.     }
  16.  
  17.     void Iterador::tornar() {
  18.         valor=1;
  19.     }
  20.  
  21.  
  22.     int Iterador::actual(){
  23.         return valor;
  24.     }
  25.  
  26.  
  27.     bool Iterador::fi(){
  28.         return (valor>9);
  29.     }

Etiquetas: clase, fichero, funcion, matriz, programa, string, sudoku
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 23:25.