Versión para imprimir
Buenas noches.
Me pregunto si alguno sabrá o tendrá idea alguna de que forma puedo hacer que un sudoku me diga rápidamente si tiene o no tiene solución.
Hay muchas formas de solucionar el sudoku. Lo he resuelto utilizando backtracking, lo malo es que hay algunos casos en los cuales se demora demasiado en informarme de que no encontró solución.
Creo que todos los sudokus tienen solución. -.-"
Bueno la unica solucion es que la resuelvas y si no te sale bueno pues.Cita:
Iniciado por Jose_Soft
dale al search en internet ahi encuentras lo que quieras es tu gran amigo
:P
No todos los sudokus tienen solucion, un numero mal puesto y ya no se cumplen todas las condiciones.Cita:
Iniciado por LarryLurex
Trata de leer nuevamente su post, esta preguntando una manera de determinar si un sudoku propuesto tiene solucion.Cita:
Iniciado por undert4ker_k4ne!
Un amigo armo un codigo con una funcion recursiva para solucionar un sudoku, es un codigo muy rapido, voy a ver si lo tiene por ahi y lo posteo.
Gracias ojalá lo encuentres =D
Mi restricción actual fue colocar como máximo de intentos 15 millones. Número excesivamente elevado me dirás. Originalmente le puse 500 000 pero me encontre con un sudoku en internet que para mi mala suerte (o para darme cuenta) se resolvió recién en el backtracking 10 millones y pico. Con los 15 millones hasta ahorita o he resuelto un tablero o mostrado que no tiene solución. A por cierto...en realidad mi interés por esta restricción es que programé el sudoku samurai y en algunas esquinas compartidas (sobre todo la última) se demora demasiado (al menos lo logra!!!) en decirme que no encuentra solución (como 3 minutos explotando mis pobres dos nucleos de procesador =( )
tal vez seria mejor que hagas lo que toda persona sana haria...
puedes consultar la "webdelprogramador" "conclase", el "rincondelc"; cuando posteaba en yahoo.answers habia mucha gente que tambien pedia lo mismo en la seccion de programacion, puede q alguno le hayan dado el codigo del programa. pero si lo que tu kieres es solucionar sudokus, creo q deberia empezar por validar el sudoku, es decir ver primero que tiene solucion unica!, eso es todo un jaraneo complejo, suerte!.
no te olvides de la web del programador es una pag donde te podrian dar, sino la restuesta, una buena asesoria en sus foros *_*
- import java.io.*;
- class Sudoku
- {
- int SQN = 3;
- int N = 9;
- int celda[][] = new int [N][N];
- boolean sector[][][] = new boolean [SQN][SQN][N+1];
- boolean RESUELTO;
- int celda_actual;
- public Sudoku ()
- {
- /* Inicializamos el sudoku con todo a cero */
- int i, j, k;
- celda_actual = 0;
- RESUELTO = false;
- for (i=0; i<9; i++)
- for (j=0; j<9; j++)
- celda [i][j] = 0;
- for (i=0; i<3; i++)
- for(j=0; j<3; j++)
- for(k=1; k<=9; k++)
- sector[i][j][k] = false;
- }
- public int getCelda(int i, int j)
- {
- return celda[i][j];
- }
- public void setCelda(int i, int j, int value)
- {
- celda[i][j] = value;
- }
- public boolean isResuelto()
- {
- return RESUELTO;
- }
- public void reset()
- {
- int i, j, k;
- celda_actual = 0;
- RESUELTO = false;
- for (i=0; i<9; i++)
- for (j=0; j<9; j++)
- celda [i][j] = 0;
- for (i=0; i<3; i++)
- for(j=0; j<3; j++)
- for(k=1; k<=9; k++)
- sector[i][j][k] = false;
- }
- public void muestra ()
- {
- int i, j;
- int h;
- System.out.printf("\n\n");
- for (i=0;i<N;i++)
- {
- if ((i%SQN == 0)&&(i!=0))
- {
- System.out.printf("\n -");
- System.out.printf("--------|------------|----------");
- System.out.printf("\n");
- }
- else
- System.out.printf("\n");
- for (j=0;j<N;j++)
- if ((j%SQN==0)&&(j!=0))
- {
- System.out.printf(" |%3d ",celda[i][j]);
- }
- else
- {
- System.out.printf("%3d", celda[i][j]);
- }
- }
- System.out.printf("\n\n");
- }
- public void resuelve ()
- {
- /* Comprueba que es resoluble, ajusta los sectores y lo resuelve */
- if (checkIntegridad())
- {
- resuelve (0);
- }
- else
- {
- RESUELTO = false;
- }
- }
- public boolean checkIntegridad ()
- {
- int i, j, k;
- boolean VALIDO = true;
- for(i=0; i<N; i++)
- {
- for(j=0; j<N; j++)
- {
- if (celda[i][j]!=0)
- {
- /* Veamos que no hay un número igual en toda la columna o fila*/
- for(k=0; k<N; k++)
- {
- if( ((k!=j)&&(celda[i][k]==celda[i][j])) || ((k!=i)&&(celda[k][j]==celda[i][j])) )
- {
- VALIDO = false; System.out.printf("\nMalo 1 en (%d,%d) k = %d", i,j,k);
- }
- }
- if(sector[i/SQN][j/SQN][celda[i][j]] == true) // ya estaba en el sector de antes
- {
- VALIDO = false; System.out.printf("\nMalo 2 en (%d, %d) ", i,j);
- }
- sector[i/SQN][j/SQN][celda[i][j]] = true;
- }
- }
- }
- return VALIDO;
- }
- public void resuelve (int celda_actual)
- {
- int i, j, n;
- boolean LEGAL;
- boolean VACIA = false;
- boolean ULTIMA = true;
- i = celda_actual/N;
- j = celda_actual%N;
- if (celda_actual < (N*N)-1)
- ULTIMA=false;
- if (celda[i][j] == 0)
- VACIA = true;
- n=0;
- if (VACIA)
- {
- do
- {
- n++;
- RESUELTO = false;
- LEGAL = true;
- /* ¿Es legal n? */
- for(int k=0; k<N; k++)
- if(celda[i][k]==n || celda[k][j]==n)
- LEGAL = false;
- if (sector[i/SQN][j/SQN][n]==true)
- LEGAL = false;
- if (LEGAL)
- {
- /* Escribimos el número en la casilla */
- celda[i][j] = n;
- sector[i/SQN][j/SQN][n] = true;
- /* Si era la última, hemos acabado */
- if (ULTIMA)
- RESUELTO = true;
- else // No es la última
- {
- /* Si no era la última, hay que seguir */
- resuelve(celda_actual+1);
- if (!RESUELTO) /* Si no ha tenido éxito, hay que borrar esta casilla y probar otra cosa */
- {
- celda[i][j] = 0;
- sector[i/SQN][j/SQN][n] = false;
- }
- }
- }
- }while((RESUELTO==false)&&(n<N));
- }
- else // No está vacía
- {
- if(ULTIMA)
- RESUELTO = true;
- else
- {
- resuelve(celda_actual+1);
- }
- }
- }
- }
Cita:
Iniciado por Fonchi
y en q programa de java copio y pego eso?? netbeans o Jcreator?
si me ekivoco corrijanme :$