四川省(二角取り)のアプリは、牌を2枚選ぶたびに「この2枚は曲がり2回以内の線でつながるか」を判定しています。ヒントで取れる組を探すときも、同じ判定を全部の組に使います。この記事では、そのしくみをプログラムで紹介します。

考え方:曲がった回数ごとに広げる

線は、縦か横にまっすぐ進み、ときどき曲がります。そこで、1枚目の牌から次のように調べます。

  1. 曲がり0回: 1枚目から上下左右に、空いたマスをまっすぐ進む。2枚目に着いたら、つながる。
  2. 曲がり1回: 1で進めたマスのそれぞれから、向きを変えて、またまっすぐ進む。
  3. 曲がり2回: 2で進めたマスのそれぞれから、向きを変えて、もう一度まっすぐ進む。

3回目までに2枚目に着かなければ、2回以内の曲がりではつながりません。まっすぐ進むのは、牌にぶつかるか、盤の外に出るところまでです。

盤の外側の扱い

線は盤の外側の1マスも通れます。プログラムでは、盤のまわりに空きのマスを1周ぶん足した盤を使えば、外側も普通の空きマスとして扱えます。6列×8行の盤なら、8列×10行の盤にして調べます。

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

この図の上の段の両端の五索は、上の外側の空きマスを通って、曲がり2回でつながります。

プログラム

JavaScriptで書くと、次のようになります。

// board[r][c] は牌の名前、空きは null。盤のまわりに空きの枠を1マスずつ足してある。
function canConnect(board, from, to) {
  const rows = board.length;
  const cols = board[0].length;
  const steps = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  // 今いるマスと、最後に進んだ向き(最初は -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 は、まわりに空きの枠を足した盤です。牌のマスには牌の名前、空きのマスには null が入っています。
  • from と to は、2枚の牌の [行, 列] です(枠を足した盤での位置)。
  • frontier は、今の曲がりの回数で着けるマスと、そこへ進んだ向きの一覧です。
  • 同じ向きにまっすぐ進むのは、前の回ですでに調べたので飛ばします(d === dir)。
  • seen は、同じマスに同じ向きで着いたことを覚えておき、同じ調べ直しをしないためのものです。

このプログラムは、2回目の曲がりのあとにまっすぐ進んだ先で、2枚目に着くかどうかまで調べます。牌の上は通れないので、ぶつかったところで止まります(2枚目の牌だけは、着いたところで判定します)。

アプリとの照合

このプログラムを、アプリと同じ線の探し方(サイトの記事の図にも使っている計算)と比べました。アプリと同じ作り方の48枚の盤を300局作り、途中まで取った盤も含めて、ばらばらに選んだ牌の組5044組で判定させたところ、つながる・つながらないの答えはすべて一致しました。

アプリでは、つながるときに画面に線を描くので、つながるかどうかだけでなく、曲がり角の位置も覚えておきます。線が何通りもあるときは、曲がりが少ない線、同じなら短い線を選んで描いています。

取れる組を全部探すには

ヒントのように取れる組を探すときは、同じ絵柄の2枚の組ごとに、このプログラムで判定します。48枚の盤では、同じ絵柄の組み合わせは72組なので、最大でも72回の判定で済みます。最初に取れる組の数は最初に取れる組は何組?で数えています。