Comentarios sobre algunos de los detalles de implementación de una versión del popular juego del Sudoku escrita en JavaScript.

Este juego se popularizó en todo el mundo durante el año 2005. El objetivo es rellenar una cuadrícula de 9×9 con números del 1 al 9 de forma que no se repitan dentro de una misma fila o columna, ni dentro de las 9 cuadrículas de 3×3 que contiene. Como guía en la búsqueda de una solución se suministra una serie de números ya colocados en su posición correcta.

En realidad la descripción anterior corresponde a la versión más popular y más conocida del juego. Existen muchas otras variaciones del mismo que utilizan ese esquema de partida, pero con modificaciones o añadidos, como utilizar letras en vez de números, usar cuadrículas de mayor o menor tamaño, o cambiar las cuadrículas por regiones de diversas formas y colores.

Técnicamente no resulta muy difícil de programar, ya que la parte gráfica se limita a una tabla de 9×9, y el único proceso de importancia a implementar es el de la generación aleatoria del Sudoku.

Código fuente

Al ser un programa escrito completamente en JavaScript, todo el código fuente se encuentra embebido dentro de la propia página HTML desde la que se ejecuta el juego, por lo que para acceder al mismo basta con seleccionar la opción «ver código fuente de la página» del navegador.

Clases

El juego se compone de las siguientes clases:

– Game: Es la clase que representa la aplicación. Instancia el tablero y le cede el control cuando se inicia el juego o se pulsa el botón de validación.

– Board: Contiene el algoritmo de generación aleatoria del Sudoku y el método de validación de la solución propuesta.

– Grid: Esta clase representa la cuadrícula sobre la que se disponen los números. Contiene atributos que definen las dimensiones de la rejilla de juego, así como los números concretos a utilizar o el número de pistas a mostrar.

Cuadrícula

La cuadrícula de juego es una tabla HTML de 3×3, de forma que dentro de cada una de las celdas de esta tabla hay otra tabla anidada de 3×3, y a su vez, dentro de cada una de las celdas de estas tablas anidadas hay un campo de edición, que es finalmente donde realmente se muestran y editan los números.

El aspecto de los bordes de cada una de las tablas se controla con tres clases CSS y los atributos cellspacing y cellpadding de cada una de las tablas. La parte más difícil estuvo, además de en la elección de fuentes, tamaños y colores, en las conocidas diferencias que existen entre Firefox e Internet Explorer a la hora de visualizar una misma página HTML. Mi solución final después de varias pruebas fue utilizar un tamaño fijo para los campos de edición consiguiendo que se visualicen de forma muy similar en ambos navegadores.

Otro detalle importante a tener en cuenta, y que me dió algún que otro quebradero de cabeza, fue la forma en la que se tratan los datos introducidos en los campos de edición. Resulta que cuando se «refresca» la página, pulsando F5 normalmente, los datos introducidos no se pierden, son retenidos de forma local. Para borrarlos completamente hay que «recargar» la página, pulsando Control+R normalmente. Esta forma de trabajar hacía que los números introducidos no se borraran de la cuadrícula entre partida y partida. Lo solucione con un pequeño hack consistente en capturar la tecla «F5» y forzar la recarga completa de la página.

document.onkeydown = function(e){
  if( getKeyCode(e) == 116) {
     window.location.reload(true);
     return(false);
    }
}

Y un último detalle que no quiero dejar de comentar, es que en Firefox, cuando se pulsa la tecla Escape, se borra el campo de edición sobre el que se encuentra el cursor, mientras que en Internet Explorer se borran todos los campos contenidos dentro del formulario en el que se encuentre el cursor. Esto hacía que se borraran de golpe todos los números de la cuadrícula, incluidos los estáticos puestos como pistas para la resolución. Para evitar este efecto no deseado quité el formulario (tags <form> y </form>) que había puesto en un principio conteniendo a los campos de edición y dejé sólo los campos de edición.

Generación del Sudoku

El algoritmo de generación de Sudoku se basa en la técnica de BackTracking. Esta es una técnica de ensayo y error con retroceso, lo que significa que consiste en escoger una solución parcial inicial, refinarla, probarla, y retroceder a la solución anterior si la nueva no constituye una solución válida.

El algoritmo que he implementado recorre todas las casillas de las cuadrícula partiendo de la esquina superior izquierda y terminando en la inferior derecha haciendo un barrido por filas de la misma. Genera un número aleatorio de 1 a 9 para la primera casilla, comprueba que constituye una solución válida y repite el mismo proceso con la siguiente casilla. Si un número generado no supone una solución válida entonces se prueba con otro número. Y si se prueban los 9 posibles números en una casilla sin generar una solución válida entonces se retrocede a la casilla anterior para probar otro número en ella, y así sucesivamente.

La forma más natural de implementar esta técnica es mediante el uso de recursividad, ya que ésta permite retroceder una serie de pasos fácilmente deshaciendo los cambios hechos hasta un cierto momento. En el programa la función recursiva se llama generateCell, y admite como parámetro un identificador de la casilla para la que se quiere generar un número. El identificador no es más que un número de 0 a 80 que corresponde a cada una de las casillas de la cuadrícula. La función retorna true cuando es capaz de generar una nueva solución válida y false cuando no puede. La solución en curso se encuentra almacenada en todo momento en una variable llamada sudoku (fácil, eh), y que no es más que una matriz de 9 filas por 9 columnas.

Lo primero que hace la función es comprobar si se ha terminado de generar una solución válida y completa. Es decir, si se han rellenado todas las casillas de todas las filas y columnas:

  this.generateCell = function(id) {
    if (id == this.grid.rows * this.grid.cols)
      return(true);

Lo siguiente que hace es convertir el identificador en un par (fila, columna):

    var row  = Math.floor(id / this.grid.rows);
    var col  = id - (row * this.grid.rows)

A continuación genera una secuencia aleatoria de 9 números del 1 al 9 mediante la función shuffle que se encarga de «barajarlos» y generar una secuencia distinta cada vez. Haciéndolo de esta forma se consigue sólo probar los nueve números sólo una vez, y permite que en vez de utilizar números se pueda utilizar otros tipos de elementos para el Sudoku, como letras por ejemplo.

Los números de la secuencia se van probando uno a uno añadiéndolos a la solución actual en curso y validando si la nueva solución propuesta sigue siendo válida. Si la solución es válida se produce la llamada recursiva a la función para la siguiente celda, y si no es válida se itera dentro de la secuencia para probar el siguiente número.

    var suit = this.shuffle(this.grid.suit);
   
    for (var index in suit) {
      this.sudoku[row][col] = suit[index];

      if ( this.isValidCell(row, col) )
        if ( this.generateCell(id + 1) )
          return(true);
    }

Si no es posible generar una solución válida se borra el último valor probado en la celda en curso y se devuelve false para retroceder y deshacer el paso anterior.

    this.sudoku[row][col] = null;
    return(false);
  }

El algoritmo funciona razonablemente bien en un ordenador rápido, pero tiene el problema de que tanto la solución inicial como los números que se le van añadiendo para refinarla son generados de forma totalmente aleatoria, por lo que puede ocurrir que genere soluciones ciertamente malas y que tenga que deshacerse muchos de los pasos efectuados hasta encauzar el árbol de resolución por una rama que lleve a una solución válida.

Por otra parte, debe ser claro que el algoritmo deja mucho que desear, en cuanto a rendimiento se refiere, y admite muchas mejoras. Por ejemplo, la primera comprobación que hace la función puede simplificarse utilizando una constante en vez de hacer en cada iteración una multiplicación, o retroceder desde la última celda hasta la primera para que la comprobación se haga contra el valor cero. Otro punto que podría mejorarse es la conversión entre identificador y par (fila, columna), ya que se realiza una división y una llamada a la función floor en cada iteración. Lo que habría que hacer es eliminar la conversión trabajando sólo con el identificador, utilizando por ejemplo una tabla precalculada con el par que corresponde a un identificador concreto, o no haciendo ninguna conversión en absoluto.

Validación del Sudoku

La función de validación de las soluciones generadas en cada iteración se llama isValidCell:

  this.isValidCell = function(row, col) {
    return( this.isValidRow(row, col) &&
            this.isValidColumn(row, col) &&
            this.isValidRegion(row, col) );
  }

La función se limita a comprobar que la fila, columna y región actual en curso siguen siendo válidas.

Las funciones isValidRow e isValidColumn son muy parecidas, y comprueban que un determinado número no aparezca más de una vez dentro de la fila o columna que está siendo examinada. Valga de ejemplo la función de comprobación de filas:

  this.isValidRow = function(row, col) {
    var count = new Array();
    for (var c = 0; c <= col; ++ c) {
      if (count[ this.sudoku[row][c] ] != null)
        return(false);
      count[ this.sudoku[row][c] ] = 1;
    }
    return(true);
  }

Por último, la función de validación de regiones se limita a comprobar que no aparece un mismo número más de una vez dentro de la región actual en curso.

  this.isValidRegion = function(row, col) {
    var count = new Array();
    var rowi  = this.grid.region * Math.floor(row / this.grid.region);
    var coli  = this.grid.region * Math.floor(col / this.grid.region);

    for (var r = rowi; r <= row; ++ r)
      for (var c = coli; c <= col; ++ c) {
        if ( count[ this.sudoku[r][c] ] != null)
          return(false);
        count[ this.sudoku[r][c] ] = 1;
      }

    return(true);
  }

Estas funciones son de gran importancia dentro del algoritmo de generación de soluciones, ya que son llamadas para cada una de las soluciones parciales encontradas, y deberían optimizarse considerablemente reduciendo las operaciones que realizan y detectando los casos especiales para los que no son necesarios ejecutar todas las comprobaciones.

Pistas

Los números que se muestran en azul para ayudar a la resolución del Sudoku se eligen aleatoriamente mediante la función showTips:

  this.showTips = function() {
    var spans = this.shuffle(this.grid.spans);
    for (var row = 0; row < this.grid.rows; ++ row) {
      var tips = this.shuffle(this.grid.tips);
      for (var col = 0; col < spans[row]; ++ col)
        this.grid.setCellValue(row, tips[col], this.sudoku[row][ tips[col] ]);
    }
  }

El número de pistas totales a mostrar cada vez es el mismo, ya que está predeterminado que se muestren 4 números en tres de las filas, 3 números en otras tres de las filas, y 2 números en las tres filas restantes. Lo que varía de partida en partida son las filas y columnas concretas en las que se muestran. Para conseguirlo se «barajan» dos arrays, primero uno que contiene el número de pistas a mostrar por fila, y después otro que contiene las posibles columnas dentro de una fila.

Posibles mejoras

El juego admite muchas mejoras, cito a continuación algunas de ellas:

– Añadir un pequeño reloj contador de tiempo. De esta forma el jugador no sólo competiría contra el tablero, sino también contra el tiempo.

– Si se añade un contador de tiempo entonces también sería interesante salvar el mejor tiempo conseguido, dando así otro motivo para continuar jugando.

– También debería poder guardarse el Sudoku en juego, para poder recuperarlo posteriormente y continuar la partida.

– Añadir indicadores visuales por fila, columna y región que indiquen si son correctas o no. Estos indicadores deberían poder desactivarse para que los jugadores más avanzados no lo encuentren demasiado «fácil».

– Permitir a los jugadores marcar las celdas de números con algún tipo de identificativo, color o texto, para facilitar las pruebas o descartes de determinados números.

– Mejorar el algoritmo de generación del Sudoku para aumentar el rendimiento y versatibilidad del mismo.

– Controlar la dificultad del Sudoku generado. Esto puede hacerse generando un Sudoku y tratando de resolverlo algorítmicamente. En función de los pasos y métodos utilizados para su resolución se puede determinar lo que puede llegar a costar solucionarlo por un jugador humano.