エルミアの数学手帖

ここでは、離散数学、特にグラフ理論の観点で語りたいことを記事にします。趣味ではフリーゲ…

エルミアの数学手帖

ここでは、離散数学、特にグラフ理論の観点で語りたいことを記事にします。趣味ではフリーゲームと呼ばれているものを作っています。ゲーム関係の記事は別のサービスで掲載しています。

記事一覧

点の一筆書きを方程式にする

例題こたえ 上から大文字のZのようにたどる 方程式の解にするべきは?経路を求めたいということだから、点をつなぐ各線を経路に含むかどうかで表すとやりやすそうですね…

パズルの解の数を調べるには

本日の話題前の記事では、一筆書きには二種類あって、そのうち点の一筆書きは「NP完全」という性質で、解くことが難しいとされていることをご紹介したわ。 NP完全や、P対N…

勘違いしているかもしれない「一筆書き」

結論「一筆書き」は大まかに分けて2種類ある 片方は解き方が簡単で、もう一方は難しい一筆書きである 難しい一筆書きの一般的な解法は未解決問題 「Fill」のルール一筆…

こんにちは!エルミアです。

偉大な数学者のピタゴラスの言葉に「万物は数なり」というものがありますけれども、数学はいろんな疑問を解決できる、本当に万能な道具だと思います。 幼いころから数やパ…

点の一筆書きを方程式にする

点の一筆書きを方程式にする

例題こたえ

上から大文字のZのようにたどる

方程式の解にするべきは?経路を求めたいということだから、点をつなぐ各線を経路に含むかどうかで表すとやりやすそうですね。

図のようにaからiまでの変数を用意して、経路に含まれるなら1、含まれないなら0が入ることにするよ。
つまり、例えば変数aの定義域は a ∈ [0,1] (0≦a≦1)を満たす整数ということになるよ。

方程式の条件経路について

もっとみる
パズルの解の数を調べるには

パズルの解の数を調べるには

本日の話題前の記事では、一筆書きには二種類あって、そのうち点の一筆書きは「NP完全」という性質で、解くことが難しいとされていることをご紹介したわ。

NP完全や、P対NPについてのざっくりした解説は下記が参考になりそうよ。

このnoteでNP完全について言及してもいいけれど、かなり難しい(私も詳しく覚えていない)から、やめておくわ。それに、探せばいろんな方が解説記事を作っているしね。

今日は、

もっとみる
勘違いしているかもしれない「一筆書き」

勘違いしているかもしれない「一筆書き」

結論「一筆書き」は大まかに分けて2種類ある

片方は解き方が簡単で、もう一方は難しい一筆書きである

難しい一筆書きの一般的な解法は未解決問題

「Fill」のルール一筆書きパズル「Fill」のルールを言語化するとおよそ次のようなものよ。

一筆書きの開始位置は決まっている

筆は、上下左右のマスに移動できる

一度経過したマスには、二度踏むことができない

すべてのマスを踏めばOK



赤い

もっとみる

こんにちは!エルミアです。

偉大な数学者のピタゴラスの言葉に「万物は数なり」というものがありますけれども、数学はいろんな疑問を解決できる、本当に万能な道具だと思います。

幼いころから数やパズルに興味があり、離散数学、特にグラフ理論と呼ばれるものを専門に研究していた時期がありました。

一時期、私が夢中になっていたパズルゲームがありました。「Fill」という、いわば「一筆書きのような」パズルゲームです。

パズルゲームという

もっとみる