墓標

オタク思想とオタク地獄とラブコメと萌え4コマ漫画

ω-Queen問題的なものを考えてみた話

真面目なブログ記事です。

↑これ訂正なんですけど、私真面目なことしか書いた覚えがなかったです。

 

 

最近Queen問題というものを知りました。

 

 

これはチェスの盤に8個のクイーンを重ならないように置けるか?という問題です。

 

 

クイーンは任意の縦横斜め方向に好きなだけ動ける、というやつです。将棋で言うなら角と飛車がくっついたような感じ。

 

 

重ならないように、とはクイーンの行動出来る軌道上に他のクイーンが存在しない、という状態です。

 

 

説明が超下手です。wikipediaのエイト・クイーン問題に画像が載っているのでそっち見てください。ごめんなさい。

 

 

で、チェス盤の大きさは8×8なのですが、これを一般のn×nにしてみたn-Queen問題というのがあります。

 

 

 

で、一般にnが大きくなるほど解の数が増えて組み合わせ爆発が起こるらしく、解の数を知りたい、というのが主な問題で、これはどちらかというとプログラムとかアルゴリズムの問題だそうです。

 

 

しかし、私はプログラムが書けないしアルゴリズム深さ優先探索幅優先探索しか知りません。

 

 

でもまぁ無限組み合わせ論オタクなのでω-Queen問題を考えてみました。

 

 

要は盤面が{\mathbb{N}\times\mathbb{N}}の時を考えよう、という話です。

 

 

で、解の存在が(ZFC上で)示せた(と思う)のでちょっと紹介してみようと。

 

 

話の流れとしてはω-Queenの定義→証明に使う補題→存在性証明という感じです。

 

 

1.ω-Queen問題の解

 

そもそも何が解なんですか、という話で。

 

 

だいたいω個の重ならないクイーンなんていくらでも置けるわけです。各nに対して十分大きいa_nを取って{\{(n,a_{n})\mid n \lt \omega \}}とすれば良いので。

 

 

 

 

でもなんかこれだとスカスカです。というのもn-Queen問題の解は任意の行に対してただ1つのクイーンが置かれていて、さらに任意の列に対しても同様です。

 

 

まぁn個重ならないように置けばそりゃそうなんですけど、

 

 

なので、「任意の行に対して1つのクイーン、任意の列に対して1つのクイーンがあって、さらに斜めで重ならないような配置」を解だと思うことにします。

 

 

で、{X\subseteq \mathbb{N}\times\mathbb{N}}がω-Queen問題の解であるとは、

 

 

まず

{\forall n,|X\cap\{(n,i)\mid i \lt\omega\}|=1}

{\forall n,|X\cap\{(i,n)\mid i \lt\omega\}|=1}

を満たしていて、

 

 

かつ斜めで重ならない。

 

 

即ち任意の{n=(n_{1},n_{2}),m=(m_{1},m_{2})\text{ in }X}に対して

 

{n_{1} \lt m_{1}}ならば{(m_{1},n_{2} + (m_{1}-n_{1})) \not= m\land(m_{1},n_{2} - (m_{1}-n_{1})) \not= m}

 

 

となります。

 

 

あまりにもアレなので最初の条件を書きなおすと任意の{n\in \mathbb{N}}に対して唯1つの{m\in\mathbb{N}}が存在して{(n,m) \in X}なので{X}は関数です。

 

 

よってこれは{f:\mathbb{N}\to\mathbb{N}}{\forall n,m \in \mathbb{N}.n \lt m\to f(m)-f(n) \not= m-n \land f(m)-f(n) \not= -(m-n)}を満たす全単射そのものです。

 

 

このような全単射をω-Queen問題の解と定義することにします。

 

 

2.半順序の稠密部分集合とRasiowa-Sikorskiの補題

 

定義が終わったので次は存在を示したいんですけど、それに使う補題の紹介をします。

 

 

最初、具体的に定義しようとするもなんか色々と勘違いしていて「ぶっちゃけこんな関数ねーだろ!!!!でも強制法でくっつけられるんじゃね?」とやってみたらこの証明が出来ましたという感じなので、強制法を知ってる人はあーわかるわかる程度に見てください。

 

 

定理で使うRasiowa-Sikorskiの補題は次の主張を言います:

 

 

定理(Rasiowa-Sikorski)

任意のc.c.c.を持つ半順序{\mathbb{P}}と稠密集合の可算族{\mathfrak{D}}に対して{\mathbb{P}}-filter{F}{\forall D \in \mathfrak{D}.D\cap F \not= \emptyset}なるものが存在する。

 

 

これだけだと大変にアレなので 各用語の説明です。

 

 

{\mathbb{P}}を半順序とします。

 

  • {A\subseteq\mathbb{P}}反鎖(antichain)であるとは、任意の{x,y\in A}に対して{r\lt x,y}なる{r \in\mathbb{P}}が存在しないことをいう。

  • {\mathbb{P}}c.c.c.を持つとは、任意の反鎖が可算であることをいう。

  • {D \subseteq\mathbb{P}}稠密集合(dense subset)であるとは、任意の{p \in\mathbb{P}}に対し{r \in D}が存在して{r \leq p}なることをいう。

  • {F\subseteq\mathbb{P}}filterであるとは任意の{x,y \in F}に対して{r\leq x,y}なる{r \in F}が存在してかつ任意の{x\lt y\land x\in F}に対して{y \in F}なることをいう。

 

filterは上方向について閉じた有向集合って言った方がわかりやすいかもしれません。まぁ同じなので良いです。 

 

 

3.解の存在の証明

 

ここで示すのは次です:

 

{\forall n,m \in \mathbb{N}.n \lt m\to f(m)-f(n) \not= m-n \land f(m)-f(n) \not= -(m-n)}を満たす全単射{f:\mathbb{N}\to\mathbb{N}}が存在する。

 

証明:

{\mathbb{P}=\{f \mid f\text{は}\mathbb{N}\text{から}\mathbb{N}\text{への半関数},|dom(f)|\lt\omega,\\ \forall n,m \in dom(f) .(f(m) \not= f(n))\land (m\lt n \to f(m)-f(n) \not= m-n \land f(m)-f(n) \not= -(m-n))\}}

 

 

また{f,g \in \mathbb{P}}に対して{f\leq g \underset{def}{\Leftrightarrow}g\subseteq f}とすると{(\mathbb{P},\leq)}は半順序です。

 

 

{\mathbb{P}}は有限半関数全体の集合に含まれます。また、有限半関数全体の集合は可算なのでもちろんc.c.c.を持ちます。

 

 

また{D_{n} =\{f \in \mathbb{P}\mid n \in dom(f)\}},{E_{n} =\{f \in \mathbb{P}\mid n \in rng(f)\}}とするとこれは稠密集合になります。これは有限性を使うと示せます。

 

 

{\{D_{n}\mid n \lt \omega\}\cup\{E_{n} \mid n \lt \omega\}}は可算な稠密集合の族なのでRasiowa-Sikorskiの補題より全部と交わるfilter{F}が取れます。

 

 

ここで、{f,g\in F}に対し{r \in F}{r\leq f,g}なるものが存在します。

 

 

{r\leq f\cup g \in F}であることに気をつけると{\cup F}が関数であることが示せます。

 

 

関数でないとすると{f,g\in F}に対して{f(m) \not=g(m)}なる{m\in dom(f)\cap dom(g)}が存在します。即ち{f\cup g}は関数ではないことがわかります。

 

 

一方で{F}の元は全て関数なので矛盾です。

 

 

さらに{S = \cup F}{\mathbb{N}\to\mathbb{N}}なる関数になります。

 

 

というのも、任意の{n \in \mathbb{N}}に対して{g \in D_{n}\cap F }が存在するので{n \in dom(g) \subseteq dom(S)}なので{dom(S) = \mathbb{N}}です。

 

 

これは全射になります。

 

 

これもまた{g \in F \cap E_{n}}が存在することよりある{m \in dom(g)\subseteq dom(S)}が存在して{n = g(m) = S(m)}であることより言えます。

 

 

さらに{\mathbb{P}}の定義より単射です。

 

 

というのも、任意の{n,m}を取ると{g,f\in F}が存在して{n \in dom(f),m\in dom(g)}なので{h=f\cup g \in F\subseteq \mathbb{P}}です。

 

 

よって、{S(n) = h(n)\not = h(m) = S(m)}となり単射性が示せました。

 

 

{(m\lt n \to S(m)-S(n) \not= m-n \land S(m)-S(n) \not= -(m-n))}も全く同様にして示せます。

 

 

よって条件を満たす全単射{S}が見つかりました。□

 

 

 

結論として{\{(n,S(n))\mid n \lt \omega\}}の点にクイーンを配置するとどのクイーンも縦横斜め移動し放題、任意の行にも任意の列にもクイーンが1ついてハッピーハッピーです。

 

 

 

で、こういう定式化をすると解が見つかるよ、という話でやっぱり気になるのは非可算の場合なんですけど、その場合どう定義したら良いかわからないですね。

 

 

なんかcoloringとかの性質で特徴付けできそうな気はするんですけどね。

 

 

まぁωの場合がわかったと思うので取り敢えず良いです。どこか間違えてたら教えてください。