Sudoku en C o C++

Para información, este es un proyecto que debo presentar durante el examen oral de mi BTS en informática, no me siento muy cómoda ya que empecé a estudiar informática para este BTS, el cual me fue más o menos impuesto (y retomar los estudios después de 9 años en la vida activa no es fácil). Así que debo cumplir con ciertos criterios para el examen, como hacer una aplicación en C o C++.

Gracias Nabla's y a los demás por las ideas dadas, voy a revisar y vuelvo a ustedes en caso de necesitar.

mensajes <3>, <4>, <5>
No sé si es la hora o si pierdo la paciencia, pero ya van dos veces seguidas que me encuentro con un hilo de discusión de C++ donde las respuestas NO tienen NADA que ver con la pregunta planteada. ¡No estamos aquí para contar nuestras vidas o discutir el tema, es una locura!

@dna.factory
Entonces, NO, un sudoku no es complicado de programar si se sabe escribir bucles for. Además, no hay que programar un solucionador. Solo hay que pensar un par de minutos antes de lanzarse.

Cada casilla puede contener un valor de 0 a 9 (su dominio). Este dominio se restringe por las casillas del cuadrante, de la fila y de la columna. Te doy el método en pseudo código para que te quede un poco de trabajo por hacer. El sudoku habitual contiene 3x3 cuadrantes de 3x3 casillas cada uno (n=3).

Para cada casilla (i,j) de la cuadrícula Si el dominio de la casilla(i,j) está reducido a un elemento: colocarlo Sino: sacar un valor v al azar entre los valores que aún están en el dominio Para cada casilla de la fila i: eliminar el valor v del dominio Para cada casilla de la columna j: eliminar el valor v del dominio Para cada casilla del cuadrado n x n que contiene (i,j): eliminar el valor v del dominio Fin para

A mi humilde opinión, la gente que dice que no está a su alcance se equivoca francamente. La verificación es bastante más simple. La única "dificultad" consiste en asociar una casilla (i,j) con un cuadrante (pero bueno, no es el fin del mundo).

#define n 3 // sudoku 3x3 cuadrantes de 3x3 casillas // Asociar cada casilla (fila,columna) a un índice que identifique un cuadrante // (el cuadrante en la parte superior izquierda tiene 0, el de su derecha 1, etc...) lo que da // este mapeo para n = 3 : // 000111222 // 000111222 // 000111222 // 333444555 // 333444555 // 333444555 // 666777888 // 666777888 // 666777888 // Devuelve el identificador del cuadrante que contiene la casilla (fila, columna) unsigned coordonnees2cadran(unsigned fila,unsigned columna){ if (fila >= n*n) throw; if (columna >= n*n) throw; return (fila/n)*n + columna/n; // '/' : división euclidiana }

Para verificar una cuadrícula:

Vaciar los dominios asociados a cada fila Vaciar los dominios asociados a cada columna Vaciar los dominios asociados a cada cuadrante Para cada fila i Para cada columna j Añadir el valor de la casilla(i,j) al dominio de la fila(i) Añadir el valor de la casilla(i,j) al dominio de la columna(j) Añadir el valor de la casilla(i,j) al dominio del cuadrante que contiene (i,j) Fin para Fin para Para cada fila i Si el dominio de la fila(i) no contiene los 9 valores: retornar falso Fin para Para cada columna j Si el dominio de la columna(j) no contiene los 9 valores: retornar falso Fin para Para cada cuadrante Si el dominio del cuadrante no contiene los 9 valores: retornar falso Fin para Retornar verdadero

Para generar una cuadrícula que el usuario debe completar, simplemente generas una solución y eliminas valores. Por ejemplo, 5 o 6 valores por cuadrante. En algunos casos, puede que la cuadrícula tenga múltiples soluciones, pero eso no importa, ya que al final la función de verificación no controla si la cuadrícula inicial y la solución propuesta son concordantes, solo verifica si la cuadrícula propuesta es válida.

Ahora solo te queda codificar todo eso ;-) Si tienes motivación, puedes ver fácilmente que el pseudo código que te propongo funciona para sudokus de n x n cuadrantes de n x n elementos (con n >=1 y no solo n = 3).

En términos de implementación, puedes utilizar estructuras de este tipo:

#include <vector> typedef std::vector<bool> dominio_t; struct case_t{ dominio_t dominio; // para generar la cuadrícula o para el solucionador unsigned valor; }; typedef std::vector<std::vector<case_t> > cuadrícula_t; 

Lo que habría sido difícil, habría sido:

1) tener que codificar un solucionador. Pero de hecho, se hace muy fácilmente con un modelo CSP (ver curso de investigación operativa para los aficionados) que, al igual que el método que acabo de proponer, se basa en reducciones de dominios. Es bastante sencillo verificar si la cuadrícula tiene una o varias soluciones (con un árbol de ramificación).

2) tener que generar cuadrículas con solución única (pero una vez que el solucionador está codificado, simplemente hay que eliminar valores y permitir su eliminación solo si la solución sigue siendo única).

Buena suerte

Yo estoy de acuerdo con Niel, también hay que pensar en la capacidad del candidato en cuestión
para no asustarlo demasiado, espero que ustedes entiendan.

Un sudoku es bastante complejo de programar... sobre todo si no te sientes cómodo con la programación...
¿Elegiste tu proyecto libremente o fue impuesto?

--
Utae Gamuza

Para la creación de grillas aleatorias, no sé.

En cambio, para la arquitectura, ya haces una matriz (tabla de 2 dimensiones) del tamaño de una grilla (puede ser variable si también usamos letras).
Haz un algoritmo de verificación de cada fila, de cada columna y de cada cuadrado, para ver si cada número se utiliza una vez, y solo una vez.

Asegúrate de que los valores generados por el programa no sean modificables por el usuario en su grilla.

... es un poco suave como presentación ...

Personalmente, elegí "el juego de la vida", no es realmente un juego, sino más bien una simulación bastante interesante (y simplista) sobre la biocultura. Es más complejo de programar que "encontrar el número", pero mucho más simple que el sudoku.
Escribe juego de la vida en Wikipedia, tendrás el modelo de la simulación... personalmente, me divertí mucho haciéndolo.

--
Utae Gamuza

efectivamente, el juego de la vida no está mal...
también está la hormiga de Langton, que no está mal (y es fácil)
https://fr.wikipedia.org/wiki/Fourmi_de_Langton

(pero en mi época, no era necesario eso, solo bastaba con pedir ser tomado...)
--
¡Deja de fallar en la prueba de Turing!

[Modo irónico activado] Oh sí, parece muy simple para alguien que no ha tenido o poco ha tenido clases de C++... [Modo irónico desactivado]

No veo en qué nuestras respuestas son fuera de lugar, le hemos propuesto (si hay posibilidad) proyectos más simples para su nivel. Un Sudoku sigue siendo de dificultad bastante alta y no todos son unos maestros de la programación... también tendrías que decirme dónde estoy contando mi vida...
En fin, puedes quedarte con tus comentarios innecesarios (al principio de tu mensaje) y limitarte a ayudarlo... como nosotros.

¡Hasta luego!
--
Utae Gamuza

Para la verificación de la cuadrícula, estoy de acuerdo, es fácil, pero esa no es la intención del proyecto.

Para la creación de la cuadrícula, no estoy de acuerdo, sin embargo, o te has expresado mal.
Tu método permite comenzar una cuadrícula, pero a menudo no permitirá terminarla.
Porque esto equivale a resolver un sudoku colocando los valores al azar entre los disponibles...
Funciona al principio, hasta cierto punto.
O bien, tu método consiste en intentar hacer cuadrículas de manera aleatoria hasta tener la suerte de encontrar una buena, lo que puede llevar bastante tiempo...

En cuanto a generar una cuadrícula eliminando valores al azar...
No solo corremos el riesgo de generar cuadrículas con múltiples soluciones, sino que también corremos el riesgo de generar cuadrículas imposibles de resolver (o al menos, muy, muy difíciles).

Tampoco estoy de acuerdo cuando dices que no respondemos a la pregunta.
Una parte importante de la pregunta es: "que realmente no soy buena".
He hecho un BTS de informática de gestión (hace 10 años), así que conozco el nivel.
Confieso que, al releer, entendí mal la pregunta, pensaba que iba a entrar en el BTS y no a pasar el examen, lo que explica mi primera respuesta.
Efectivamente, para un examen final, el 'encontrar el número' es demasiado simplista (lo programaba en mi calculadora en segundo de secundaria), pero, ya para ella, eso le permite hacerse una idea de su nivel, si lo que se le propone le parece fácil, entonces, efectivamente, puede intentar trabajar en algo más complicado.

--
¡Deja de fallar en la prueba de Turing!

o entonces, tu método consiste en intentar hacer rejillas de forma aleatoria hasta tener la suerte de encontrar una buena, lo que puede llevar bastante tiempo...

Absolutamente no. No es ni largo ni incorrecto. Solo elegimos un valor al azar entre los que aún están disponibles para la casilla. Restringimos el conjunto de valores disponibles para que las casillas afectadas por el valor que instalamos reciban en las siguientes iteraciones un valor coherente con el valor de la rejilla.

Por ejemplo, para un sudoku con n = 3, inicialmente tengo 9 valores disponibles para cada casilla. Tiro un valor entre 0 y 8 (lo que da 9 valores). Supongamos que saco el valor 6. Avanzo 6 veces en {0,1,2,3,4,5,6,7,8,9}, lo que corresponde al valor 6 que instalo en la casilla. Entonces elimino del dominio de las casillas del cuadrante superior izquierdo, de la fila superior y de la columna izquierda el valor 6.

Luego paso a la casilla inmediatamente a la derecha. El 6 ya no está disponible (por lo que quedan 8 valores disponibles). Tiro un valor entre 0 y 7 (lo que corresponde a una muestra de 8 valores). Supongamos que saco el valor 6. Avanzo 6 espacios en {0,1,2,3,4,5,7,8,9} para elegir mi valor, es decir, el valor 7. Luego retiro este valor en las casillas del cuadrante, de la fila y de la columna correspondientes. Y así sucesivamente.

Conclusión: recorremos una casilla una y solo una vez, para cada una de ellas hacemos un sorteo aleatorio que da sistemáticamente un valor admisible (y cuando el dominio se reduce a un elemento, ni siquiera necesitamos hacer el sorteo aleatorio, sabemos que es el único valor que podemos instalar en la casilla). En resumen, es un algoritmo polinómico, es rápido...

en cuanto a generar una rejilla eliminando valores al azar...
no solo corremos el riesgo de generar rejillas con múltiples soluciones, sino que también hay riesgo de generar rejillas imposibles de resolver (o al menos, muy muy difíciles)

No, porque partes de una solución admisible y eliminas ciertas casillas. Por lo tanto, al menos hay esa solución. En cuanto a tener múltiples soluciones, ya he explicado cómo evitar tener múltiples soluciones, pero si no eliminas demasiados valores, la rejilla estará lo suficientemente restringida como para admitir solo una (o pocas) soluciones. De todos modos, incluso si hay varias soluciones, eso no tiene importancia ya que el método de verificación no compara la solución que permitió generar la rejilla con la solución propuesta por el jugador.

No estoy de acuerdo tampoco cuando dices [...]

Bueno, el programa se reduce a 100 líneas y ya he dado la estructura del código. Como ves, son solo algunos bucles for, que deben ser una de las primeras cosas que se aprenden en algoritmia. La única dificultad del problema era reflexionar sobre el algoritmo y eso ya se le ha proporcionado. Y has visto que no hay nada de milagroso.

Además, si le decimos que el tema es generar un sudoku, ¿por qué desviarse a hablar de otros juegos? El objetivo del foro es responder a un problema, no cuestionar la declaración, ¿no?

Buena continuación.

Nada indica que el tema fuera impuesto: ella dice bien "... elegí ...". Lo ideal es de todos modos elegir un tema compatible con sus capacidades... De hecho, es preferible que al final, durante la defensa, el programa funcione. Lo digo en su propio interés y en ningún momento estuve fuera de tema...
He visto demasiadas personas durante mis estudios que eligieron un proyecto demasiado complejo para ellas y que fracasaron en la defensa.
El Sudoku puede parecerte fácil de realizar, pero no es necesariamente el caso de todos. Si no está segura de sí misma, lo mejor, como dice dna.factory, es que experimente lo que sabe hacer en un proyecto más simple...

--
Utae Gamuza

un foro de desarrolladores de sudoku: http://www.setbb.com/phpbb/?mforum=sudoku

Para mí, fue uno de mis proyectos de primer año: Programar un resolutor de sudoku en C en dos días.

No es "tan" complicado, en realidad hay que saber jugar sudoku básico para que tu programa tenga buenos algoritmos...

Personalmente, me paseaba con un array de 3 dimensiones para almacenar todos mis valores.

Aquí está el resultado de la batalla...

#include <iostream> #include <vector> #include <set> #include <cstdlib> #include <cassert> #define N 3 #define N2 N*N typedef std::set<unsigned> domaine_t; unsigned randint(unsigned max){ return (unsigned) (((double) rand()*(max+1))/RAND_MAX); } struct case_t{ domaine_t domaine; unsigned valeur; case_t(): valeur(0) { for(unsigned i=1;i<N2+1;++i) domaine.insert(i); } void supprimer(unsigned val){ domaine_t::iterator fit = domaine.find(val); if(fit != domaine.end()) domaine.erase(fit); } }; struct grille_t{ std::vector<std::vector<case_t> > data; grille_t(){ for(unsigned i=0;i<N2;++i){ data.push_back(std::vector<case_t>(N2,case_t())); } } void corriger(unsigned i,unsigned j,unsigned val){ assert(i < N2); assert(j < N2); // Virar val de la ligne i et de la colonne j for(unsigned k=0;k<N2;++k){ data[i][k].supprimer(val); data[k][j].supprimer(val); } // Virar val du cadran dont la case supérieure gauche // est (i0,j0) unsigned i0 = i / N2; unsigned j0 = j / N2; for(unsigned i1=0; i1<N; ++i1){ for(unsigned j1=0; j1<N; ++j1){ data[i0+i1][j0+j1].supprimer(val); } } } void generer(){ unsigned val, k, rnd; for(unsigned i=0;i<N2;++i){ for(unsigned j=0;j<N2;++j){ const domaine_t & d = data[i][j].domaine; rnd = randint(d.size()-1); // Tirer la valeur de la case (i,j) // (la rnd-ième valeur du domaine) domaine_t::const_iterator sit (d.begin()), send(d.end()); for(k=0;sit!=send && k < rnd;++sit, ++k); val = *sit; data[i][j].valeur = val; // Corriger les domaines corriger(i,j,val); } } } }; std::ostream & operator << (std::ostream & out,const grille_t & g){ for(unsigned i = 0; i < N2; ++i){ if(i%N == 0){ for(unsigned j = 0; j < N2 + N; ++j) out << '-'; out << std::endl; } for(unsigned j = 0; j < N2; ++j){ if (j%N == 0) out << '|'; out << g.data[i][j].valeur; } out << std::endl; } return out; } int main(){ // for(unsigned k=0;k<20;++k) std::cout << randint(9) << std::endl; grille_t grille; grille.generer(); std::cout << grille << std::endl; return 0; }

Como pueden ver, hice exactamente el algoritmo que les había anunciado. Van a estar contentos, hay un caso al que no había pensado. Pero como tenemos a muchos profesionales de la informática y ya está hecho lo más grande, estoy seguro de que aportarán la solución adecuada (bueno, no inicialicé la semilla del generador aleatorio, lo sé).

Esto es lo que da:

------------ |847|691|352 |536|478|910 |192|350|476 ------------ |283|765|194 |674|932|580 |951|840|237 ------------ |725|183|649 |419|207|803 |368|509|721 

Los 0 corresponden a casillas que no pudieron ser llenadas, típicamente la última de la segunda fila. De hecho, esto se debe a que en el momento de llenar las casillas del último cuadrante, solo hay dos valores admitidos (9 y 1) entre los tres que deberían colocarse (es decir, {1, 5, 9}. No siendo una mala perdedora, reconozco humildemente que fallé en este punto.

Cómo resolver el problema: es necesario mantener el dominio asociado a cada cuadrante y asegurarse de que al momento de insertar un valor en la cuadrícula no se quede sin valores para las casillas restantes, lo cual, admito, no es necesariamente trivial. Y viene bastante bien, porque de lo contrario hubiera bastado con copiar este código fuente para hacer el proyecto por su cuenta. Reconozco que no tengo las ganas de reflexionar más sobre esto esta noche, pero ya es una pista.

Respecto a la historia "lo que mencionas es un solucionador": sí, se parece y no tenemos realmente otra opción, pero si encuentras otro método, no dudes en compartirlo con nosotros.

En relación a "escribe el pseudocódigo", ya había hecho eso en mi primer mensaje.

En cuanto a sus mensajes: me alegra ver el entusiasmo que ponen en defender su punto de vista y su franqueza. De verdad. Ahora creo que el objetivo es avanzar en la resolución del problema, y espero de ustedes mensajes más constructivos que ayuden en esta dirección (no sirve de nada inundar un hilo de discusión con un debate; los mensajes privados son para eso). En lo que a mí respecta, eso es lo que he intentado hacer, espero su contribución, sobre todo porque por lo que creo entender, son buenos en informática. En fin, ¡impreséntenme! ;-)

Buena suerte.

Intenté hacer uno hace algún tiempo (en mi período de "locura") y me rompí los dientes con eso, en fin, no lo intentaré de nuevo (solo de pensarlo, me duele la cabeza)...
El asunto de la "O" es precisamente el defecto que dna.factory había detectado... ahora entiendes mejor la dificultad de realizar un programa así.
--
Utae Gamuza

1) Esto no es en absoluto lo que había anunciado dna.factory, ni siquiera había comprendido que el algoritmo generaba una cuadrícula aleatoria. Te remito a sus mensajes. En ningún momento planteó el problema del algoritmo que propuse. Además, si has seguido la discusión, verás que no todo lo que propuse es para desechar. Al contrario, incluso le mostré que, efectivamente, para generar una cuadrícula, teníamos casi el equivalente a un solucionador.

2) No propuso la más mínima aproximación constructiva para ayudarlo a resolver su problema. Simplemente se comportó como un padre con un "no lo lograrás, yo de todos modos soy el más jaja". Todavía estoy esperando ver al profesional en acción (y lo digo sinceramente, porque las tablas dinámicas de Excel en un programa C/C++ me hacen reír suavemente).

3) No tengo nada que demostrar, ni de qué avergonzarme. Reconozco que el tema es más difícil de lo que suponía al principio (ver mensaje anterior). No tengo ningún problema en reconocer que me he equivocado. Al menos intenté responder a la pregunta en lugar de comportarme como un padre y alimentar la discusión con mensajes que no sirven para nada. Esa es, al final, la única cosa que le he reprochado. Honestamente, ¿a quién le importa que tenga su BTS en informática? Si quiere contar su vida, hay foros en CCM para eso.

En lugar de contaminar este hilo con discusiones pueriles e interesantes, les invito, si lo desean, a continuar el debate en mensajes privados, estaré encantada de responder.

Con esto, cordialmente, que tengan una buena tarde.

Je suis ici pour vous aider.

Genial entonces, estamos en la misma sintonía... no importa si lo consideras fácil o no, lo importante es que sea posible para ella.
--
Utae Gamuza

voy a ser el rompe sueños...
deja el sudoku, no tienes el nivel...
es más de nivel de examen de fin de BTS.

si quieres hacer un programa de juego, empieza ya por 'adivina el número en el que pienso' (con más grande, menos grande)
es realmente la base de la programación, pero al menos te permite avanzar despacio.

--
¡Deja de fallar el test de Turing!