Club Delphi  
    FTP   CCD     Buscar   Trucos   Trabajo   Foros

Retroceder   Foros Club Delphi > Principal > Varios
Registrarse FAQ Miembros Calendario Guía de estilo Buscar Temas de Hoy Marcar Foros Como Leídos

Grupo de Teaming del ClubDelphi

Respuesta
 
Herramientas Buscar en Tema Desplegado
  #1  
Antiguo 11-12-2006
metalfox6383 metalfox6383 is offline
Miembro
 
Registrado: jul 2005
Posts: 97
Poder: 19
metalfox6383 Va por buen camino
Question 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.
Responder Con Cita
  #2  
Antiguo 11-12-2006
Avatar de Bicho
[Bicho] Bicho is offline
Miembro Premium
 
Registrado: jul 2003
Ubicación: Inca - Mallorca
Posts: 1.776
Poder: 22
Bicho Va por buen camino
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
Responder Con Cita
  #3  
Antiguo 11-12-2006
metalfox6383 metalfox6383 is offline
Miembro
 
Registrado: jul 2005
Posts: 97
Poder: 19
metalfox6383 Va por buen camino
Interesante. Voy a estudiar esos códigos, aunque espero cumplan con las debidas reglas para que los Sudokus creados puedanser resueltos.

Gracias.
Responder Con Cita
  #4  
Antiguo 11-12-2006
Avatar de seoane
[seoane] seoane is offline
Miembro Premium
 
Registrado: feb 2004
Ubicación: A Coruña, España
Posts: 3.717
Poder: 24
seoane Va por buen camino
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
Responder Con Cita
  #5  
Antiguo 11-12-2006
metalfox6383 metalfox6383 is offline
Miembro
 
Registrado: jul 2005
Posts: 97
Poder: 19
metalfox6383 Va por buen camino
¿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.

Última edición por metalfox6383 fecha: 11-12-2006 a las 18:46:32.
Responder Con Cita
  #6  
Antiguo 11-12-2006
Avatar de seoane
[seoane] seoane is offline
Miembro Premium
 
Registrado: feb 2004
Ubicación: A Coruña, España
Posts: 3.717
Poder: 24
seoane Va por buen camino
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

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.

Caramba como me he liado.
Responder Con Cita
  #7  
Antiguo 11-12-2006
Avatar de seoane
[seoane] seoane is offline
Miembro Premium
 
Registrado: feb 2004
Ubicación: A Coruña, España
Posts: 3.717
Poder: 24
seoane Va por buen camino
Cita:
Empezado por metalfox6383
He buscado con todas las frases posibles pero no he tenido éxito.
Estas bromeando verdad.

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.
Archivos Adjuntos
Tipo de Archivo: zip Sudoku.zip (19,2 KB, 301 visitas)
Responder Con Cita
  #8  
Antiguo 11-12-2006
Avatar de Neftali [Germán.Estévez]
Neftali [Germán.Estévez] Neftali [Germán.Estévez] is offline
[becario]
 
Registrado: jul 2004
Ubicación: Barcelona - España
Posts: 18.233
Poder: 10
Neftali [Germán.Estévez] Es un diamante en brutoNeftali [Germán.Estévez] Es un diamante en brutoNeftali [Germán.Estévez] Es un diamante en bruto
Una busqueda sencilla en los foros y llegarás aquí.
Revisa los ejemplos.

EDITO: ¡¡Qué lento soy....!!!
__________________
Germán Estévez => Web/Blog
Guía de estilo, Guía alternativa
Utiliza TAG's en tus mensajes.
Contactar con el Clubdelphi

P.D: Más tiempo dedicado a la pregunta=Mejores respuestas.
Responder Con Cita
  #9  
Antiguo 11-12-2006
Avatar de Bicho
[Bicho] Bicho is offline
Miembro Premium
 
Registrado: jul 2003
Ubicación: Inca - Mallorca
Posts: 1.776
Poder: 22
Bicho Va por buen camino
JAJAJAJA

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?

Saludos
Responder Con Cita
Respuesta


Herramientas Buscar en Tema
Buscar en Tema:

Búsqueda Avanzada
Desplegado

Normas de Publicación
no Puedes crear nuevos temas
no Puedes responder a temas
no Puedes adjuntar archivos
no Puedes editar tus mensajes

El código vB está habilitado
Las caritas están habilitado
Código [IMG] está habilitado
Código HTML está deshabilitado
Saltar a Foro

Temas Similares
Tema Autor Foro Respuestas Último mensaje
crear instalador, ejecutar al iniciar i crear desinstalador vivamotos C++ Builder 1 25-08-2006 15:13:01
crear una dll chete Varios 13 14-01-2006 02:24:31
Crear un pdf en C++ lomeli_cl C++ Builder 2 01-05-2004 03:47:03
Crear BD cpal Firebird e Interbase 5 08-03-2004 17:11:01
crear una dll Rafa Varios 3 27-01-2004 20:09:38


La franja horaria es GMT +2. Ahora son las 17:02:25.


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
Copyright 1996-2007 Club Delphi