SUDOKU 1K para ZX-81
Publicado: 21 Jul 2013, 21:33
- DSC_1227.jpg (57.4 KiB) Visto 8202 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
En la zona inferior se deben entrar tres valores juntos:
1. Fila (0 a 8).
2. Columna (0 a 8).
3. Valor de la celda. Puede ser un número (1 a 9) o cualquier otro carácter.
BLOQUES
He dividido el listado en 5 bloques:
- Definición del Sudoku modelo.
- Desordenar las celdas del Sudoku.
- Mostrar el Sudoku por pantalla.
- Introducir las coordenadas y el valor.
- Revisar si el Sudoku es correcto.
COMO FUNCIONA
El programa ocupa 20 líneas.
A continuación detallo, línea por línea, el funcionamiento del programa.
Se utilizan las siguientes variables:
F – Variable para bucles.
I – Variable de apoyo.
U – Variable que contiene el valor “1”.
N – Variable que contiene el valor “9”.
A$ - Variable donde se guarda el Sudoku correcto.
B$ - Variable donde se guarda el Sudoku como se ve en pantalla.
C$ - Variable donde se guarda la casilla del movimiento.
10 – Introducimos un Sudoku correcto.
14 – Guardamos el valor 1 en la variable “U”.
16 – Guardamos el valor 9 en la variable “N”.
20 – Desordenamos las líneas del Sudoku. El método se detalla más adelante.
22 – Se vuelve a la línea 20 si un número aleatorio entre 0 y 8 es mayor de 1.
30 – Guardamos el Sudoku generado en la variable B$.
40 – Inicio de un bucle entre los valores 0 y 26 usado para ocultar celdas.
42 – Ocultamos una celda del Sudoku guardado en B$.
44 – Final del bucle.
50 – Se muestra el identificador de las casillas horizontales.
52 – Inicio de un bucle entre los valores 0 y 8.
54 – Imprimimos la posición vertical y una tira del Sudoku con 9 valores.
56 – Final del bucle.
60 – Introducimos la casilla en la variable “C$”.
62 - Si la longitud de “C$” es distinta de 3 se vuelve a 60.
64 – Guardamos en “I” el primer carácter de “C$”, que es la fila.
66 – Guardamos en “F” el segundo carácter de “C$”, que es la columna.
68 – Ponemos el valor introducido en la posición de pantalla correspondiente.
70 – Añadimos el valor introducido en la posición correspondiente de la variable “B$”.
86 – Si el Sudoku completo guardado en “A$” es distinto al guardado en B$ se salta a la línea 60, sino finaliza el programa.
EL PROGRAMA
- Listado.jpg (140.36 KiB) Visto 8202 veces
APUNTES FINALES
Jamás me había planteado meter un Sudoku en una máquina con 1 KB de RAM, pero visto que conseguí hacer funcionar un Mine-Field en 1 KB me lo tomé como un reto.
Partiendo del listado de la versión para el VIC-20 programada previamente, empecé a tachar líneas y bloques de código. Presentación, corrección, movimiento con teclas, etc. Todo fuera.
Al final quedó un listado mini, que había que conseguir encajarlo en el ZX-81. La verdad es que ha costado.
Peleando con la memoria (otra vez):
- Un ZX-81 básico dispone de 1024 bytes de RAM libres.
- Las variables de sistema ocupan 125 bytes.
- La memoria de video para un tablero de juego de 9x9 más los indicadores de fila y columna ocupan un total de 10x10=100 bytes, más los 25 bytes de final de línea, ocupan 125 bytes. Más unos 5 ó 6 de la zona del INPUT.
Total unos 130 bytes menos.
He conseguido reducir el uso de variables numéricas a 4, pero el problema está en las alfanuméricas que contienen el Sudoku correcto y el mostrado en pantalla. Almacenar la variable “A$” en el listado ocupa unos 90 bytes, pero a parte ocupa unos 85 bytes más en la zona de variables, más otros 85 para la variable “B$”. Y unos 8 para “C$”. En total las variables ocupan unos 300 bytes entre el listado y la zona de variables. Y esto ha ido un auténtico quebradero de cabeza.
Como va la memoria: 1024 – 125 – 125 - 300 = 474 bytes para el programa.
¿Como se hace?
El programa se ha desarrollado en un TIMEX SINCLAIR 1000 con 2 KB para evitar el engorro de programar con 1 KB y su molesta “escalada” de líneas en pantalla mientras programas. Así daba uso a este equipo, con el que nunca había programado.
Durante el desarrollo existía una línea:
4 DIM Z$(1012)
... que me ha permitido dejar el equipo con 1 KB durante la ejecución del programa. Si funciona aquí tendrá que funcionar en un ZX-81 con 1 KB sin ningún problema, como realmente ha sucedido.
¿Cómo generar un SUDOKU con un BASIC lento y sin memoria?
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 8202 veces
Aquí he aplicado la misma técnica que había usado previamente en la versión del COMMODORE VIC-20 y del SHARP MZ-80B. Básicamente consiste en introducir un Sudoku correcto, desordenarlo, y al final ocultar parte de las celdas. El Sudoku es correcto pero distinto del modelo base.
En esos programas se aplicaban tres técnicas:
1. Invertir el Sudoku diagonalmente.
2. Mover las columnas verticalmente.
3. Mover las filas horizontalmente.
Las primeras versiones del ZX-81 usaban las dos primeras técnicas, pero daba un error de memoria 4 durante la ejecución.
Así que he aplicado solo la técnica 2 pero he añadido una nueva que consiste en desordenar las filas de un bloque.
Con esto consigo hacer 9 combinaciones distintas a partir de un Sudoku original, y como cada vez se ocultan celdas distintas... parecen distintos.
- sudoku_3_vertical.gif (7.79 KiB) Visto 8202 veces
¿Como ahorrar memoria?
Visto que almacenar el Sudoku en el listado más lo que ocupan las variables A$ y B$ en la zona de variables se comen casi una tercera parte de la memoria, la primera decisión ha sido el “como guardarlo”. Tras muchas vueltas he prescindido de la opción REM como en el “Mine-Field” ya que su gestión posterior ocupaba demasiadas líneas de código.
Como usaré el valor 1 y 9 varias veces, he declarado una variable “U” y otra “N” con ese valor. Se ha declarado mediante un VAL porque el valor ocupa 7 bytes en la zona de variables, pero en la zona del programa ocupa 3 bytes menos que de la forma tradicional y queda más claro que con un CODE.
Como sustitutivo del valor 0 uso NOT PI ya que solo ocupa 2 bytes en lugar de los 5 habituales, y con combinaciones o cálculos de las variables “U” y “N” consigo otros valores.
He evitado el uso de GOSUB-RETURN y otras cosas y en todo momento el programa se ejecuta de arriba a abajo.
Todo el código que desordena el Sudoku base ocupa 2 líneas (22 - 22) y es bastante rápido.
La parte de entrada de datos es casi igual a la del “Mine-Field” pero aquí si válido la entrada. Más o menos.
Para forzar la detención del programa he hecho la validación del Sudoku al final del programa. Si no es correcto vuelve a la línea 60 y si es correcto acaba porque no hay más líneas.
Por suerte, el programa ha ido justo de memoria pero he podido usar VAL y no CODE en la mayoría de los casos. El programa es más comprensible.
¿Que me gustaría que hiciera y no hace?
A continuación hago una lista de los que me habría gustado poder incorporar en esta versión:
- Poder introducir varios Sudoku distintos y poder aplicar más métodos de desorden.
- Mostrar un tablero más claro.
- Validar los valores de entrada: “0 a 8” en los dos primeros valores, y “1 a 9 o espacio” en el tercero.
- Revisar el estado de juego.
- Mostrar el Sudoku correcto.
- Incorporar pantalla de presentación y niveles de dificultad.
Con todo, el programa ocupa menos de 500 bytes, funciona perfectamente y con una excelente velocidad, así que, al final…
Otra prueba superada ¡!!
Os invito a probarlo.
- DSC_1225.jpg (93.25 KiB) Visto 8202 veces
- DSC_1231.jpg (63.12 KiB) Visto 8202 veces
- DSC_1229.jpg (80.4 KiB) Visto 8202 veces
De ahí que en las "instrucciones" que escribí al lado de cada enlace al .P pusiera de qué forma se puede arrancar una nueva partida 
