四川省(二角取り)のアプリは、牌を2枚選ぶたびに「この2枚は曲がり2回以内の線でつながるか」を判定しています。ヒントで取れる組を探すときも、同じ判定を全部の組に使います。この記事では、そのしくみをプログラムで紹介します。
考え方:曲がった回数ごとに広げる
線は、縦か横にまっすぐ進み、ときどき曲がります。そこで、1枚目の牌から次のように調べます。
- 曲がり0回: 1枚目から上下左右に、空いたマスをまっすぐ進む。2枚目に着いたら、つながる。
- 曲がり1回: 1で進めたマスのそれぞれから、向きを変えて、またまっすぐ進む。
- 曲がり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回の判定で済みます。最初に取れる組の数は最初に取れる組は何組?で数えています。
