Foros del Web » Programación para mayores de 30 ;) » C/C++ »

Sudoku en borland c++

Estas en el tema de Sudoku en borland c++ en el foro de C/C++ en Foros del Web. que creen!!. el viejo borland ataca de nuevo esta vez busco en vuestra sabiduria infinita a la respuesta a una interrogante tan vieja: como hacer ...
  #1 (permalink)  
Antiguo 23/11/2014, 17:19
 
Fecha de Ingreso: noviembre-2014
Mensajes: 3
Antigüedad: 9 años, 7 meses
Puntos: 0
Sudoku en borland c++

que creen!!. el viejo borland ataca de nuevo
esta vez busco en vuestra sabiduria infinita a la respuesta a una interrogante tan vieja: como hacer un sudoku? en este caso como hacerlo en borland c++??

y con esto no solo quiero conseguir el codigo(que de verdad mucha falta me hace) sino entender como se hace, que debo tomar en cuenta al momento de comenzar a escribirlo, ya saben la logica en general. otra cosa, debo usar graphics.h

y para agregar un poco de emocion tomen en cuenta esto, es mi proyecto de fin de semestre asi que me juego el pellejo con este programa, jeje

se les agradece por adelantado.
  #2 (permalink)  
Antiguo 24/11/2014, 06:05
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 9 años, 9 meses
Puntos: 204
Respuesta: Sudoku en borland c++

No, si seguro que más de uno estará encantado de hacerte la práctica pero... ¿cuánto le vas a pagar?

Una cosa es ayudar, resolviendo dudas, y otras es hacerle a uno los ejercicios...
  #3 (permalink)  
Antiguo 24/11/2014, 09:35
 
Fecha de Ingreso: julio-2012
Mensajes: 375
Antigüedad: 12 años
Puntos: 28
Respuesta: Sudoku en borland c++

¿Sudoku? Te refieres a resolverlo o a una interfaz para jugarlo?

Para resolverlo hay un algoritmo muy mono:

1º Buscar las casillas "unicas" (es decir, cuando al analizar en horizontal, en vertical y en cuadrado descubrimos que solo puede haber una casilla posible). Si en alguna casilla descubrieramos que no existe ninguna posibilidades, devolvemos SUDOKU_IMPOSIBLE
2º Comprobamos si lo hemos resuelto.
3º Si no lo hemos resuelto, cogemos una casilla que quede libre y ponemos unos de los valores posibles. Llamamos recursivamente a nuestro metodo, si este consigue resolverlo entonces ya hemos terminado, sino probamos el siguiente valor. Si agotamos todos los valores devolvemos SUDOKU_IMPOSIBLE.

Con ese algoritmo me hize programitas que resolvía sudokus en menos de un segundo, suerte ^^
  #4 (permalink)  
Antiguo 25/11/2014, 16:09
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 12 años, 1 mes
Puntos: 49
Respuesta: Sudoku en borland c++

Cita:
Iniciado por amchacon Ver Mensaje
¿Sudoku? Te refieres a resolverlo o a una interfaz para jugarlo?

Para resolverlo hay un algoritmo muy mono:
.................................................
Con ese algoritmo me hize programitas que resolvía sudokus en menos de un segundo, suerte ^^


A pesar de mis más de treinta años dedicado a la Enseñanza Superior me sigo emocionando viendo explicaciones tan claras, concisas y precisas. Tan sólo le queda a elturco_94 ponerlas en practica y que pregunte si se "atora" en algún punto.

Respecto a tu código me queda la duda de si es como esos que circulan por Internet, cosa que viniendo del gran amhacon lo dudo, consistentes en "bambolear"
ternas de números de una línea a otra, vamos algo como:

Código C++:
Ver original
  1. *********************************************************
  2.   5    4    6    *      1    2    3    *      7    8    9
  3.   8    7    9    *      4    5    6    *      1    2    3
  4.   2    1    3    *      7    8    9    *      4    5    6
  5.  *********************************************************
  6.   6    5    7    *      2    3    4    *      8    9    1
  7.   9    8    1    *      5    6    7    *      2    3    4
  8.   3    2    4    *      8    9    1    *      5    6    7
  9.  *********************************************************
  10.   7    6    8    *      3    4    5    *      9    1    2
  11.   1    9    2    *      6    7    8    *      3    4    5
  12.   4    3    5    *      9    1    2    *      6    7    8
  13.  *********************************************************

Donde se ve que se repiten series de números en filas y/o en columnas, o es acaso de tipo "más aleatorio", de esos que no hay por donde cogerlos:

Código C++:
Ver original
  1. *****************************************************
  2.     5    8    9    *    3    4    6    *    7    2    1
  3.     4    6    7    *    1    2    9    *    8    3    5
  4.     3    1    2    *    8    5    7    *    9    4    6
  5.    *****************************************************
  6.     1    5    4    *    9    3    8    *    6    7    2
  7.     7    3    6    *    2    1    4    *    5    9    8
  8.     9    2    8    *    7    6    5    *    4    1    3
  9.    *****************************************************
  10.     6    4    3    *    5    7    2    *    1    8    9
  11.     8    7    1    *    6    9    3    *    2    5    4
  12.     2    9    5    *    4    8    1    *    3    6    7
  13.    *****************************************************
  14.  
  15. Process returned 0 (0x0)   execution time : 0.050 s
  16. Press any key to continue.

Ha sido un cosa rapidita pero funcional, todo se andará en su mejora.

Y para que vayan abriendo el apetito nada mejor que un par de Sudokus para resolver. ¿ Se animan?, los he preparado sencillitos con muchos números al descubierto para que no se desanimen....pero un poco más complejos:

Código C++:
Ver original
  1. ********************************************************************************************
  2.    14    #    5    #    *    2    #    8    1    *   16    #    #    #    *    #   10    #   12
  3.    13   11    3    #    *   10    #   12    6    *    #    5    #    #    *    #    #    #   15
  4.     8    #    #    #    *    #    #   11    #    *   13   12    #    #    *   16    #    #    2
  5.     #    2    1    #    *   16    #    3    #    *    9    #    #    #    *   11    5    8    #
  6.    ********************************************************************************************
  7.    10    3   15    #    *    #    1    7   16    *    #    9    #    #    *   12    8    #    6
  8.     #    6   16    9    *    #    #    #    #    *    5    3    4    #    *    1   14   10    #
  9.    12    #    8   14    *    4    #    5    #    *   10    #    #    #    *    2    #   11    #
  10.     2    7    4    #    *   12    9    #   10    *   15   11    8    #    *    #    #    5    #
  11.    ********************************************************************************************
  12.     9    #    #    #    *   14    #    #    5    *    7   13    #    #    *   15   11    #    1
  13.     3   15    #    #    *    #   11   10    #    *    4    6    9    #    *    5    #    #    8
  14.     #   12   13    #    *    #    #    6    #    *   11    #    #    5    *    9    #    #    #
  15.     #    #   11    #    *    #    #    9   15    *   14    8   12    3    *    #    #    #    #
  16.    ********************************************************************************************
  17.     #   14    #    #    *    6    5   15    #    *    #   10    #   13    *    4    9    2    #
  18.     #    1    2    4    *    #   10    #   11    *   12   15   14    7    *    #    #    #    #
  19.    15    #    9   13    *    #    #    #    #    *    6    2    5   11    *    #    #    #   14
  20.     #    #   12   11    *    8    2   13   14    *    3    4   16    9    *    7    1   15    5
  21.    ********************************************************************************************
  22. Process returned 0 (0x0)   execution time : 1.239 s
  23. Press any key to continue.

En el que viene te "aconsejo estirar" la ventana del navegador para verlo de forma correcta:

Código C++:
Ver original
  1. ************************************************************************************************************************************
  2.    11    #    #    #    #    #    *    8    #   24    #    #    #    *    #   22    #   18   21    #    *   20   17    #    #   16    7
  3.     #    #    #    #    #    8    *    #   11   10    #   12    #    *    #    #    #   19   24   13    *    3    4    #   18    #    5
  4.     5    #    #    #    #    3    *    #    #    #    #    #    #    *    #    #    #    #    #    #    *    #    #    8    #    #    #
  5.     #   24    #   17    #    #    *    5    #    #    #    #    #    *    #   11    #    #    7    #    *   23   21    #    #    #    #
  6.    ************************************************************************************************************************************
  7.     #   19    #   20    #    #    *    #   24    #    #    #    #    *    #   21    #    9    #    #    *   16    3    #    #    #    #
  8.     #    #   24    #   17    #    *    #   10   19   13    2    #    *    #    #    #    3    #    #    *    #    #    1    #    #    #
  9.     #    #    #    #   22    9    *   17    #    3    1    #    #    *    #    #   12    #    #    #    *    #    #    #   15    #   18
  10.     #   21    3    1    #   18    *   23    #    #    #    #    #    *    #    5    #   15    #    #    *    #    #    #    #    #   14
  11.    ************************************************************************************************************************************
  12.    18    #    #    #   12   14    *    #   21    7    #    #    #    *   10    #    5    #    #    #    *    #   22   11   20    #    1
  13.     #    #    #    #   11    #    *   20    #   17    #    #   23    *    #    #    #    #   14    #    *    #    9    #    #    #   10
  14.     7    #    1    6    #   19    *    4    8    #   18    #    #    *    #    #   11    #    #    #    *   13    #    #    #    #    #
  15.     9    #   17    #    #    #    *   10    #   22    #   14    #    *    #    #    #   13    #    #    *    #    7    #    #    #   23
  16.    ************************************************************************************************************************************
  17.     #    #   16   11    #    #    *    #    #    #    #    #    5    *    #    6    #    #   12    #    *   21    #    #    #    #    #
  18.    23   14    9    #   21    #    *    #    2   15    3    1    #    *    #    #    7    #    #    #    *    #    #   20    #   10    #
  19.     #    #    #    #    5    #    *   11    #    #    #    #   19    *    #    2   23    #    #   15    *    #    1    #    #    #   22
  20.     #    4    #    #    #   15    *    6   18   23    #   22   14    *    5    3   21   16   13    1    *   12    2   19   11    9   17
  21.    ************************************************************************************************************************************
  22. Process returned 0 (0x0)   execution time : 3.056 s
  23. Press any key to continue.

Espero que sirva de relax entre tanto código.

Y las soluciones en próximos días.

¡¡¡Saluditos!!!


Última edición por leosansan; 25/11/2014 a las 16:14
  #5 (permalink)  
Antiguo 26/11/2014, 10:34
 
Fecha de Ingreso: noviembre-2014
Mensajes: 3
Antigüedad: 9 años, 7 meses
Puntos: 0
Respuesta: Sudoku en borland c++

si, me referia a que debe haber ua interfaz donde el usuario pueda resolverlo. tomare en cuenta lo que dice amchacon
  #6 (permalink)  
Antiguo 26/11/2014, 14:02
 
Fecha de Ingreso: julio-2012
Mensajes: 375
Antigüedad: 12 años
Puntos: 28
Respuesta: Sudoku en borland c++

Pues una interfaz es más sencillo, aunque yo empezaría haciendolo primero en consola.

Las interfaces se hacen con librerías externas (wxWidgets, QT...). Existen otros lenguajes más sencillos para estos lares, como Java que incluye esto en su libreria estándar. Lo digo por si tienes la oportunidad de elegir.
Cita:
Iniciado por leosansan Ver Mensaje

A pesar de mis más de treinta años dedicado a la Enseñanza Superior me sigo emocionando viendo explicaciones tan claras, concisas y precisas. Tan sólo le queda a elturco_94 ponerlas en practica y que pregunte si se "atora" en algún punto.

Respecto a tu código me queda la duda de si es como esos que circulan por Internet, cosa que viniendo del gran amhacon lo dudo, consistentes en "bambolear"
¿Bambolear?

Es intuitivo sacado sobre la marcha, forma parte de un programita más complejo que leía el sudoku línea a línea y después lo resolvía. Te paso el código por MP (en C++ por supuesto).

Cita:
Iniciado por leosansan Ver Mensaje
Donde se ve que se repiten series de números en filas y/o en columnas, o es acaso de tipo "más aleatorio", de esos que no hay por donde cogerlos
Ya que se comenta el tema, estos sudokus los has generado con un programa tuyo. ¿Que estrategia has usado para que sea 100% aleatorio? ^^
  #7 (permalink)  
Antiguo 27/11/2014, 10:32
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 9 años, 9 meses
Puntos: 204
Respuesta: Sudoku en borland c++

Cita:
Iniciado por leosansan Ver Mensaje
En el que viene te "aconsejo estirar" la ventana del navegador para verlo de forma correcta:
Eres consciente que con esa disposición, debido a que no hay tantas filas como posibles valores, es posible que haya más de una solución, no?

Pd.: voy a ver si preparo un código que me permita resolver sudokus...
  #8 (permalink)  
Antiguo 05/12/2014, 03:48
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 12 años, 1 mes
Puntos: 49
Respuesta: Sudoku en borland c++

Cita:
Iniciado por amchacon Ver Mensaje
.................................................. .............................
Ya que se comenta el tema, estos sudokus los has generado con un programa tuyo. ¿Que estrategia has usado para que sea 100% aleatorio? ^^
Antes que nada, gracias por el código que me pasaste, muy interesante y me ha animado a hacer otro con el mismo objetivo.

Bueno, como han pasado ya unos días no creo que se considere hacer la tarea y sí compartir con un amigo y el resto del foro una idea, aún incipiente, pero funcional.

Pues bien amchacon, la idea en sí es más sencilla de explicar que de ponerla en práctica. Para fijar ideas me referiré a un Sudoku de 9x9 casillas lo que equivale a tres casillas de 9x9 en cada una de las tres líneas, aunque el program que propongo genera Sudokus más variados como de 2x2, 2x3, 2x4, 3x2, 3x3, 3x4, 3x5 ,4x4, 4x5 ,4x6 y así ....excepto el de 5x5 y mayores. Aún lo tengo en fase alfa y tengo que "dirigir" los aleatorios para que sea más eficiente y alcance tamaños mayores. Pero no te quería hacer esperar más.

* Existen dos índices o contadores, uno parcial y otro total, que me indica si tengo que hacer un reinicio parcial o total si se bloquea el relleno, vamos si no encuentra números válidos para rellenar alguna casilla.

* Se trata de ir rellenando casilla a casilla, es decir que no se rellena como una matriz normal línea a línea sino que se rellenan casilla a casilla de 3x3 en cada línea. Parece una tontería pero el que recorra tres columnas, baje para rellenar otras tres y vuelva a la primera línea otra vez para ir rellanando otra casilla tiene su miga.

* La forma de relleno es casi obvia. Por cada casilla que relleno genero un conjunto de valores aleatorios del 1 al 9 y de forma aleatoria los voy metiendo en la casilla correspondiente y voy poniendo los valores del array a cero y eso me indica que si sale un aleatorio y el array vale cero tendía que coger otro porque ese ya está pillado.

* Y el meollo del problema: que no se repitan en más de una línea y columna. De eso se encarga el array "ocupados" donde voy guardando los valores que han salido para no repetirlos. Es muy "jugoso" ya que además de tener las dimensiones del tamaño del Sudoku, [tam][tam] incorpora otras dos dimensiones, resultando en un ¡¡¡ array cuadrimensiona ¡¡¡. La tercera dimensión, [salto] la uso para una pequeña "virguería". Y es que si se supera el contador total el reinicio es desde cero, se vuelve al estado original, pero si el contador que se supera es el parcial el reinicio sólo afecta al "salto" ( en este caso de 3x3 hay tres saltos correspondientes a conjuntos de tres líneas por cada salto ). Por ejemplo si estoy en el salto 3 ( líneas de 6 a 9 ) y se hace un reinicio parcial los otros dos saltos anteriores ( líneas de 1 a 6 ) conservan sus valores y se sigue intentando rellenar sólo el tercer salto, así me ahorro reinicios innecesarios. Y es que me manejo muy bien con arrays multidimensionales y casi siempre puedo prescindir de cosas como estructuras, listas y árboles, al fin y al cabo no dejan de ser arrays manejados de forma implícita.

Pero te comento que ha sido algo rapidito y está muy verde aún, aunque insisto en que es totalmente funcional. Y como era algo para salir del paso y ver si podía superar el reto de conseguirlo, no he dudado en usar cosas como el goto. Ya en versiones posteriores lo eliminaré, son cosas de mis inicios hace más de cuatro décadas en Basic y Fortran .

Por cierto, te dejo activado un printf para que veas que está en ejecución. Hay otra línea con un "imprimir" que la puedes activar para "ver" como se rellena el Sudoku. También están desactivados unos arrays que hacen las veces de los contadores y es que estoy haciendo pruebas para encontrar unos valore óptimos de los mencionados contadores, aunque se compica porque a su vez están relacionados con el tamaño de la matriz. Pero todo se andará .........

El código que te paso en primer lugar es el "humanizado", vamos el que uso para compartir códigos y que se entienda meridianamente bien. El segundo te lo dejo como curiosidad para que veas como trabajo en modo "borrador". Como observarás es muy "compacto", con for muy largos e if sin cuerpo que acaban en punto y coma. Y es que como hábito y para concentrarme en lo básico, el algoritmo que resuelva un problema, paso de perder tiempo en pequeñeces, así entenderás mejor el uso intensivo que hago del operador condicional. Estoy tan acostumbrado al mismo que no me cuesta nada encadenarlos, pero todo es cuestión de práctica, sencillamente. . De paso te dejo una salida de uno de 4x4 y, por cierto, los de 3x3 tardan menos de un segundo, no así los de 4x4 que va de unos pocos segundos a un minuto y es que rellenar de esa forma aleatorio una matriz de 256 elementos es tela marinera:

Sigue en el siguiente mensaje..................no cabe en uno sólo .

¡¡¡Saluditos!!!

  #9 (permalink)  
Antiguo 05/12/2014, 03:54
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 12 años, 1 mes
Puntos: 49
Respuesta: Sudoku en borland c++

Por cierto, fíjate que la función estrella" apenas es de 50 líneas, lo demás es imprimir y otras lindeces para hacer la salida más interesante.

Código C++:
Ver original
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <windows.h>
  5. /** 1 < fil < 6 ....1 < col < 6 ..ej: 2x3, 2x4, 3x2, 3x3, 3x5, 5x3, 4x3, 3x4, 4x4, 4x5, 4x6....¡¡¡..NO 5 x 5 ¡¡¡ ***/
  6. #define fil  3u
  7. #define col  3u /** NO 5 x 5 **/
  8. #define tamXY  ( fil * col )
  9. #define tamX  ( fil * fil )
  10. #define tamY  ( fil * col )
  11. #define tam  ( fil * col )
  12. #define Tam  ( tamX * tam )
  13.  
  14. void generarSudoku ( void ) ;
  15. void generarNumAleatorio ( unsigned int TAM , unsigned int algO [ TAM ] ) ;
  16. void imprimir ( unsigned int algo [ tam ][ tam ] , unsigned int flag ) ;
  17. void espaciado ( )  ;
  18. int gotoxy ( int x , int y ) ;
  19.  
  20. int  main ( void ) {
  21.   srand ( ( unsigned ) time ( NULL ) ) ;
  22.   generarSudoku ( ) ;
  23.   return 0 ;
  24. }
  25.  
  26. void generarSudoku ( void ) {
  27.   unsigned int  i  , j , k  , tamx , cont , contTotal , q , salto , saltoFil , aleatorio , num [ tam ][ tam ] , numAleat [ tam ] ;
  28.   unsigned int  icont = 2500 , icontTotal = 1000000 ,/*10000000*/ ocupados  [ 2 ][ fil  ][ tam ][ tam ] ;
  29.   //unsigned int icont [ ]= {2500,25000,250000,250000,2500000,2500000}, icontTotal [ ] = {10000000, 50000000, 100000000, 500000000, 1000000000, 100000000} ;
  30.   static unsigned int reinicios = 0 , reinicio [ 6 ] ;
  31.   tamx = ( fil < col ) ? tamX : tam ;
  32.   for ( i = 0 ; i < tamx ; i ++ )  reinicio [ i ] = 0 ;
  33.   inicio1 :  /** <===  INICIO1 **/
  34.     for ( salto = 0 , contTotal = 0 ; salto < fil ; salto++ ) {
  35.     saltoFil = salto * fil - 1 ;
  36.     inicio :  /** <===  INICIO **/
  37.     for ( i = 0  ,cont = 0 ; i < tamx ; i ++ )
  38.       for ( j = 0 ; j < tam ; j++ ) {
  39.         if ( salto == 0 )
  40.           for ( k = 0 ; k < fil ; k ++ )
  41.             ocupados  [ 0 ][ k ][ i ][ j ] = ocupados [ 1 ][ k ][ i ][ j ] = 0 ;
  42.         else
  43.           ocupados [ 0 ][ salto ][ i ][ j ] = ocupados [ 0 ][ salto - 1 ][ i ][ j ] , ocupados [ 1 ][ salto ][ i ][ j ] = ocupados [ 1 ][ salto - 1 ][ i ][ j ] ;
  44.           if ( i >= salto * fil )
  45.             num [ i ][ j ] = 0 ;
  46.       }
  47.     generarNumAleatorio ( tam , numAleat ) ;
  48.     for ( i = salto * fil , q = 0;  i <  ( salto + 1 ) * fil ; i++ ) {
  49.       aleatorio = rand ( ) % tam ;
  50.       for ( j = q ; j < q + col ; j++ , aleatorio = rand ( ) % tam  ) {
  51.         while ( ocupados [ 0 ][ salto ][ i ][ numAleat [ aleatorio ] - 1 ] == 1 || ocupados [ 1 ][ salto ][ numAleat [ aleatorio ] - 1 ][ j ] == 1 || numAleat [ aleatorio  ] == 0  ) {
  52.           aleatorio = rand ( ) % tam , contTotal++ , cont++ ;
  53.           if ( cont > icont /*icont [ salto ]*/ )
  54.             { gotoxy ( 0 , 2 * tam + 16 ) ;
  55.             printf ( "SALTO::%u:: contador = %8u\tcontTotal = %10u\treinicios = %4u\treinicios [ %d ] = %4u\n" , salto , cont , contTotal , reinicios , salto , reinicio [ salto ] ) ;
  56.             //gotoxy(0,2*tam+20),imprimir(num,0); /** Activalo si lo quieres ver trabajando, pero en valores mayores ralentiza el resultado final **/
  57.             goto inicio ;}
  58.           if ( contTotal > icontTotal/* icontTotal [ salto ]*/ )
  59.             { gotoxy ( 0 , 2 * tam + 17 ) ; reinicio [ salto ]++ ; reinicios++ ; printf ( "SALTO::%u:: contador = %8u\tcontTotal = %10u\treinicios = %4u\treinicios [ %d ] = %4u\n" , salto , cont , contTotal , reinicios , salto , reinicio [ salto ] ) ; goto inicio1 ; }
  60.           }
  61.         num[i][j]=numAleat[aleatorio],ocupados[0][salto][i][numAleat[aleatorio]-1]=1, ocupados[1][salto][numAleat[ aleatorio ]-1][j]=1, numAleat[aleatorio]=0 ;
  62.       }
  63.       if ( i == ( ( salto + 1 ) * fil - 1 ) && j < tam && j % col == 0 )
  64.         i = saltoFil , q += col ;
  65.       if ( i == saltoFil  && j % col == 0 )
  66.         generarNumAleatorio ( tam , numAleat ) ;
  67.     }
  68.     if ( fil > col && num [ tam -1 ][ tam -  1 ] != 0 )
  69.       break  ;
  70.   }
  71.   gotoxy (0,0) , imprimir ( num , 0 ) , gotoxy ( 0 , tam + 8 ) , imprimir ( num , 1 ) ;
  72. }
  73.  
  74. void generarNumAleatorio (  unsigned int TAM , unsigned int Algo [ TAM ] ) {
  75.     int i , temp , aleatorio ;
  76.     for ( i = 0  ; i < TAM ; i++ )
  77.       Algo [ i ] = i + 1 ;
  78.   for ( i = 0  ; i < TAM ; i++ ) {
  79.     aleatorio = 1 + rand ( ) % TAM ;
  80.     temp = Algo [ i ] ;
  81.     Algo [ i ] = Algo [ aleatorio - 1 ] ;
  82.     Algo [ aleatorio - 1 ] = temp ;
  83.   }
  84. }
  85. void generarNumAleatorio1 (  unsigned int TAM , unsigned int Algo [ TAM ] ) {
  86.     int i , temp , aleatorio ;
  87.     for ( i = 0  ; i < TAM ; i++ )
  88.       Algo [ i ] = i + 1 ;
  89.   for ( i = 0  ; i < TAM ; i++ ) {
  90.     aleatorio = 1 + rand ( ) % TAM ;
  91.     temp = Algo [ i ] ;
  92.     Algo [ i ] = Algo [ aleatorio - 1 ] ;
  93.     Algo [ aleatorio - 1 ] = temp ;
  94.   }
  95. }
  96.  
  97. void imprimir ( unsigned int algo [ tam ][ tam ] , unsigned int flag ) {
  98.   int i , j , l , p , tamx , noVer = 0.6 * tam * tam , ocultos [ Tam ] ;/** 0.6 sera variable segun nivel de dificultad **/
  99.   tamx = ( fil < col ) ? tamX : tam ;
  100.   generarNumAleatorio ( Tam , ocultos ) ;
  101.   espaciado ( ) ;
  102.   for ( i = 0 , p = 0 ; i < tamx ; i++ , p++ ) {
  103.     for ( j = 0 ; j < tam ; j++ , p++) {
  104.       if ( j > 0 && j % col == 0 )
  105.         printf ( "    *" ) ;
  106.       if ( i > 0  && i % fil == 0 && j % tam == 0 )
  107.         espaciado ( ) ;
  108.       if ( flag == 1 ) {
  109.         for ( l = 0  ; l < noVer ; l++ )
  110.           if  ( p == ocultos [ l ] ) {
  111.             printf ( "%5c" , '#' ) ;
  112.             break ;
  113.           }
  114.         if ( l == noVer )
  115.           printf ( "%5d" , algo [ i ][ j ] ) ;
  116.       }
  117.         else
  118.           printf ( "%5d" , algo [ i ][ j ] ) ;
  119.     }
  120.     putchar ( '\n' ) ;
  121.   }
  122.   espaciado ( ) ;
  123. }
  124.  
  125. void espaciado ( void ) {
  126.   int k ;
  127.   printf ( "   " ) ;
  128.   for ( k = 0 ; k < tam * 5 + ( fil - 1 ) * 4 ; k++ )
  129.     putchar ( '*' ) ;
  130.   putchar ( '\n' ) ;
  131. }
  132.  
  133. int gotoxy ( int x , int y ) {
  134.    COORD coord ;
  135.    HANDLE h_stdout ;
  136.    coord.X = x ;
  137.    coord.Y = y ;
  138.    if ( ( h_stdout = GetStdHandle( STD_OUTPUT_HANDLE ) ) == INVALID_HANDLE_VALUE )
  139.       return 0 ;
  140.    if ( SetConsoleCursorPosition (h_stdout , coord ) == 0 )
  141.       return 0 ;
  142.    return 1 ;
  143. }

Código C++:
Ver original
  1. ********************************************************************************************
  2.     7   16    3    5    *    8   15   14   10    *    1    2    9    6    *   12   13   11    4
  3.     9    1   13   10    *    7    5   12   11    *   15    8   14    4    *    2    6    3   16
  4.     4    2   14   12    *   16   13    6    9    *   10    3    7   11    *    8   15    1    5
  5.    15   11    8    6    *    2    1    4    3    *   13    5   12   16    *   10    9    7   14
  6.    ********************************************************************************************
  7.    16   13    6    1    *    4    3   11    5    *    7   15    2   12    *   14    8    9   10
  8.     2   14   15    8    *    6   16    9    7    *    5    1   10   13    *   11   12    4    3
  9.    10    4    5   11    *   14   12    2    1    *    3    6    8    9    *   15   16   13    7
  10.    12    3    9    7    *   15   10   13    8    *   11    4   16   14    *    6    1    5    2
  11.    ********************************************************************************************
  12.     3    6   12   16    *    5   11   10   13    *   14    9   15    7    *    1    4    2    8
  13.    11    5    4   14    *   12    8   16    2    *    6   10    1    3    *   13    7   15    9
  14.     1   10    2    9    *    3    4    7   15    *    8   11   13    5    *   16   14   12    6
  15.     8   15    7   13    *    9   14    1    6    *   12   16    4    2    *    5    3   10   11
  16.    ********************************************************************************************
  17.    13    9   16    4    *   10    7   15   12    *    2   14   11    8    *    3    5    6    1
  18.     6    8    1   15    *   11    9    3    4    *   16   13    5   10    *    7    2   14   12
  19.     5    7   11    2    *    1    6    8   14    *    9   12    3   15    *    4   10   16   13
  20.    14   12   10    3    *   13    2    5   16    *    4    7    6    1    *    9   11    8   15
  21.    ********************************************************************************************
  22.  
  23. Process returned 0 (0x0)   execution time : 0.759 s
  24. Press any key to continue.
  25.  
  26. SALTO::0:: contador =   251    contTotal =     8785
  27.  
  28. SALTO::1:: contador =   751    contTotal =    41270
  29.  
  30. SALTO::2:: contador =  2251    contTotal =  1286352
  31.  
  32. SALTO::3:: contador =  6751    contTotal =  5087589

Un fuerte abrazo amigo amchacon y desde ya ¡¡¡ Felices Fiestas ¡¡¡.

¡¡¡Saluditos!!!


Última edición por leosansan; 05/12/2014 a las 04:11
  #10 (permalink)  
Antiguo 12/12/2014, 04:13
 
Fecha de Ingreso: julio-2012
Mensajes: 375
Antigüedad: 12 años
Puntos: 28
Respuesta: Sudoku en borland c++

No me convence que esté tan junto, le quita legibilidad. A lo mejor son manías mías ^^

Lo del array cuadrimensional me parece demasiado grande, como intentes generar sudokus un poco más grandes (6x6) podría desbordarte la pila. Maxime cuando en la practica realizas saltos muy rara vez.

Pero quitando los detalles esteticos, tengo que felicitarte. Es muy rápido: 0,032s me ha tardado en generar. Creo que esto merece una contrapropuesta cuando acabe con los examenes, todo se andará.
  #11 (permalink)  
Antiguo 23/12/2014, 16:27
 
Fecha de Ingreso: julio-2012
Mensajes: 375
Antigüedad: 12 años
Puntos: 28
Respuesta: Sudoku en borland c++

Aquí va mi código ^^

Código C++:
Ver original
  1. #include <iostream>
  2. #include <ctime>
  3. #include <cstdlib>
  4. using namespace std;
  5.  
  6. const int TAM = 9; // Maximo numero que puede haber en el sudoku, numeros más grandes o mas pequeños generan sudokus con cuadrados de 2x2,4x4,5x5... Por defecto lo dejamos en el clásico 3x3
  7.  
  8. bool resuelto(short Tablero[TAM][TAM]);
  9. void generarSudoku(short Tablero[TAM][TAM]);
  10.  
  11. //funcion raiz natural, mas eficiente que sqrt y que uso para sacar el tamaño de cada cuadrado (raiz(TAM))
  12. inline int raiz(int n)
  13. {
  14.     for (int i = 2;i*i<=n;i++)
  15.     {
  16.         if (i*i == n) return i;
  17.     }
  18.     throw "Error no valido";
  19. }
  20. void mostrarTablero(short Tablero[TAM][TAM])
  21. {
  22.     for (int i = 0; i<TAM; i++)
  23.     {
  24.         for (int j = 0; j<TAM; j++)
  25.         {
  26.             cout<<(int)Tablero[i][j]<<" | ";
  27.         }
  28.         cout<<endl;
  29.     }
  30.  
  31.     cout<<endl<<endl;
  32. }
  33.  
  34. int main()
  35. {
  36.     srand(time(0));
  37.     short Tablero[TAM][TAM];
  38.     generarSudoku(Tablero);
  39.  
  40.     mostrarTablero(Tablero);
  41.  
  42.     cout<<resuelto(Tablero)<<endl;
  43.     return 0;
  44. }
  45.  
  46. // Generamos un sodoku, no es necesario que tablero este inicializado
  47. void generarSudoku(short Tablero[TAM][TAM])
  48. {
  49.     #define SUBCUADRADO(i,j) (i/TAM_N+(j/TAM_N)*TAM_N)
  50.     const int TAM_N = raiz(TAM); // tamaño de cada cuadrado, corresponde a su raiz
  51.     bool Tabla[TAM][TAM][TAM]; // Tabla(x,y,valor) con los valores probados en una casilla, true si fue probado
  52.     bool Tabla_Fila[TAM][TAM]; // Tabla(y,valor) con los valores existen en la fila, true si existe
  53.     bool Tabla_Columna[TAM][TAM]; // Tabla(x,valor) con los valores probados en una columna, true si fue probado
  54.     bool Tabla_Cuadrado[TAM][TAM]; // Tabla(SUBCUADRADO,valor) con los valores probado en un cuadrado, true si fue probado
  55.     int cont;
  56.  
  57.     // Inicializar las tablas
  58.  
  59.     for (int i = 0; i<TAM; i++)
  60.     {
  61.         for (int j = 0; j<TAM; j++)
  62.         {
  63.             Tablero[i][j] = -1; // inicializo el sudoku
  64.             for (int k = 0; k<TAM; k++)
  65.             {
  66.                 Tabla[i][j][k] = false;
  67.                 Tabla_Fila[j][k] = false;
  68.                 Tabla_Columna[i][k] = false;
  69.             }
  70.         }
  71.     }
  72.  
  73.     for (int i = 0; i<TAM; i++)
  74.     {
  75.         for (int k = 0; k<TAM; k++)
  76.         {
  77.             Tabla_Cuadrado[i][k] = false;
  78.         }
  79.     }
  80.  
  81.  
  82.     // Bucle principal
  83.  
  84.     for (int i = 0; i<TAM; i++)
  85.     {
  86.         for (int j = 0; j<TAM; j++)
  87.         {
  88.             int aux = (rand()%TAM); // Numero aleatorio
  89.             bool fallo;
  90.  
  91.             if (Tablero[i][j] >= 0) // Si ya contenía algo, quitamos sus valores de las tablas
  92.             {
  93.                 const int valor = Tablero[i][j] - 1;
  94.  
  95.                 Tabla_Fila[j][valor] = false;
  96.                 Tabla_Columna[i][valor] = false;
  97.                 Tabla_Cuadrado[SUBCUADRADO(i,j)][valor] = false;
  98.             }
  99.             cont = 0; //variable control para el bucle, solo vamos a comprobar los 9 valores posibles
  100.  
  101.             do
  102.             {
  103.                 aux = ((aux+1)%TAM);//aumento en una unidad
  104.                 fallo = (Tabla[i][j][aux] |        // tabla de valores probados en esa casilla
  105.                          Tabla_Fila[j][aux] |      // tabla de valores probados en esa fila
  106.                          Tabla_Columna[i][aux] |   // tabla de valores probados en esa columna
  107.                          Tabla_Cuadrado[SUBCUADRADO(i,j)][aux]); // tabla de valores probados en ese cuadrado
  108.                 cont++; // una iteracion mas
  109.             }
  110.             while( fallo && cont < TAM); // mientras no encontremos un valor que no este en las tablas y no hayamos recorrido todos los valores...
  111.  
  112.             if (!fallo) //añadimos
  113.             {
  114.                 Tablero[i][j] = aux+1; // Tablero a devolver, los numeros son del 1-9
  115.                 Tabla[i][j][aux] = true; // Marcamos en la tabla de casillas un nuevo valor
  116.                 Tabla_Fila[j][aux] = true; // Marcamos un nuevo valor en la fila
  117.                 Tabla_Columna[i][aux] = true; // Marcamos un nuevo valor en la columna
  118.                 Tabla_Cuadrado[SUBCUADRADO(i,j)][aux] = true; // Marcamos un nuevo valor en el cuadrado
  119.             }
  120.             else //Si no encontramos ningun valor válido para añadir
  121.             {
  122.                 for (int k = 0; k<TAM; k++)
  123.                 {
  124.                     Tabla[i][j][k] = false; // reseteamos la tabla de valores probados
  125.                 }
  126.  
  127.                 Tablero[i][j] = -1; // borramos la casilla
  128.                 j -= 2; // retrocedemos, son dos unidades porque luego el for me avanza una
  129.  
  130.                 if (j < -1) // si nos hemos pasado de la fila, retrocedemos una columna
  131.                 {
  132.                     j =TAM-2;
  133.                     i--;
  134.                     if(i < 0) // if de depuración, en principio no debería activarse nunca pues indica que nos hemos salido del sudoku
  135.                     {
  136.                         cerr<<"Error inesperado"<<endl;
  137.                         throw "Error inesperado";
  138.                     }
  139.                 }
  140.  
  141.             }
  142.         }
  143.     }
  144. }
  145.  
  146. /* Funcion auxiliar para depuración, reciclado de otro proyecto por lo que ha sido necesario añadir algunas constantes
  147.  
  148. Se usa para comprobar que el sudoku está correctamente generado (no hay repeticiones en cada fila/columna/cuadrado)
  149. */
  150.  
  151. const int MAX = TAM;
  152. const int MAX_N = 3;
  153. const int Suma = 45;
  154.  
  155. bool resuelto(short Tablero[TAM][TAM])
  156. {
  157.     // Macro para comprobar repeticiones
  158.  
  159. #define COMPROBAR_REPETICIONES if (i != 0) \
  160.     for (short k = i-1; k > -1;k--) \
  161.             if (Repeticiones[i] == Repeticiones[k]) \
  162.                     return false;
  163.  
  164.     // Lineas horizontales
  165.  
  166.     short Repeticiones[MAX];
  167.  
  168.     for (short i = 0; i < MAX; i++)
  169.         Repeticiones[i] = 0;
  170.  
  171.     short Contador = 0;
  172.  
  173.     for (short j = 0; j < MAX; j++)
  174.     {
  175.  
  176.         for (short i = 0; i < MAX; i++)
  177.         {
  178.             Repeticiones[i] = Tablero[i][j];
  179.  
  180.             COMPROBAR_REPETICIONES
  181.  
  182.         }
  183.  
  184.     }
  185.  
  186.     // Lineas verticales
  187.  
  188.     for (short j = 0; j < MAX; j++)
  189.     {
  190.         Contador = 0;
  191.         for (short i = 0; i < MAX; i++)
  192.         {
  193.             Repeticiones[i] = Tablero[j][i];
  194.  
  195.             COMPROBAR_REPETICIONES
  196.         }
  197.     }
  198.  
  199.  
  200.     // Cuadrados
  201.  
  202.     for (short l = 0; l < MAX_N; l++)
  203.         for (short k = 0; k < MAX_N; k++)
  204.         {
  205.             Contador = 0;
  206.             for (short j = k*MAX_N; j < (MAX_N*k)+MAX_N; j++)
  207.                 for (short i = l*MAX_N; i < (l*MAX_N)+MAX_N; i++)
  208.                 {
  209.                     Contador += Tablero[i][j];
  210.                 }
  211.  
  212.             // Aquí no podemos usar la macro, asi que usamos otro método
  213.  
  214.             if (Contador != Suma) // Suma es lo que da si se suma 1+2+3+4+5+6+7+8+9
  215.             {
  216.                 cout<<l<<','<<k<<endl;
  217.                 return false;
  218.             }
  219.  
  220.         }
  221.  
  222.     return true;
  223. }

Etiquetas: borland, int, programa, sudoku
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 20:47.