隣接が禁止された数字の組の数が最大の数独について
前置き
数独（ナンプレ）バリエーションの一つに、隣り合った数の組に着目するというものがあります。
今回は、禁止できる数字の組の最大数についての考察を進めていきます。
問題
にしなんとかさんのサイトより
9つの数字から2つの数字を選ぶ方法は36通りある。このうち何通りかを指定して、その2数ごとに以下の追加ルールを指定する: 「その2数が縦横に隣り合ったマスに入ってはならない。」
この問題は、既に解決しており、
19組禁止するためにはある数字について、5つの数字との隣接を禁止する必要がある
他の3つの数字としか隣接しないような配置はできないことが証明された
残りの18組での数独盤面は具体的に構成済
と、上界下界が共に示されています。
今回は、残った問題である、
"18通り"の選び方は、「どの数字もちょうど4種類の数字と縦横に隣り合う」という制約を加えても、上の例と本質的に異なる（数字の入れ替えなどで一致しない）選び方がいくつも存在する（いくつ存在するのだろう？グラフ理論の分野の問題だ。）が、そのような"18通り"でも数独の盤面を構成できるかは未解決である。
について、全探索により本質的に異なる18通りの選び方で構成される全解を構築しました。
手法
どの数字もちょうど4種類の数字と隣接する9つの数字の本質的に異なる組み合わせの数について、
グラフ理論では単純かつ連結な9頂点の4-正則グラフの個数として知られており、
Number of connected regular simple graphs of degree 4 (or quartic graphs) with n nodes.
Regular Graphs
16種類あるようです。
この16種類について数独の盤面が存在するかをソルバで調べていきます。
以下、隣接している数字（禁止されている数字ではなく）をグラフとして表していきます。
結果
16種類のうち3種類で数独の盤面を構成可能でした。
長くなるので詳細は別ページに記載しました。
table: solutions
グラフ番号 解の数 隣接禁グラフ
Graph#14
https://gyazo.com/79936bd516ddb0eb20d7593769196d20
Graph#15
https://gyazo.com/7616456fa5d54a4eb8af15d1d4d90fe2
Graph#16
にしなんとかさんの記事にあったケース
https://gyazo.com/bd86679042051ca6ba740247afdb342f
考察
解が存在する条件
一旦グラフの形が明らかになったので、解が存在する条件について色々考えてみることができます。
グラフの対称性が高い方が解が成立しやすい？
各方向に長さ4のループが必要そう？
https://gyazo.com/01a1b5d78a8a6253a427b2045769d498
数独の盤面として成立させるために、
隣接する数字を4つ辿り、同じ数字に戻る必要があります。
グラフによってはこの方針で解が存在しないことを証明できるかもしれません。
解のパターン
詳細リンクには求まった解の一覧を載せました。
それらの解の対称性や同じ数字の繰り返し、配置のパターンなどを検証できそうです。
どちらも今後の研究が進むと明らかになっていきそうですね。
課題と展望
最後に、今後の課題や展望、思いつきについてまとめて締めくくります。
解が存在する条件
解が存在しないグラフについてのより簡易な証明や条件の一般化
どの数字からも4つ以上隣接しているという制約で、数独としての解が存在しない最大の隣接数はいくつか
18通り以外のグラフについても、グラフを見ただけで解があるかどうかを判定することはできるか
解のパターン
解の対称性や同じ数字の繰り返し、配置のパターンなどの法則性
人間が解く時の手筋などはどのようなものが使えるか
最少表出数等
実際に問題を作ってみる
拡張
有向グラフへの拡張、すなわち左→右、上→下と右←左、下←上を区別した時に条件はどう変化するか
４方向を区別した時はどうなるか
ブロック制約を無くし、ラテン方陣にしたらどうなるか
→ 解が存在しなかった13パターンすべてで解が存在。
Graph#6 のみ22万解、Graph#13が4万解、それ以外は1000〜3000解
Graph#6 の対称性の高さが所以?
ブロック制約をなくす、もしくは変形盤面を認めると、2つの数字とのみ隣接(辺の数が9)する解が存在する
https://gyazo.com/164953e964c449aa7721b4c41f75978f
▲例えばこのような分け方が存在する。
興味のあるテーマがありましたら、ぜひぜひ考えてみてください
指摘等はTwitter@wand_125 まで