新接龍因為所有的牌都看得到,很適合用電腦來找解法。這篇文章要淺顯地介紹電腦是怎麼解新接龍的。為了這一頁,我們寫了一個依「新接龍」App 相同規則運作的程式來試驗。
搜尋:一邊走步,一邊往後查
電腦和人一樣,會查「走了這一步會變成怎樣」。不同的是數量。
- 把現在的牌局能走的步驟全部列出來(放進空白欄、疊到牌列、放到目標欄等)。
- 走其中一步,做出新的牌局。
- 在那個牌局上,再把能走的步驟全部列出來。
- 找到目標欄放滿 52 張的牌局,走到那裡的步驟就是答案。
這種「從一個牌局走到下一個牌局,一路分岔下去」的做法,叫做搜尋。
做法 1:不重複查同一個牌局
新接龍裡,用不同的順序移動,常常會走到同一個牌局。把牌往右移,再移回左邊,就是原來的牌局。把查過的牌局記下來,遇到相同的牌局就不查,浪費就會大幅減少。
另外,只有列的順序不同的牌局,或是只有空白欄裡的排列不同的牌局,解法也是一樣的。把它們當作同一個牌局處理,要查的數量還能更少。
做法 2:從看起來有希望的牌局開始查
把所有的牌局依序查下去,太花時間。所以要給「目標欄放上去的張數多」、「接下來想放到目標欄的牌上面,壓著的張數少」、「空白欄有空著」之類的分數,從看起來有希望的牌局先查。
用本頁的程式去解 Windows 新接龍第 1 號牌局,查了 843 個牌局,就找到了 110 步的解法。人要想會很辛苦,對電腦來說卻是一瞬間。找到的步驟,不一定是最短的步驟(步數與過關的步數)。
確認解不開
找到解法的話,那個牌局就是解得開的。那麼,「解不開」要怎麼確認呢?
答案是:把走得到的牌局全部查完。不論走哪一步,都不再出現新的牌局,而且其中也沒有放滿 52 張的牌局,就能知道那個牌局解不開。
Windows 新接龍的第 11982 號,是有名的解不開的牌局。本頁的程式也是,第 11982 號連從目標欄拿回牌的走法都算進去,把走得到的牌局(約 9 萬 5 千種)全部查完,也沒有解法(新接龍幾乎都解得開)。
一起移動牌的規定,和解不解得開無關
「新接龍」App 一次能移動的,是「空著的空白欄數 + 1」張,有空列時也不會增加(一次能移動的張數)。不過,一起移動的步驟,可以拆成利用空白欄和空列的一張一張的步驟。走得到的牌局是一樣的,所以解得開的牌局也一樣。改變的只有步數的算法。
「新接龍」App 牌局的驗算
「新接龍」App 的牌局,每次都是隨機洗亂後發牌。作者用電腦解了隨機的 10 萬種牌局,並把找到的解法,用和 App 相同的遊戲機制實際走到最後確認過。結果,10 萬種全部都有解法。
不過,這並不是「所有的牌局都解得開」的證明。沒查過的牌局之中,還是有可能偶爾有解不開的。
解法的想法,人在玩的時候也派得上用場。也請看看新接龍的攻略與必勝法。
