论文标题
解决Shisen-Sho板
Solving Shisen-Sho boards
论文作者
论文摘要
我们简单地证明了确定Shisen-Sho板的可溶性是NP完整的。此外，我们表明，在现实的假设下，如果两个图块形成可播放的对，则可以在对数时间中计算。 我们结合了算法的实现，以测试对配对的可玩性与我较早的算法，以求解Mahjong Solitaire板，以获取算法来求解Shisen-Sho-Sho板。我们为Shisen-Sho和Mahjong Solitaire采样了几个Shisen-Sho和Mahjong Solitaire布局。
We give a simple proof of that determining solvability of Shisen-Sho boards is NP-complete. Furthermore, we show that under realistic assumptions, one can compute in logarithmic time if two tiles form a playable pair. We combine an implementation of the algoritm to test playability of pairs with my earlier algorithm to solve Mahjong Solitaire boards with peeking, to obtain an algorithm to solve Shisen-Sho boards. We sample several Shisen-Sho and Mahjong Solitaire layouts for solvability for Shisen-Sho and Mahjong Solitaire.
