- DSC_1019.JPG (70.76 KiB) Visto 6089 veces
EL JUEGO
El objetivo de un SUDOKU es rellenar una cuadrícula de 9x9, que a su vez está dividida en 9 regiones de 3x3, con números de 1 al 9 sin repetir ninguna cifra en la misma fila, columna y región.
El sistema muestra una cantidad de números, que no podemos modificar, y debemos deducir el resto hasta completar todas las casillas.
Controles:
Usa las teclas Q - A - O - P para mover el cursor por la cuadrícula.
Usa los números del 1 al 9 para poner ese número en la posición del cursor.
Pulsa el "0" para borrar el contenido de una celda.
Pulsa "CR" para revisar el estado del juego. Se borran los números erróneos y finaliza el juego si no hay fallos.
Pulsa "H" para que el programa ponga el número correcto en la posición del cursor.
Pulsa "R" para mostrar la solución del SUDOKU y finalizar la partida.
BLOQUES
He dividido el programa en 12 bloques:
- Definición de variables e inicialización.
- Control de teclas.
- Gestión del cursor: forma y posición.
- Poner número en una celda.
- Mostrar SUDOKU correcto.
- Corregir el SUDOKU introducido.
- Generar un SUDOKU.
- Mostrar el SUDOKU en pantalla.
- Pantalla de presentación.
- Imprimir la cabecera.
- Rutina de pulsar una tecla.
- Lista de SUDOKU correctos para generar las variantes.
COMO FUNCIONA
He optado por estructurar el programa con una instrucción por línea para facilitar su comprensión.
Se utilizan las siguientes variables, principalmente:
V() = Matriz donde se guardan el SUDOKU resuelto.
T() = Matriz donde se guarda los números que se ven en pantalla.
M() = Matriz donde se indican las casillas fijas (1) o modificables (0).
A$() = Matriz donde introducimos los SUDOKU predefinidos para generar los nuevos.
X = Posición horizontal del cursor respecto a las posiciones del tablero.
Y = Posición vertical del cursor respecto a las posiciones del tablero.
El resto de variables son utilizadas en distintos procesos sin ser de ámbito global.
10 - Definimos las matrices.
30 – Llamamos a la rutina que carga la matriz A$ con SUDOKUS predefinidos.
50 - Llamamos a la rutina que muestra la presentación (3000) y la que genera el SUDOKU (2000).
100 - Bloque con el que controlamos el teclado para mover el cursor, ayudar, corregir o resolver el SUDOKU.
400 - Muestra (G=2) o oculta (G=1) el cursor en la posición correspondiente.
500 - Calcula la posición del cursor en función del bloque de 3x3 en el que está.
600 - Pone el número indicado en la posición del cursor. Si el número es 0 lo borra del tablero.
700 - Muestra la solución del SUDOKU. Finaliza la partida.
800 - Rutina de revisión del SUDOKU introducido.
840 - Las casillas incorrectas se borran del tablero.
870 - En función de los fallos muestra un mensaje u otro.
920 - Si el SUDOKU es correcto se acaba el juego y salta a 50.
930 - Si no es correcto muestra el cursor y sigue la partida.
2000 - Seleccionamos uno de los 3 SUDOKU predefinidos y lo cargamos en B$.
2010 - Si un número aleatorio entre 0 y 1 es menos de 0.5 invertimos el tablero diagonalmente.
2070 - Decidimos si rotamos las columnas verticalmente, y cuantas posiciones (0 a 2).
2110 - Decidimos si rotamos las columnas horizontalmente, y cuantas posiciones (0 a 2).
2200 - Guardamos el SUDOKU en las matrices para su posterior control.
2280 - Ocultamos las celdas en función del nivel de dificultad seleccionado (L). N=L*8.
2500 - Mostramos el SUDOKU definitivo en pantalla.
3000 - Mostramos la pantalla de presentación.
3120 - Seleccionamos el nivel de dificultad pidiendo un número entre 1 y 8. Se guarda en (L).
4000 - Borramos la pantalla con CHR$(6) y ponemos la cabecera en vídeo inverso.
4100 - Rutina que espera a la pulsación de una tecla.
9000 - Guardamos los SUDOKU predefinidos en la matriz A$. Podemos entrar tantos como queramos.
EL PROGRAMA
Código: Seleccionar todo
10 DIM T(9, 9),V(9, 9),M(9, 9),A$(3)
30 GOSUB 9000
50 GOSUB 3000:GOSUB 2000
80 X=1:Y=1
90 G=2:GOSUB 400
'
' Gestion Teclas
'
100 GET K$:IF K$="" THEN 100
110 G=1:GOSUB 400
120 IF K$=CHR$(13) THEN 800
130 IF (K$="O")*(X>1) THEN X=X-1
140 IF (K$="P")*(X<9) THEN X=X+1
150 IF (K$="Q")*(Y>1) THEN Y=Y-1
160 IF (K$="A")*(Y<9) THEN Y=Y+1
170 IF K$="R" THEN 700
180 IF (K$>="0")*(K$<="9")*(M(Y,X)=0) THEN GOSUB 600
190 IF (K$="H")*(M(Y,X)=0) THEN K$=CHR$(48+V(Y,X)):GOSUB 600
200 G=2:GOSUB 400
210 GOTO 100
'
' Gestion Cursor
'
400 IF G=1 THEN C1$=" ":C2$=" "
410 IF G=2 THEN C1$="[":C2$="]"
420 GOSUB 500
430 CURSOR XX,YY:PRINT C1$
440 CURSOR XX+2,YY:PRINT C2$
450 RETURN
'
' Posicion Cursor
'
500 YY=Y*2+1
510 XX=X*3+3:XX=XX+INT((X-1)/3)
520 RETURN
'
' Poner Numero
'
600 T(Y,X)=VAL(K$):C1$=" "
610 IF T(Y,X)>0 THEN C1$=CHR$(176+T(Y,X))
620 CURSOR XX+1,YY:PRINT C1$
630 RETURN
'
' Mostrar Sudoku correcto
'
700 FOR Y=1 TO 9
710 FOR X=1 TO 9
720 IF M(Y,X)=1 THEN 740
730 GOSUB 500:CURSOR XX+1,YY:PRINT CHR$(176+V(Y,X))
740 NEXT X
750 NEXT Y
760 CURSOR 12,21:PRINT "TE HAS RENDIDO !!!"
770 GOSUB 4100
780 GOTO 50
'
' Corregir el Sudoku
'
800 N=0:F=X:I=Y
810 FOR Y=1 TO 9
820 FOR X=1 TO 9
830 IF T(Y,X)<>V(Y,X) THEN 850
840 N=N+1:K$="0":GOSUB 500:GOSUB 600
850 NEXT X
860 NEXT Y
870 IF N=0 THEN C$=" SUDOKU CORRECTO !!!"
880 IF N>0 THEN C$="SUDOKU CON "+STR$(N)+" ERRORES"
890 CURSOR 10,21:PRINT C$
900 GOSUB 4100
910 CURSOR 10,21:PRINT SPACE$(22)
920 IF N=0 THEN 50
930 X=F:Y=I
940 GOTO 90
' ***************************************
' * Generar el SUDOKU *
' ***************************************
2000 B$=A$(INT(RND(1)*3)+1)
' Invertir Diagonalmente
2010 IF RND(1)<.5 THEN 2070
2020 C$=""
2030 FOR G=81 TO 1 STEP -1
2040 C$=C$+MID$(B$,G,1)
2050 NEXT G
2060 B$=C$
' Rotar Verticalmente
2070 N=INT(RND(1)*3)
2080 FOR G=0 TO N
2090 B$=RIGHT$(B$,27)+LEFT$(B$,54)
2100 NEXT G
' Rotar Horizontalmente
2110 N=INT(RND(1) * 3)
2120 FOR G=0 TO N
2130 C$=""
2140 FOR F=0 TO 8
2150 I=F*9+1
2160 C$=C$+MID$(B$,I+3,6)+MID$(B$,I,3)
2170 NEXT F
2180 B$=C$
2190 NEXT G
' Guardar el tablero en la matriz
2200 N=1
2210 FOR Y=1 TO 9
2220 FOR X=1 TO 9
2230 G=VAL(MID$(B$,N,1))
2240 T(Y,X)=G:V(Y,X)=G:M(Y,X)=1
2250 N=N+1
2260 NEXT X
2270 NEXT Y
' Ocultar parte de las celdas
2280 N=8*L
2290 FOR F=1 TO N
2300 X=INT(RND(1)*9)+1:Y=INT(RND(1)*9)+1
2310 IF T(Y,X)=0 THEN 2300
2320 T(Y,X)=0:M(Y,X)=0
2330 NEXT F
'
' Imprimir el Sudoku Final
'
2500 GOSUB 4000
2510 CURSOR 5,2:PRINT "ÚÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄ¿"
2520 FOR F=1 TO 3
2530 FOR I=1 TO 5
2540 PRINT TAB(5); "³ ³ ³ ³";
2550 NEXT I
2560 IF F<3 THEN PRINT TAB(5); "ÃÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄ´"
2570 NEXT F
2580 PRINT TAB(5); "ÀÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÙ";
2590 FOR Y=1 TO 9
2600 FOR X=1 TO 9
2610 IF T(Y,X) <> 0 THEN GOSUB 500:CURSOR XX,YY:PRINT V(Y,X)
2620 NEXT X
2630 NEXT Y
2640 CURSOR 0,22:PRINT " [CR]:Corregir [H]:Ayuda [R]:Resolver "
2650 RETURN
'
' Pantalla de Presentacion
'
3000 GOSUB 4000
3010 PRINT "Resuelve el SUDOKU teniendo en cuenta"
3020 PRINT "que no se puede repetir el mismo numero"
3030 PRINT "en la misma fila, columna o bloque."
3040 PRINT:PRINT:PRINT:PRINT
3050 PRINT "Utiliza las teclas:":PRINT
3060 PRINT " Cursor: Q Numeros: 1-9"
3070 PRINT " O + P"
3080 PRINT " A Anular: 0"
3090 PRINT:PRINT:PRINT
3100 PRINT "Selecciona el nivel de dificultad:":PRINT
3110 PRINT "Dificultad: 1=Facil - 8=Dificil"
3120 GOSUB 4100:IF (K$<"1")+(K$>"8") THEN 3120
3130 L=VAL(K$)
3140 RETURN
'
' Imprimir la Cabecera
'
4000 PRINT CHR$(6);" SUDOKU-80B (C) SCAINET SOFT, 2013 ":PRINT
4010 RETURN
'
' Rutina Pulsar Tecla
'
4100 GET K$:IF K$="" THEN 4100
4110 RETURN
'
' Datos de SUDOKUS Correctos
'
9000 A$(1)="835416927296857431417293658569134782123678549748529163652781394981345276374962815"
9010 A$(2)="357964281468123579912587463631795842724318695895246137176459328583672914249831756"
9020 A$(3)="845967312723814956961532748359178624617243895284659137576491283492386571138725469"
9030 RETURN
Atención:
En las líneas 2510, 2540, 2560 y 2580 se deben sustituir los caracteres que aparecen en el listado por los correspondientes de los gráficos que aparecen en la foto del juego.
EL PROYECTO
El objetivo del programa consistía en investigar un método para generar SUDOKUS automáticamente, y trasladarlo al BASIC de sistemas de 8 bits. Esto quiere decir que el proceso debía ser rápido y sencillo.
Lo que en un principio parecía algo trivial se convirtió en un quebradero de cabeza. Pero como dicen que más vale “maña que fuerza”, al final he recurrido a una solución más que digna que funciona bien, y sobretodo muy rápidamente.
La primera en la frente
En un PC moderno programo una sencilla rutina que genera una matriz de 9x9 números aleatoriamente, con la particularidad de que no pueden coincidir dos números iguales en una misma fila y columna. El proceso tarda unos 30 segundos en finalizar. Es demasiado.
Miro el tiempo que tarda en generar cada una de las filas y me encuentro que las 7 primeras se calculan en 1 segundo, la 8 en unos 2 segundos y la 9 entre 8 y 10 segundos. La última tarda el triple que las ocho anteriores juntas. No puede ser.
Pensando llego a la conclusión que la suma de cada fila es igual a 1+2+3+4+5+6+7+8+9=45. De esta forma, la última fila es 45 menos la suma de los ocho números que tiene encima. Al generar cada fila guardo la suma de cada columna y consigo que todo el proceso tarde unos 3 segundos. Bien.
Pero hay un problema. No tengo en cuenta que el SUDOKU se divide en bloques de 3x3 y esto hace que según mi proceso en un mismo bloque se pueda repetir hasta 3 veces un mismo número. Mal vamos.
Pensando como ordenarlo llego a la conclusión que en 8 bits y con un BASIC interpretado el proceso será eterno. Abandono.
Un problema a partir de una solución
Le sigo dando vueltas al tema porque quiero que con mi SHARP MZ-80B se puedan hacer SUDOKUS.
Analizando bien un SUDOKU ya completado veo que realmente se pueden dividir en 3 filas o en 3 columnas, como se puede ver en la siguiente imagen. Si se mueven estas filas o columnas, el SUDOKU sigue siendo perfectamente válido.
- sudoku_1_estructura.gif (8.87 KiB) Visto 6089 veces
Así que mi proceso consistirá en introducir un SUDOKU correcto y desordenarlo.
Se puede desordenar de muchas formas, pero yo lo voy a limitar a 3.
1.- Inversión diagonal.
Según mi proceso, hay un 50% de posibilidades de invertir el tablero.
Esto quiere decir que el primer número será el último, el segundo será el penúltimo y así sucesivamente.
- sudoku_2_inverso.gif (6.77 KiB) Visto 6089 veces
2.- Mover bloques verticalmente
Calculo un número entre 0 y 2 que indica las veces que voy a mover la primera fila. Acabará en una de las tres posiciones.
- sudoku_3_vertical.gif (7.26 KiB) Visto 6089 veces
3.- Mover bloques horizontalmente
Calculo un número entre 0 y 2 que indica las veces que voy a mover la primera columna. Acabará en una de las tres posiciones.
- sudoku_4_horizontal.gif (7.44 KiB) Visto 6089 veces
Estas 3 formas hacen que a partir de un SUDOKU se puedan generar 18 variantes.
Introduzco 3 SUDOKUS correctos, con lo que puedo generar hasta 54 SUDOKUS "diferentes".
Teniendo en cuenta que después, y en función de la dificultad, se ocultan un número de celdas, la posibilidad de "reconocer" el SUDOKU son ínfimas. En la imagen se ve como quedan los nueve bloques de 3x3 después del proceso de desordenado.
- sudoku_5_listo.gif (8.21 KiB) Visto 6089 veces
Prueba superadas.
Genero un SUDOKU en menos de 5 segundos !!!
APUNTES FINALES
Mi primera intención era usar este equipo para programar una versión del "Campo Minado" en modo gráfico de 320x200.
Mi SHARP MZ-80B dispone de 32 KB, pero al cargar el BASIC desde cinta solo quedan unos 12 KB libres. El problema es que al activar el modo gráfico se reserva casi 10 KB y me quedan solo 2 KB para el programa. No entra ni con calzador.
Siguiendo con el equipo, viendo las fotos se puede comprobar que es un SEÑOR EQUIPO (si, en mayúsculas). A pesar de ser un equipo del año 1981 dispone de una línea más moderna, con ángulos rectos, a diferencia de otros equipos de esa época más "redondeados". Tanto el equipo como el teclado son realmente robustos.
El equipo dispone de un modo de 80 columnas (CONSOLE C80), pero para este proyecto he preferido usar el modo de 40 columnas, ya que la pantalla aparece más llena. La calidad de imagen es perfecta a pesar de ser monocromo.
El tema de la monocromía me planteó la forma de diferenciar las celdas fijas de las variables. Suerte que su juego de caracteres, compatible con ASCII a diferencia del SHARP MZ-700, tiene una copia de los caracteres en modo video inverso. Tema solucionado.
Respecto a su BASIC, es casi idéntico al del SHARP MZ-700, pero con el añadido de comandos gráficos y para manejar el casete. Si, desde el BASIC podemos avanzar y retroceder el casete, entre otras cosas. No lo había visto nunca.
La parte de generar el SUDOKU se desarrolló inicialmente en un PC moderno. Una vez encontrada la forma de generar el SUDOKU seguí con el desarrollo en el SHARP MZ-80B. Sea como sea, el programa es fácilmente adaptable a cualquier BASIC ya que se ha programado usando comandos estándar. Excepto el CURSOR (LOCATE en Microsoft BASIC) y poca cosa más, el 99% del código debería ser idéntico.
Yo me he tomado la molestia de introducir 3 SUDOKU predefinidos distintos, pero lo suyo sería introducir más e incorporar nuevas formas de desordenarlos. El número de combinaciones se dispararía.
Para terminar, decir que no me gustan los SUDOKU pero me lo he pasado muy bien descubriendo sus interioridades.
Os invito a probarlo.
- DSC_1031.JPG (78.17 KiB) Visto 6089 veces
- DSC_1015.JPG (82.91 KiB) Visto 6089 veces
- DSC_1022.JPG (112.78 KiB) Visto 6089 veces
- DSC_1023.JPG (105.89 KiB) Visto 6089 veces
- DSC_1026.JPG (124.59 KiB) Visto 6089 veces
- DSC_1028.JPG (144.77 KiB) Visto 6089 veces
- DSC_1036.JPG (60.37 KiB) Visto 6089 veces
