Sudoku

[ssalas]

Hola alguien me puede ayudar en las validaciones de el juego sudoku es que no se como seria de implementar el algoritmo para que realize todas las validaciones posibles para poder generar este juego.

Alguien sabe una logica para poder resolver este juego rapidamente, es que necesito realizar el juego para una tarea

[latindeveloper]

En esta direccion puedes encontrar la implementacion de la solucion.

http://www.sudokusolver.co.uk/

[nidll]

tengo un trabajo para una clase de .net, mi proyecto fue hacer un sudoku... por muchas razones no he podido hacerlo pues llevo tambien un curso de progra objetos, queria pedirte el favor de que si fuera posible me ayudaras con el programa pues no tengo ni la minima idea de como hacerlo....me lo podrias prestar??? porfa!!!! es urgente!!!!

[nickyjairam]

para hacer el programa tienes q dominar la técnica de backtraking. El backtracking consiste en hacer llamadas al propio procedimiento y ir probando con distintos valores, retrocediendo si hace falta, hasta encontrar el valor adecuado.

Para hacer un sudoku primero generas un tablero con todas las soluciones y despues a la hora de presentarselo al usuario eliminas ciertas soluciones, que kedaran guardadas en un tablero auxiliar para corroborar si esta bien o no.

Tendrás que hacer por backtracking un procedimiento que genere las soluciones. Empezamos generando valores por ejemplo aleatorios para cada una de las filas.

En el Tablero.h

Código: Seleccionar todo

class Tablero {
private:
   int _tablero[9][9];
public:
   Tablero();
   ~Tablero();
   bool GenerarSoluciones(int x, int y, int valor);
   int GeneraValorAleatorio();
   ...
};


En el Tablero.cpp

Código: Seleccionar todo



bool GenerarSoluciones(int x, int y, int valor){
   // Aqui estableces condiciónes de parada o de vuelta atras
   Si valor ya esta en la fila entonces vuelta atras
   Si valor ya esta en la columna entonces vuelta atras
   Si valor ya esta en el recuadro de 3x3 vuelta atras
   Si no entonces
   GenerarSoluciones(x + 1, y, NuevoValor);
   GenerarSoluciones(x, y + 1, NuevoValor);
 

El backtracking es una técnica muy dificil de implementar, si no tienes mucha idea, te aconsejo q primero busques ejemplo más sencillos antes de ponerte a hacer este programa, pq éste precisamente es muy complejo.

Por cierto, hay otros algoritmos como por ejemplo algoritmos las vegas que a veces sustituyen a los del backtracking por su simplicidad. Consiste en hacer lo siguiente:
para todo el tablero genera valores aleatorios hasta que se cumplan las condiciones de integridad. Las condiciones de integridad son:
Que el valor no este en la misma fila
que el valor no este en la misma columna
que el valor no este en el recuadro 3x3.

Esto de generar valores aleatorios se conjuga con cálculos de probabilidades estadísticas para intentar cumplir más rápido con las condiciones de integridad. Por supuesto esto tardaría muchisimo, la CPU emplearia mucho tiempo en conseguir la combinación correcto así que no es muy recomendable a menos que sepas manejar bien probabilidades estadísticas.

Sin duda, la mejor solución es la del backtracking. Y sobre todo, no pierdas la esperanza, que al final reconforta. Ánimo y suerte