四川省(兩次轉彎消除)的 App,每次選兩張牌,都會判定「這兩張牌能不能用轉彎兩次以內的線連起來」。用提示尋找能消除的對時,也是對所有的對使用相同的判定。這篇文章要用程式來介紹這個原理。

想法:依轉彎次數逐步擴大

線是沿著直線或橫線筆直前進,偶爾轉彎。所以,從第 1 張牌開始,這樣依序檢查。

  1. 轉彎 0 次:從第 1 張牌往上下左右,沿著空格筆直前進。如果走到第 2 張牌,就連得起來。
  2. 轉彎 1 次:從 1 走得到的每一格,換個方向,再次筆直前進。
  3. 轉彎 2 次:從 2 走得到的每一格,換個方向,再筆直前進一次。

如果到第 3 次為止都沒走到第 2 張牌,就表示用兩次以內的轉彎連不起來。筆直前進,是走到撞上牌或是走出牌桌外為止。

牌桌外側的處理

線也可以通過牌桌外側的一圈空格。在程式裡,只要使用在牌桌四周多加一圈空格的牌桌,外側就能當成普通的空格來處理。6 列×8 行的牌桌,就用 8 列×10 行的牌桌來檢查。

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

這張圖上方列兩端的五條,通過上方外側的空格,轉彎 2 次就連起來了。

程式

用 JavaScript 寫,會像下面這樣。

// board[r][c] 是牌的名稱,空格是 null。牌桌四周各多加了一圈空格的外框。
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 是兩張牌的 [列, 行](加了外框之後的牌桌上的位置)。
  • frontier 是以目前的轉彎次數能走到的格子,以及走到那裡時的方向清單。
  • 往同一個方向繼續筆直前進,在前一輪已經檢查過了,所以跳過(d === dir)。
  • seen 是用來記住同一格已經從同一個方向到達過,避免重複檢查。

這個程式,會連第 2 次轉彎之後筆直前進所到之處,是否走到第 2 張牌都檢查。牌的上面不能通過,所以撞上就停下來(只有第 2 張牌,是在走到的當下判定)。

與 App 對照

我們把這個程式,拿來和 App 的找線方式(本站文章的圖也是用這個計算)比較。用和 App 相同的方式做出 300 局 48 張的牌桌,包括消到一半的牌桌在內,對隨機選的 5044 組牌做判定,結果連得起來、連不起來的答案全部一致。

App 在連得起來時會在畫面上畫線,所以不只記住能不能連起來,連轉角的位置也會記住。線有很多種畫法時,會選轉彎少的線,轉彎次數相同就選比較短的線來畫。

要找出所有能消除的對

像提示這樣尋找能消除的對時,是針對每一組相同圖案的兩張牌,用這個程式來判定。48 張的牌桌,相同圖案的組合有 72 組,所以最多判定 72 次就夠了。一開始能消除的對數,在一開始能消除幾對?裡數過了。