Resultados 1 al 8 de 8

Restricción Sudoku (programación)

Esta es una discusión para el tema Restricción Sudoku (programación) en el foro Off-Topic, bajo la categoría Temas de Interes General; Buenas noches. Me pregunto si alguno sabrá o tendrá idea alguna de que forma puedo hacer que un sudoku me ...
Página: 1


  1. #1
    Member Avatar de Jose_Soft
    Fecha de ingreso
    18 nov, 07
    Ubicación
    Perú
    Mensajes
    10

    Predeterminado Restricción Sudoku (programación)

    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.

  2. #2
    Senior Member Avatar de LarryLurex
    Fecha de ingreso
    05 feb, 07
    Ubicación
    EN mi casa
    Mensajes
    197

    Predeterminado Re: Restricción Sudoku (programación)

    Creo que todos los sudokus tienen solución. -.-"

  3. #3
    Senior Member Avatar de undert4ker_k4ne!
    Fecha de ingreso
    02 abr, 05
    Ubicación
    Santa Anita - Lima
    Mensajes
    138

    Thumbs down Re: Restricción Sudoku (programación)

    Cita Iniciado por Jose_Soft Ver mensaje
    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.
    Bueno la unica solucion es que la resuelvas y si no te sale bueno pues.
    dale al search en internet ahi encuentras lo que quieras es tu gran amigo
    :P
    Los ejércitos no están hechos para la paz si no para el triunfante ejercicio de la guerra.
    Cuando se inicia y desencadena una guerra lo que importa no es tener la razón sino conseguir la victoria.
    JODG

  4. #4
    Planet Express Staff Avatar de lmchv
    Fecha de ingreso
    07 feb, 04
    Ubicación
    Lima - Miraflores
    Mensajes
    6,733

    Predeterminado Re: Restricción Sudoku (programación)

    Cita Iniciado por LarryLurex Ver mensaje
    Creo que todos los sudokus tienen solución. -.-"
    No todos los sudokus tienen solucion, un numero mal puesto y ya no se cumplen todas las condiciones.

    Cita Iniciado por undert4ker_k4ne! Ver mensaje
    Bueno la unica solucion es que la resuelvas y si no te sale bueno pues.
    dale al search en internet ahi encuentras lo que quieras es tu gran amigo
    :P
    Trata de leer nuevamente su post, esta preguntando una manera de determinar si un sudoku propuesto tiene solucion.

    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.
    BEHEMOTH (Desktop): Asus Sabertooth X99 | Intel Core i7 5930K + Corsair Hydro H110 | Kingston 32GB DDR4-2400 | Dell 2715Q 27" 4K | ASUS Strix Geforce GTX1080 8GB | Cooler Master Cosmos 2 + Thermaltake Toughpower 1200W | Sound Blaster Z + Logitech Z-5500 + CM Storm Sirus | Logitech G105 + Logitech G700S + Gigabyte Krypton | Samsung 950Pro 512GB NVMe M2 + 2 x Samsung 850Pro 512GB SSD RAID0 + 2 x Western Digital Black 1TB RAID0 | Sony BD-ROM + LG DVD-RAM DL | Windows 10 Pro 64bits
    Charquito (Desktop): Gigabyte GA-Z97X Gaming GT | Intel Core i7 4790K + Corsair Hydro H100 | Corsair 16GB DDR3-1600 | Dell U2713HM 27" | 2 x XFX Radeon R9-290X Black Edition 4GB Crossfire | Cooler Master Cosmos 1000 + Thermaltake SP-850M | Microsoft Reclusa + Microsoft Sculpt | GSkill Phoenix 120GB SSD + Seagate 500GB | Windows 10 Pro 64bits
    KRAKEN (Laptop): MSI GT70 0NE-446US | Intel Core i7 3630QM | 16GB DDR3-1600 | nVidia Geforce GTX680M 4GB @ 1920x1080 17" | 2 x mSATA 128GB SSD RAID0 + 750GB 7200RPM SATA3 | Logitech G700 + Func F-10R | Bluray burner | Windows 10 Pro 64bits I'm always watching!

  5. #5
    Member Avatar de Jose_Soft
    Fecha de ingreso
    18 nov, 07
    Ubicación
    Perú
    Mensajes
    10

    Predeterminado Re: Restricción Sudoku (programación)

    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 =( )

  6. #6
    Senior Member Avatar de tomas1251
    Fecha de ingreso
    01 mar, 06
    Ubicación
    UNi-FIIS
    Mensajes
    591

    Predeterminado Re: Restricción Sudoku (programación)

    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 *_*

    MAPLEando pasa mis dias MAPLEando....
    No te concideras un bruto?? -> zuhey.ok.pe

  7. #7
    Member
    Fecha de ingreso
    18 feb, 07
    Mensajes
    12

    Predeterminado Re: Restricción Sudoku (programación)

    1. import java.io.*;
    2. class Sudoku
    3. {
    4. int SQN = 3;
    5. int N = 9;
    6. int celda[][] = new int [N][N];
    7. boolean sector[][][] = new boolean [SQN][SQN][N+1];
    8. boolean RESUELTO;
    9. int celda_actual;
    10. public Sudoku ()
    11. {
    12. /* Inicializamos el sudoku con todo a cero */
    13. int i, j, k;
    14. celda_actual = 0;
    15. RESUELTO = false;
    16. for (i=0; i<9; i++)
    17. for (j=0; j<9; j++)
    18. celda [i][j] = 0;
    19. for (i=0; i<3; i++)
    20. for(j=0; j<3; j++)
    21. for(k=1; k<=9; k++)
    22. sector[i][j][k] = false;
    23. }
    24. public int getCelda(int i, int j)
    25. {
    26. return celda[i][j];
    27. }
    28. public void setCelda(int i, int j, int value)
    29. {
    30. celda[i][j] = value;
    31. }
    32. public boolean isResuelto()
    33. {
    34. return RESUELTO;
    35. }
    36. public void reset()
    37. {
    38. int i, j, k;
    39. celda_actual = 0;
    40. RESUELTO = false;
    41. for (i=0; i<9; i++)
    42. for (j=0; j<9; j++)
    43. celda [i][j] = 0;
    44. for (i=0; i<3; i++)
    45. for(j=0; j<3; j++)
    46. for(k=1; k<=9; k++)
    47. sector[i][j][k] = false;
    48. }
    49. public void muestra ()
    50. {
    51. int i, j;
    52. int h;
    53. System.out.printf("\n\n");
    54. for (i=0;i<N;i++)
    55. {
    56. if ((i%SQN == 0)&&(i!=0))
    57. {
    58. System.out.printf("\n -");
    59. System.out.printf("--------|------------|----------");
    60. System.out.printf("\n");
    61. }
    62. else
    63. System.out.printf("\n");
    64. for (j=0;j<N;j++)
    65. if ((j%SQN==0)&&(j!=0))
    66. {
    67. System.out.printf(" |%3d ",celda[i][j]);
    68. }
    69. else
    70. {
    71. System.out.printf("%3d", celda[i][j]);
    72. }
    73. }
    74. System.out.printf("\n\n");
    75. }
    76. public void resuelve ()
    77. {
    78. /* Comprueba que es resoluble, ajusta los sectores y lo resuelve */
    79. if (checkIntegridad())
    80. {
    81. resuelve (0);
    82. }
    83. else
    84. {
    85. RESUELTO = false;
    86. }
    87. }
    88. public boolean checkIntegridad ()
    89. {
    90. int i, j, k;
    91. boolean VALIDO = true;
    92. for(i=0; i<N; i++)
    93. {
    94. for(j=0; j<N; j++)
    95. {
    96. if (celda[i][j]!=0)
    97. {
    98. /* Veamos que no hay un número igual en toda la columna o fila*/
    99. for(k=0; k<N; k++)
    100. {
    101. if( ((k!=j)&&(celda[i][k]==celda[i][j])) || ((k!=i)&&(celda[k][j]==celda[i][j])) )
    102. {
    103. VALIDO = false; System.out.printf("\nMalo 1 en (%d,%d) k = %d", i,j,k);
    104. }
    105. }
    106. if(sector[i/SQN][j/SQN][celda[i][j]] == true) // ya estaba en el sector de antes
    107. {
    108. VALIDO = false; System.out.printf("\nMalo 2 en (%d, %d) ", i,j);
    109. }
    110. sector[i/SQN][j/SQN][celda[i][j]] = true;
    111. }
    112. }
    113. }
    114. return VALIDO;
    115. }
    116. public void resuelve (int celda_actual)
    117. {
    118. int i, j, n;
    119. boolean LEGAL;
    120. boolean VACIA = false;
    121. boolean ULTIMA = true;
    122. i = celda_actual/N;
    123. j = celda_actual%N;
    124. if (celda_actual < (N*N)-1)
    125. ULTIMA=false;
    126. if (celda[i][j] == 0)
    127. VACIA = true;
    128. n=0;
    129. if (VACIA)
    130. {
    131. do
    132. {
    133. n++;
    134. RESUELTO = false;
    135. LEGAL = true;
    136. /* ¿Es legal n? */
    137. for(int k=0; k<N; k++)
    138. if(celda[i][k]==n || celda[k][j]==n)
    139. LEGAL = false;
    140. if (sector[i/SQN][j/SQN][n]==true)
    141. LEGAL = false;
    142. if (LEGAL)
    143. {
    144. /* Escribimos el número en la casilla */
    145. celda[i][j] = n;
    146. sector[i/SQN][j/SQN][n] = true;
    147. /* Si era la última, hemos acabado */
    148. if (ULTIMA)
    149. RESUELTO = true;
    150. else // No es la última
    151. {
    152. /* Si no era la última, hay que seguir */
    153. resuelve(celda_actual+1);
    154. if (!RESUELTO) /* Si no ha tenido éxito, hay que borrar esta casilla y probar otra cosa */
    155. {
    156. celda[i][j] = 0;
    157. sector[i/SQN][j/SQN][n] = false;
    158. }
    159. }
    160. }
    161. }while((RESUELTO==false)&&(n<N));
    162. }
    163. else // No está vacía
    164. {
    165. if(ULTIMA)
    166. RESUELTO = true;
    167. else
    168. {
    169. resuelve(celda_actual+1);
    170. }
    171. }
    172. }
    173. }

  8. #8
    Senior Member Avatar de Baldoceda
    Fecha de ingreso
    29 may, 06
    Ubicación
    Lima - sjL
    Mensajes
    527

    Predeterminado Re: Restricción Sudoku (programación)

    Cita Iniciado por Fonchi Ver mensaje
    1. import java.io.*;
    2. class Sudoku
    3. {
    4. int SQN = 3;
    5. int N = 9;
    6. int celda[][] = new int [N][N];
    7. boolean sector[][][] = new boolean [SQN][SQN][N+1];
    8. boolean RESUELTO;
    9. int celda_actual;
    10. public Sudoku ()
    11. {
    12. /* Inicializamos el sudoku con todo a cero */
    13. int i, j, k;
    14. celda_actual = 0;
    15. RESUELTO = false;
    16. for (i=0; i<9; i++)
    17. for (j=0; j<9; j++)
    18. celda [i][j] = 0;
    19. for (i=0; i<3; i++)
    20. for(j=0; j<3; j++)
    21. for(k=1; k<=9; k++)
    22. sector[i][j][k] = false;
    23. }
    24. public int getCelda(int i, int j)
    25. {
    26. return celda[i][j];
    27. }
    28. public void setCelda(int i, int j, int value)
    29. {
    30. celda[i][j] = value;
    31. }
    32. public boolean isResuelto()
    33. {
    34. return RESUELTO;
    35. }
    36. public void reset()
    37. {
    38. int i, j, k;
    39. celda_actual = 0;
    40. RESUELTO = false;
    41. for (i=0; i<9; i++)
    42. for (j=0; j<9; j++)
    43. celda [i][j] = 0;
    44. for (i=0; i<3; i++)
    45. for(j=0; j<3; j++)
    46. for(k=1; k<=9; k++)
    47. sector[i][j][k] = false;
    48. }
    49. public void muestra ()
    50. {
    51. int i, j;
    52. int h;
    53. System.out.printf("\n\n");
    54. for (i=0;i<N;i++)
    55. {
    56. if ((i%SQN == 0)&&(i!=0))
    57. {
    58. System.out.printf("\n -");
    59. System.out.printf("--------|------------|----------");
    60. System.out.printf("\n");
    61. }
    62. else
    63. System.out.printf("\n");
    64. for (j=0;j<N;j++)
    65. if ((j%SQN==0)&&(j!=0))
    66. {
    67. System.out.printf(" |%3d ",celda[i][j]);
    68. }
    69. else
    70. {
    71. System.out.printf("%3d", celda[i][j]);
    72. }
    73. }
    74. System.out.printf("\n\n");
    75. }
    76. public void resuelve ()
    77. {
    78. /* Comprueba que es resoluble, ajusta los sectores y lo resuelve */
    79. if (checkIntegridad())
    80. {
    81. resuelve (0);
    82. }
    83. else
    84. {
    85. RESUELTO = false;
    86. }
    87. }
    88. public boolean checkIntegridad ()
    89. {
    90. int i, j, k;
    91. boolean VALIDO = true;
    92. for(i=0; i<N; i++)
    93. {
    94. for(j=0; j<N; j++)
    95. {
    96. if (celda[i][j]!=0)
    97. {
    98. /* Veamos que no hay un número igual en toda la columna o fila*/
    99. for(k=0; k<N; k++)
    100. {
    101. if( ((k!=j)&&(celda[i][k]==celda[i][j])) || ((k!=i)&&(celda[k][j]==celda[i][j])) )
    102. {
    103. VALIDO = false; System.out.printf("\nMalo 1 en (%d,%d) k = %d", i,j,k);
    104. }
    105. }
    106. if(sector[i/SQN][j/SQN][celda[i][j]] == true) // ya estaba en el sector de antes
    107. {
    108. VALIDO = false; System.out.printf("\nMalo 2 en (%d, %d) ", i,j);
    109. }
    110. sector[i/SQN][j/SQN][celda[i][j]] = true;
    111. }
    112. }
    113. }
    114. return VALIDO;
    115. }
    116. public void resuelve (int celda_actual)
    117. {
    118. int i, j, n;
    119. boolean LEGAL;
    120. boolean VACIA = false;
    121. boolean ULTIMA = true;
    122. i = celda_actual/N;
    123. j = celda_actual%N;
    124. if (celda_actual < (N*N)-1)
    125. ULTIMA=false;
    126. if (celda[i][j] == 0)
    127. VACIA = true;
    128. n=0;
    129. if (VACIA)
    130. {
    131. do
    132. {
    133. n++;
    134. RESUELTO = false;
    135. LEGAL = true;
    136. /* ¿Es legal n? */
    137. for(int k=0; k<N; k++)
    138. if(celda[i][k]==n || celda[k][j]==n)
    139. LEGAL = false;
    140. if (sector[i/SQN][j/SQN][n]==true)
    141. LEGAL = false;
    142. if (LEGAL)
    143. {
    144. /* Escribimos el número en la casilla */
    145. celda[i][j] = n;
    146. sector[i/SQN][j/SQN][n] = true;
    147. /* Si era la última, hemos acabado */
    148. if (ULTIMA)
    149. RESUELTO = true;
    150. else // No es la última
    151. {
    152. /* Si no era la última, hay que seguir */
    153. resuelve(celda_actual+1);
    154. if (!RESUELTO) /* Si no ha tenido éxito, hay que borrar esta casilla y probar otra cosa */
    155. {
    156. celda[i][j] = 0;
    157. sector[i/SQN][j/SQN][n] = false;
    158. }
    159. }
    160. }
    161. }while((RESUELTO==false)&&(n<N));
    162. }
    163. else // No está vacía
    164. {
    165. if(ULTIMA)
    166. RESUELTO = true;
    167. else
    168. {
    169. resuelve(celda_actual+1);
    170. }
    171. }
    172. }
    173. }

    y en q programa de java copio y pego eso?? netbeans o Jcreator?

    si me ekivoco corrijanme :$
    Baldoceda <3 Estefany.
    f1rst
    s.pe
    czone

Temas similares

  1. Respuestas: 41
    Último mensaje: 26/03/2012, 13:36
  2. ¿Juegan, practican, estudian Sudoku?
    Por *x3m* en el foro Discusión General
    Respuestas: 18
    Último mensaje: 10/09/2010, 00:12
  3. PROGRAMACION : Diseño de Motores Graficos 3D y Juegos
    Por SorlaC »GhR<. en el foro Discusión General
    Respuestas: 22
    Último mensaje: 17/07/2008, 16:37
  4. Intype, editor de programación para Windows.
    Por jvAnziNho~ en el foro Discusión General
    Respuestas: 1
    Último mensaje: 14/01/2007, 16:12
  5. Tengo Una Duda Sobre Programacion!!
    Por GuGoRuLz en el foro Discusión General
    Respuestas: 7
    Último mensaje: 13/03/2005, 02:22

Permisos de publicación

  • No puedes crear nuevos temas
  • No puedes responder temas
  • No puedes subir archivos adjuntos
  • No puedes editar tus mensajes
  •