Cada vez que eliges dos fichas, la app de Shisen-Sho (dos giros como máximo) decide si «estas dos fichas se pueden unir con una línea de dos giros como máximo». Para buscar parejas con la pista se usa la misma comprobación con todas las parejas posibles. En este artículo te mostramos cómo funciona con un programa.

La idea: ampliar el alcance por cada giro

Una línea avanza en recto en vertical o en horizontal y de vez en cuando gira. Así que, desde la primera ficha, se comprueba lo siguiente:

  1. 0 giros: desde la primera ficha, avanzar en recto hacia arriba, abajo, izquierda y derecha por las casillas libres. Si se llega a la segunda ficha, se unen.
  2. 1 giro: desde cada casilla a la que se llegó en el paso 1, cambiar de dirección y avanzar otra vez en recto.
  3. 2 giros: desde cada casilla a la que se llegó en el paso 2, cambiar de dirección y avanzar en recto una vez más.

Si en el tercer paso no se ha llegado a la segunda ficha, no se pueden unir con dos giros como máximo. Se avanza en recto hasta chocar con una ficha o salir del tablero.

Cómo se trata el borde exterior

Las líneas también pueden pasar por la casilla exterior del tablero. En el programa, si usas un tablero al que se le añade una vuelta de casillas libres alrededor, el exterior se trata como unas casillas libres más. Con un tablero de 6 columnas × 8 filas, se comprueba como un tablero de 8 columnas × 10 filas.

五索二萬三萬五索東南西北

Los dos 5 de Bambú de los extremos de la fila de arriba de esta figura se unen con dos giros por las casillas libres del exterior de arriba.

El programa

En JavaScript queda así:

// board[r][c] es el nombre de la ficha y las casillas libres son null. Se ha añadido un marco de casillas libres alrededor del tablero.
function canConnect(board, from, to) {
  const rows = board.length;
  const cols = board[0].length;
  const steps = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  // La casilla actual y la última dirección en que se avanzó (al principio -1)
  let frontier = [[from[0], from[1], -1]];
  const seen = new Set();
  for (let turn = 0; turn <= 2; turn++) {
    const next = [];
    for (const [r0, c0, dir] of frontier) {
      for (let d = 0; d < 4; d++) {
        if (d === dir) continue;
        let r = r0;
        let c = c0;
        while (true) {
          r += steps[d][0];
          c += steps[d][1];
          if (r < 0 || c < 0 || r >= rows || c >= cols) break;
          if (r === to[0] && c === to[1]) return true;
          if (board[r][c] !== null) break;
          const key = r + ',' + c + ',' + d;
          if (!seen.has(key)) {
            seen.add(key);
            next.push([r, c, d]);
          }
        }
      }
    }
    frontier = next;
  }
  return false;
}
  • board es el tablero con el marco de casillas libres alrededor. Las casillas con ficha contienen el nombre de la ficha y las libres contienen null.
  • from y to son el [fila, columna] de las dos fichas (su posición en el tablero con el marco añadido).
  • frontier es la lista de casillas a las que se puede llegar con el número actual de giros, junto con la dirección en que se llegó.
  • Avanzar en la misma dirección en que ya se venía se omite, porque se comprobó en el paso anterior (d === dir).
  • seen recuerda que ya se llegó a una casilla en una dirección, para no repetir la misma comprobación.

Este programa comprueba, después del segundo giro, si avanzando en recto se llega a la segunda ficha. No se puede pasar por encima de una ficha, así que se detiene al chocar con ella (solo la segunda ficha se comprueba en el momento de llegar).

Comparación con la app

Comparamos este programa con el método de búsqueda de líneas que usa la app (el mismo cálculo que se usa para las figuras de los artículos del sitio). Generamos 300 tableros de 48 fichas con el mismo método de reparto que la app y, incluyendo tableros con parte de las fichas ya quitadas, pedimos que decidiera para 5044 parejas de fichas elegidas al azar. Todas las respuestas de «se unen» y «no se unen» coincidieron.

Cuando se unen, la app dibuja la línea en pantalla, así que además de si se unen guarda la posición de los giros. Cuando hay varias líneas posibles, elige la de menos giros y, si empatan, la más corta.

Buscar todas las parejas disponibles

Para buscar las parejas que se pueden quitar, como hace la pista, se aplica este programa a cada pareja de fichas con el mismo dibujo. En un tablero de 48 fichas hay 72 combinaciones de fichas iguales, así que bastan 72 comprobaciones como máximo. El número de parejas disponibles al empezar se cuenta en ¿cuántas parejas se pueden quitar al empezar?.