À chaque fois que vous choisissez deux tuiles, l’app de Shisen-Sho vérifie si « ces deux tuiles se relient par une ligne à au plus deux virages ». Pour chercher les paires retirables avec l’indice, la même vérification est appliquée à toutes les paires. Cet article présente ce fonctionnement avec un programme.

L’idée : élargir virage après virage

Une ligne avance tout droit à la verticale ou à l’horizontale, et tourne de temps en temps. On examine donc à partir de la première tuile de la façon suivante.

  1. 0 virage : depuis la première tuile, on avance tout droit vers le haut, le bas, la gauche et la droite, sur les cases libres. Si l’on atteint la deuxième tuile, elles se relient.
  2. 1 virage : depuis chacune des cases atteintes à l’étape 1, on change de direction et on avance de nouveau tout droit.
  3. 2 virages : depuis chacune des cases atteintes à l’étape 2, on change de direction et on avance encore tout droit.

Si l’on n’a pas atteint la deuxième tuile à la 3e étape, les tuiles ne se relient pas avec au plus 2 virages. On avance tout droit jusqu’à ce qu’on rencontre une tuile ou qu’on sorte du plateau.

Traiter l’extérieur du plateau

La ligne peut aussi passer par la case extérieure du plateau. Dans le programme, il suffit d’utiliser un plateau auquel on a ajouté un tour de cases libres pour traiter l’extérieur comme de simples cases libres. Pour un plateau de 6 colonnes × 8 rangées, on examine un plateau de 8 colonnes × 10 rangées.

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

Les deux 5 de Bambous aux extrémités de la rangée du haut de ce schéma se relient en 2 virages en passant par la case libre extérieure du haut.

Le programme

En JavaScript, cela donne ceci.

// board[r][c] est le nom de la tuile, null pour une case libre. On a ajouté un cadre de cases libres autour du plateau.
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 case où l’on est et la dernière direction suivie (au départ -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 est le plateau entouré d’un cadre de cases libres. Les cases avec une tuile contiennent le nom de la tuile, les cases libres contiennent null.
  • from et to sont les [rangée, colonne] des deux tuiles (leur position sur le plateau avec cadre).
  • frontier est la liste des cases atteintes avec le nombre de virages actuel, et de la direction par laquelle on y est arrivé.
  • Avancer encore dans la même direction a déjà été examiné à l’étape précédente, on le saute donc (d === dir).
  • seen retient qu’on est déjà arrivé sur une case dans une direction donnée, pour ne pas refaire le même examen.

Ce programme examine, après le deuxième virage, si l’on atteint la deuxième tuile en avançant tout droit. On ne peut pas passer sur une tuile, donc on s’arrête à la première rencontrée (seule la deuxième tuile est testée au moment où on l’atteint).

Comparaison avec l’app

J’ai comparé ce programme à la recherche de ligne de l’app (le même calcul que celui utilisé pour les schémas du site). J’ai fait fabriquer 300 plateaux de 48 tuiles, de la même façon que l’app, et fait vérifier 5044 paires de tuiles choisies au hasard, y compris sur des plateaux déjà en partie vidés : les réponses « se relient » et « ne se relient pas » étaient toutes identiques.

Dans l’app, quand deux tuiles se relient, on trace la ligne à l’écran : on retient donc non seulement si elles se relient, mais aussi la position des coudes. S’il y a plusieurs lignes possibles, on dessine celle qui a le moins de virages, et à égalité la plus courte.

Chercher toutes les paires retirables

Pour chercher les paires retirables, comme l’indice, on applique ce programme à chaque paire de tuiles identiques. Sur un plateau de 48 tuiles, il y a 72 paires possibles de tuiles identiques : 72 vérifications au maximum suffisent. Le nombre de paires retirables au départ est compté dans Combien de paires peut-on retirer au départ ?.