{
"cells": [
{
"cell_type": "markdown",
"id": "4ab86ac1",
"metadata": {},
"source": [
"# 『なには八ツ橋智恵の渡り』で橋渡り('24.06.05)\n",
"\n",
"和算書籍の眞元算法(1845年)に『浪華二十八橋智慧渡』という問題が載っている。\n",
"それは、1736年にオイラーが題材とした「ケーニヒスベルクの橋の問題」問題の亜種だ。\n",
"つまり、ケーニヒスベルクにある7つの橋を「ひとつの橋を2度通ることなく、全ての橋を渡って、元の場所に帰ってくることができるか？」という問題の変形バージョンである。\n",
"オイラーが橋渡り問題を扱った百年後に出された『浪華二十八橋智慧渡』は、オリジナルの問題とは異なる趣向が含まれている。\n",
"あるいは、オリジナルの問題の本質を外したことで、別のパズル問題となっているようだ。\n",
"\n",
"%<img style=\"float:center;transform: rotate(0deg); height:10cm\" src=\"./images/day_240604_yatsuhashi_original.png\" />\n",
"\n",
"```{figure} ./images/day_240604_yatsuhashi_original.png\n",
"---\n",
"height: 10cm\n",
"---\n",
"オイラーの「ケーニヒスベルクの橋の問題」論文\n",
"```\n",
"\n",
"今回は、『浪華二十八橋智慧渡』を解くための準備をしてみようと思う。\n",
"その題材として使うのは、『浪華二十八橋智慧渡』の簡易版たる[『なには八ツ橋智恵の渡り』](https://www.osakamushis.jp/news/2009/tenjigae/0908222.html)である。\n",
"これは、『浪華二十八橋智慧渡』が扱ったあたりを舞台に、橋の数を8つに減らした単純バージョンだ。\n",
"\n",
"%<img style=\"float:center;transform: rotate(0deg); height:12cm\" src=\"./images/day_240604_yatsuhashi.jpg\" />\n",
"\n",
"```{figure} ./images/day_240604_yatsuhashi.jpg\n",
"---\n",
"height: 12cm\n",
"---\n",
"『なには八ツ橋智恵の渡り』\n",
"```"
]
},
{
"cell_type": "markdown",
"id": "89550c75",
"metadata": {},
"source": [
"## 『なには八ツ橋智恵の渡り』をグラフにしてみる\n",
"\n",
"まずは、『なには八ツ橋智恵の渡り』をグラフ構造にしてみよう。\n",
"後で実際の地名を使うことにして、とりあえずは仮地名でデータを作ってみる。"
]
},
{
"cell_type": "code",
"execution_count": 30,
"id": "6db0aff5",
"metadata": {
"tags": [
"hide-output",
"hide-input"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"島の数 5\n",
"橋の数 9\n"
]
}
],
"source": [
"import numpy as np\n",
"import networkx as nx\n",
"\n",
"# c.f. https://medium.com/@victorialandaberry/solving-the-konigsberg-bridge-problem-with-python-914f9f51bb8e\n",
"g = nx.MultiGraph() #create an empto Multigraph named G\n",
"#add nodes one by one \n",
"g.add_node(\"難波A\")\n",
"g.add_node(\"難波B\")\n",
"g.add_node(\"難波C\")\n",
"g.add_node(\"難波D\")\n",
"g.add_node(\"難波E\")\n",
"#add edges\n",
"g.add_edge(\"難波A\", \"難波B\")\n",
"g.add_edge(\"難波B\", \"難波C\")\n",
"g.add_edge(\"難波C\", \"難波E\")\n",
"g.add_edge(\"難波A\", \"難波D\")\n",
"g.add_edge(\"難波A\", \"難波D\")\n",
"g.add_edge(\"難波B\", \"難波D\")\n",
"g.add_edge(\"難波B\", \"難波D\")\n",
"g.add_edge(\"難波D\", \"難波E\")\n",
"g.add_edge(\"難波C\", \"難波D\")\n",
"\n",
"print(\"島の数\", g.number_of_nodes())\n",
"print(\"橋の数\", g.number_of_edges())"
]
},
{
"cell_type": "markdown",
"id": "0368127d",
"metadata": {},
"source": [
"作成した『なには八ツ橋智恵の渡り』のグラフ構造を描画してみよう。"
]
},
{
"cell_type": "code",
"execution_count": 26,
"id": "6d764bbc",
"metadata": {
"tags": [
"hide-input"
]
},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"207pt\" height=\"332pt\" viewBox=\"0.00 0.00 206.84 332.00\">\n",
"<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 328)\">\n",
"<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-328 202.84,-328 202.84,4 -4,4\"/>\n",
"<!-- 難波A -->\n",
"<g id=\"node1\" class=\"node\">\n",
"<title>難波A</title>\n",
"<ellipse fill=\"none\" stroke=\"black\" cx=\"163.1\" cy=\"-306\" rx=\"36\" ry=\"18\"/>\n",
"<text text-anchor=\"middle\" x=\"163.1\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">難波A</text>\n",
"</g>\n",
"<!-- 難波B -->\n",
"<g id=\"node2\" class=\"node\">\n",
"<title>難波B</title>\n",
"<ellipse fill=\"none\" stroke=\"black\" cx=\"91.1\" cy=\"-234\" rx=\"35.19\" ry=\"18\"/>\n",
"<text text-anchor=\"middle\" x=\"91.1\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">難波B</text>\n",
"</g>\n",
"<!-- 難波A--難波B -->\n",
"<g id=\"edge1\" class=\"edge\">\n",
"<title>難波A--難波B</title>\n",
"<path fill=\"none\" stroke=\"black\" d=\"M147.12,-289.46C135.19,-277.86 118.95,-262.08 107.03,-250.49\"/>\n",
"</g>\n",
"<!-- 難波D -->\n",
"<g id=\"node3\" class=\"node\">\n",
"<title>難波D</title>\n",
"<ellipse fill=\"none\" stroke=\"black\" cx=\"107.1\" cy=\"-90\" rx=\"36\" ry=\"18\"/>\n",
"<text text-anchor=\"middle\" x=\"107.1\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">難波D</text>\n",
"</g>\n",
"<!-- 難波A--難波D -->\n",
"<g id=\"edge2\" class=\"edge\">\n",
"<title>難波A--難波D</title>\n",
"<path fill=\"none\" stroke=\"black\" d=\"M153.67,-288.51C142.85,-259.31 127.25,-196.65 113.1,-144 109.87,-131.99 106.05,-118.51 104.25,-108.15\"/>\n",
"</g>\n",
"<!-- 難波A--難波D -->\n",
"<g id=\"edge3\" class=\"edge\">\n",
"<title>難波A--難波D</title>\n",
"<path fill=\"none\" stroke=\"black\" d=\"M164.31,-287.57C160.52,-257.99 145.1,-196.09 131.1,-144 127.77,-131.63 123.82,-117.68 119.51,-107.21\"/>\n",
"</g>\n",
"<!-- 難波B--難波D -->\n",
"<g id=\"edge5\" class=\"edge\">\n",
"<title>難波B--難波D</title>\n",
"<path fill=\"none\" stroke=\"black\" d=\"M88.44,-215.87C88.63,-188.43 94.67,-134.95 100.67,-107.75\"/>\n",
"</g>\n",
"<!-- 難波B--難波D -->\n",
"<g id=\"edge6\" class=\"edge\">\n",
"<title>難波B--難波D</title>\n",
"<path fill=\"none\" stroke=\"black\" d=\"M97.55,-216.15C103.52,-188.97 109.54,-135.72 109.75,-108.27\"/>\n",
"</g>\n",
"<!-- 難波C -->\n",
"<g id=\"node4\" class=\"node\">\n",
"<title>難波C</title>\n",
"<ellipse fill=\"none\" stroke=\"black\" cx=\"35.1\" cy=\"-162\" rx=\"35.19\" ry=\"18\"/>\n",
"<text text-anchor=\"middle\" x=\"35.1\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">難波C</text>\n",
"</g>\n",
"<!-- 難波B--難波C -->\n",
"<g id=\"edge4\" class=\"edge\">\n",
"<title>難波B--難波C</title>\n",
"<path fill=\"none\" stroke=\"black\" d=\"M78.39,-217.12C69.22,-205.66 56.91,-190.26 47.75,-178.82\"/>\n",
"</g>\n",
"<!-- 難波E -->\n",
"<g id=\"node5\" class=\"node\">\n",
"<title>難波E</title>\n",
"<ellipse fill=\"none\" stroke=\"black\" cx=\"71.1\" cy=\"-18\" rx=\"34.39\" ry=\"18\"/>\n",
"<text text-anchor=\"middle\" x=\"71.1\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">難波E</text>\n",
"</g>\n",
"<!-- 難波D--難波E -->\n",
"<g id=\"edge9\" class=\"edge\">\n",
"<title>難波D--難波E</title>\n",
"<path fill=\"none\" stroke=\"black\" d=\"M98.57,-72.41C92.83,-61.25 85.29,-46.6 79.57,-35.47\"/>\n",
"</g>\n",
"<!-- 難波C--難波D -->\n",
"<g id=\"edge7\" class=\"edge\">\n",
"<title>難波C--難波D</title>\n",
"<path fill=\"none\" stroke=\"black\" d=\"M50.72,-145.81C62.63,-134.23 78.98,-118.34 91.01,-106.64\"/>\n",
"</g>\n",
"<!-- 難波C--難波E -->\n",
"<g id=\"edge8\" class=\"edge\">\n",
"<title>難波C--難波E</title>\n",
"<path fill=\"none\" stroke=\"black\" d=\"M39.44,-143.87C46.36,-116.58 59.81,-63.52 66.74,-36.19\"/>\n",
"</g>\n",
"</g>\n",
"</svg>"
],
"text/plain": [
"<IPython.core.display.SVG object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"from IPython.core.display import SVG, display\n",
"\n",
"def draw(graph):\n",
" svg = nx.nx_agraph.to_agraph(graph).draw(prog='dot',format='svg')\n",
" display(SVG(svg))\n",
"\n",
"draw(g)"
]
},
{
"cell_type": "markdown",
"id": "701e533a",
"metadata": {},
"source": [
"そして、オイラーが1736年に考えた「一筆書きで元の場所に戻れるか」を判定法を、『なには八ツ橋智恵の渡り』に適用させてみると、答えはこうなる。\n",
"つまり、オリジナルの「ケーニヒスベルクの橋の問題」と同じ結果が得られる。"
]
},
{
"cell_type": "code",
"execution_count": 24,
"id": "169d72d3",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"一筆書き経路で元の場所に戻ることはできません。\n"
]
}
],
"source": [
"def eulerpath(graph):\n",
" odd=0\n",
" a=list(graph.degree(graph.nodes()))\n",
" for i in a:\n",
" if (i[1] % 2) != 0:\n",
" odd+=1\n",
" if odd>0:\n",
" print(\"一筆書き経路で元の場所に戻ることはできません。\")\n",
" else:\n",
" print(\"一筆書き経路で元の場所に戻ることができます。\")\n",
"\n",
"eulerpath(g)"
]
},
{
"cell_type": "markdown",
"id": "5c0ffdc7",
"metadata": {},
"source": [
"## ハシを渡りさえしばければワキの町を通り抜けても良い？の謎\n",
"\n",
"『なには八ツ橋智恵の渡り』には妙な解説文がある。\n",
"それは「ハシを渡りさえしばければワキの町を通り抜けても良い」「工夫をすれば渡ることも簡単だ」という一節だ。\n",
"この謎について、また眞元算法(1845年)で出題された『浪華二十八橋智慧渡』についても、関連する文章を参考にして、史実や真実の答えに辿り着いてみたいと思う。\n",
"\n",
"%<img style=\"float:center;transform: rotate(0deg); height:10cm\" src=\"./images/day_240604_yatsuhashi_IMG_3321B40D720A-1.jpeg\" />\n",
"\n",
"```{figure} ./images/day_240604_yatsuhashi_IMG_3321B40D720A-1.jpeg\n",
"---\n",
"height: 10cm\n",
"---\n",
"『なには八ツ橋智恵の渡り』\n",
"```\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "67bcf451",
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"celltoolbar": "Tags",
"kernelspec": {
"display_name": "jupyter-book-py311",
"language": "python",
"name": "jupyter-book-py311"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.11.9"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 5
}