Foros Club Delphi

Foros Club Delphi (https://www.clubdelphi.com/foros/index.php)
-   Varios (https://www.clubdelphi.com/foros/forumdisplay.php?f=11)
-   -   Crear Sudoku. (https://www.clubdelphi.com/foros/showthread.php?t=38319)

metalfox6383 11-12-2006 18:14:07

Crear Sudoku.
 
Hola:

He resuelto muchos Sudokus y ahora quisiera hacer un programa que los cree. ¿Alguien conoce el algoritmo para crear Sudokus para todos los niveles de dificultad? He buscado con todas las frases posibles pero no he tenido éxito.

Gracias.

Bicho 11-12-2006 18:26:53

Hola, pues no sé, si aquí habrás buscado o no, pero no era tan difícil. Aquí el amigo Domingo Seoane, empezaba despuntarse con sus numerosísimos ejemplos de código.

Espero te sirva.

Saludos

seoane 11-12-2006 18:28:59

1 Archivos Adjunto(s)
Cita:

Empezado por metalfox6383
He buscado con todas las frases posibles pero no he tenido éxito.

:eek: Estas bromeando verdad.

:D Probaste a buscar la palabra Sudoku
http://www.clubdelphi.com/foros/sear...earchid=583607

Porque a mi me salen un par de hilos en los que se trata el tema de los Sudokus. Por ejemplo esto dos mios.
http://www.clubdelphi.com/foros/showthread.php?t=32663
http://www.clubdelphi.com/foros/show...11&postcount=5

El algoritmo que utilizo para generar los Sudokus, los divide en 2 niveles de dificultad, los fáciles, en los que todos los números resultan obvios, y los difíciles, donde algunos números no resultan obvios y hay que probar con varios números. Ignoro si existe algún tipo de clasificación estándar para los sudokus en su nivel de dificultad, si es así explícalo aquí e intentaremos buscar un algoritmo que se ajuste a esa norma.

Aprovecho para subir, la ultima versión. Ahora se pueden imprimir los sudokus, e hice un par de cambios en los menús.

Neftali [Germán.Estévez] 11-12-2006 18:32:03

Una busqueda sencilla en los foros y llegarás aquí.
Revisa los ejemplos.

EDITO: ¡¡Qué lento soy....!!!

Bicho 11-12-2006 18:34:30

JAJAJAJA :D :D :D

Ala quéjate, tienes el mismo hilo por triplicado!!!
Unos que son lentos y otros que se enrollan más que...
Buen rollo. Por cierto, no pienso hacer comentarios al respecto sobre marcadores, que luego la liamos, eh? :D

Saludos

metalfox6383 11-12-2006 18:35:32

Interesante. Voy a estudiar esos códigos, aunque espero cumplan con las debidas reglas para que los Sudokus creados puedanser resueltos.

Gracias.

seoane 11-12-2006 18:39:00

Cita:

Empezado por metalfox6383
Interesante. Voy a estudiar esos códigos, aunque espero cumplan con las debidas reglas para que los Sudokus creados puedanser resueltos.

Hombre, es difícil que no se puedan resolver. Teniendo en cuenta que parto de un Sudoku resuelto y voy sacando números ;)

metalfox6383 11-12-2006 18:40:50

¿Qué criterio has tomado para saber qué número sacar y qué otro dejar? El crear el tablero complero no hay problema, mi problema parte desde saber cuál de los números extraer y cuál dejarlos escritos, cuántos de ellos debe ser como máximo.

seoane 11-12-2006 19:04:09

Si te parece bien, vamos a poner un poco de código. Para resumir partimos de los siguiente:

Código:

El tipo TTablero es una matriz de 9x9
La función Valido nos dice si un numero, en esa posición, cumple con las reglas del Sudoku.
La función Obvio nos devuelve el único numero que puede ocupar esa posición, respetando las reglas, o 0 si puede haber mas de uno.
La función Resolver, resuelve el sudoku usando la estrategia "Backtracking"

El codigo, para generar Sudokus es el siguiente:
Código Delphi [-]
procedure GenerarTablero(var Tablero: TTablero; Dificultad: Integer);
var
  i,j,k,l: integer;
begin
  FillChar(Tablero,Sizeof(Tablero),0);
  Randomize;
  i:= 0;
  while i < NUM_COLUMNAS do
  begin
    j:= Random(9)+1;
    if Valido(Tablero, i, 0, j) then
    begin
      Tablero[i,0]:= j;
      inc(i)
    end;
  end;
  Resolver(Tablero);
  k:= 0;
  // Quitamos algunos obvios
  while k < 30 do
  begin
    i:= Random(NUM_COLUMNAS);
    j:= Random(NUM_FILAS);
    if Tablero[i,j] <> 0 then
    begin
      l:= Tablero[i,j];
      Tablero[i,j]:= 0;
      if Obvio(Tablero,i,j)>0 then
        inc(k)
      else
        Tablero[i,j]:= l;
    end;
  end;
  k:= 0;
  // Quitamos algunos que no son obvios
  while k < Dificultad do
  begin
    i:= Random(NUM_COLUMNAS);
    j:= Random(NUM_FILAS);
    if Tablero[i,j] <> 0 then
    begin
      l:= Tablero[i,j];
      Tablero[i,j]:= 0;
      if Obvio(Tablero,i,j)=0 then
        inc(k)
      else
        Tablero[i,j]:= l;
    end;
  end;
end;

Como ves primero rellenamos la primera fila del tablero con números del 0 al 9 de forma aleatoria pero respetando las normas a la hora de su colocación. Entonces mandamos el tablero a resolver, esto nos devuelve un tablero completamente lleno. Ahora es cuando empezamos a quitar números, primero quitamos números Obvios, es decir, solo quitamos números que se van a poder averiguar aplicando las normas. No se cuantos exactamente podemos quitar, pero por experiencia no muchos mas de 30, seguro que si buscas por internet encuentras algún matemático que te diga el numero exacto :D

Después de todo lo anterior tenemos un Sudoku, que con solo aplicar rigurosamente las normas puede ser resuelto. Para añadirle "dificultad", quitamos un par de números "no Obvios", de esta manera obligamos al jugador a aplicar el método de prueba y error para resolver el Sudoku, teniendo incluso que volver sobre sus pasos para resolverlo. El numero de "no Obvios" se lo paso como parámetro a la función, pudiendo así con una dificultad 0 crear Sudokus en los que la resolución es Obvia y no hay nunca que retroceder, si se aplican bien las reglas.

:D Caramba como me he liado.

metalfox6383 11-12-2006 19:26:08

Clarísimo. Gracias. Empezaré con mi propio programa.

seoane 11-12-2006 21:22:22

Cita:

Empezado por metalfox6383
Clarísimo. Gracias. Empezaré con mi propio programa.

No se si lo dije antes, pero todo el código que publico en el foro puede ser usado por cualquiera, en sus propias aplicaciones si le resulta de utilidad, sin ninguna restricción (aunque una mención de mi nombre nunca esta demás :p ). Así que si quieres usar todo o parte del código de mi programa de Sudoku, puedes hacerlo sin problemas.


La franja horaria es GMT +2. Ahora son las 18:32:43.

Powered by vBulletin® Version 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Traducción al castellano por el equipo de moderadores del Club Delphi