『パズルの算法---手とコンピュータでのパズルの味わい方』の補足ページ
本ページは
の補足ページです．本書はもともとは日本評論社の『数学セミナー』で2021年4月号から2022年3月号まで連載した
『パズルの算法』という記事に大幅に加筆修正したものです．連載時に比べると倍くらいの内容になっています．
連載情報
- パズルの算法／パズルソルバ，『数学セミナー』
pp. 76-77, 2022年3月号.
- パズルの算法／クロスバーパズル，『数学セミナー』
pp. 80-81, 2022年2月号.
- パズルの算法／ルービック・キューブ，『数学セミナー』
pp. 80-81, 2022年1月号.
- パズルの算法／アンチスライドパズル，『数学セミナー』
pp. 88-89, 2021年12月号.
- パズルの算法／マッチングパズル，『数学セミナー』
pp. 78-79, 2021年11月号.
- パズルの算法／重ねるパズル，『数学セミナー』
pp. 86-87, 2021年10月号.
- パズルの算法／シルエットパズル，『数学セミナー』
pp. 82-83, 2021年9月号.
- パズルの算法／15パズル，『数学セミナー』
pp. 84-85, 2021年8月号.
- パズルの算法／ペグソリテア，『数学セミナー』
pp. 86-87, 2021年7月号.
- パズルの算法／ペンシルパズル，『数学セミナー』
pp. 78-79, 2021年6月号.
- パズルの算法／スライディングブロックパズル，『数学セミナー』
pp. 74-75, 2021年5月号.
- パズルの算法／ハノイの塔，『数学セミナー』
pp. 82-83, 2021年4月号.
目次
- 第１章 ハノイの塔
- ハノイの塔
- ハノイの塔の解き方
- ハノイの塔の状態遷移
- 関連パズル：パネックス
- ハノイの塔の単純な解き方
- 第２章 スライディングブロックパズル
- スライディングブロックパズル
- スライディングブロックパズルの仲間たち
- 第３章 ペンシルパズル
- ペンシルパズル
- ペンシルパズルのNP完全性
- なぜペンシルパズルはNP完全なのか
- ペンシルパズルから理論への逆襲
- 第４章 数のパズル
- 数のパズル
- 虫食い算・覆面算
- メイク10
- 第５章 15パズル
- 15パズル
- 15パズルの歴史について
- 15パズルの数理とトリック
- 15パズルのアルゴリズムと計算量
- 第６章 シルエットパズル
- シルエットパズル
- タングラム対清少納言智慧の板
- 最適解
- 理論的な難しさと最近のシルエットパズル進化形
- 第７章 重ねるパズル
- 重ねるパズル
- Kaboozle の困難性
- 第８章 マッチングパズル
- マッチングパズル
- 簡単な話なのか
- マッチングパズルの困難性
- 解けるマッチングパズル
- 第９章 アンチスライドパズル
- パズルの難しさとは？
- アンチスライドパズル
- アンチスライドパズルをコンピュータで解くには
- 第10章 ルービック・キューブ
- ルービック・キューブと仲間たち
- ルービック・キューブの解法：人間編
- ルービック・キューブの解法：コンピュータ編
- ルービック・キューブの流行の秘密？
- 第11章 クロスバーパズル
- グラフ同型性判定問題
- クロスバーパズル
- クロスバーパズルの先にあるもの：組木やからくり
- 第12章 手順の必要なパッキングパズル
- 手順の必要なパッキングパズル
- 3次元版
- 2次元版
- 計算量的な難しさ
- 蛇足：不可能物体
- 第13章 折り紙パズル
- 折るパズル
- 折るパズルの困難性
- 折るパズルをコンピュータで解く
- 第14章 裁ち合わせパズル
- 裁ち合わせパズル
- デュードニー氏の裁ち合わせパズル
- 一般的な場合の技法
- 第15章 ペグソリテア
- ペグソリテア
- ペグソリテアの思い出：その1
- ペグソリテアの思い出：その2
- 過去の精算
- 未来に向けて
- 第16章 パズルソルバ
- コンピュータで解く：さまざまなソルバ
- そもそも算法とは何だったのか
- 第17章 コンウェイのライフ・ゲームと計算不能性
- 計算不能なパズルとコンウェイのライフ・ゲーム
- コンウェイのライフ・ゲーム
- 付 録
- ポリオミノ・ポリキューブ・ポリアボロ
- チューリング機械
- 計算可能な関数と計算量クラス
補足情報
いくつかの補足情報を以下に示します．
- 3章で紹介したペンシルパズルの中の数独のところで，16x16の数独のヒント数55の問題が2問載っています．
これは2016年当時，上原研の学生であった奥村俊文氏がスパコンを用いて32問生成したうちの最初の問題と最後の問題です．
32問すべてが載っているPDFファイルを置いておきます．奥村氏の修士論文の付録です．
筆者の知る限り，ヒント数54以下の問題があるかどうかは未解決です．
- 本書は計算量的観点から見たパズルの面白さを取り上げて紹介している本です．
数学的な厳密性・理論的な証明・詳細な参考文献などはかなり省略しています．
このあたりの省略した部分をサーベイした論文を以下で出版していますので，詳細に興味がある方は参考にしてください．
特に細かい参考文献を調べて100編以上網羅的にサーベイしてあるので，資料的価値はあると思います．
章 |
ページ |
場所 |
間違い |
訂正 |
言い訳 |
発見者 |
発見日 |
2 |
14 |
脚注 |
岩瀬尚之 |
岩瀬尚行 |
ごめんなさい |
田守伸也 |
2024/09/21 |
5 |
31 |
5行目 |
crasy |
crazy |
typo |
谷口智子 |
2024/09/20 |
5 |
33 |
下から7行目 |
角 |
隅 |
typo |
谷口智子 |
2024/09/20 |
7 |
50 |
下から11行目 |
組合せて |
組み合わせて |
typo |
谷口智子 |
2024/09/20 |
7 |
51 |
1行目 |
旧知の中 |
旧知の仲 |
typo |
谷口智子 |
2024/09/20 |
8 |
54 |
下から6行目 |
前回 |
6章 |
typo |
谷口智子 |
2024/09/20 |
12 |
85 |
1行目 |
組合せながら |
組み合わせながら |
typo |
谷口智子 |
2024/09/20 |
12 |
92 |
5行目 |
作成 |
作製 |
typo |
谷口智子 |
2024/09/20 |
15 |
110 |
5行目 |
精算 |
清算 |
typo |
谷口智子 |
2024/09/20 |
15 |
112 |
1行目 |
Fourty One |
Forty One |
typo |
谷口智子 |
2024/09/20 |
おわりに |
137 |
4行目 |
岩瀬尚之 |
岩瀬尚行 |
ごめんなさい |
田守伸也 |
2024/09/21 |
おわりに |
137 |
下から6行目 |
勤めて |
務めて |
typo |
谷口智子 |
2024/09/20 |
人名索引 |
144 |
10行目 |
岩瀬尚之 |
岩瀬尚行 |
ごめんなさい |
田守伸也 |
2024/09/21 |
Last modified: Mon Jan 02 14:03 JST 2023
by Ryuhei Uehara (uehara@jaist.ac.jp)
| 
|