TIM Labs

fujiによるエントリー一覧

今回は、280合体ナンプレの問題としての正当性について書く。

ギネス世界記録™として認めてもらうには、当然問題の正当性が保証されないといけない。

その中でも面倒なのが、解の一意性(ユニーク性)である。

「ルールを満たす解が存在し、その数は1つだけである」

これは、ギネス世界記録™だけでなく、普通にナンプレ本、ナンプレ雑誌などに載る問題でも当然保証しなければいけない事で、問題を作ったプログラムの中に、そういう検証も含まれている。

しかし、パズルを作ったプログラムで、ユニーク性を確認しても、それは保証にはならないだろう。

公式記録となるためには、第三者がユニーク性を確認しなければいけない。

方法としては、まあ色々あり、検討された。

ナンプレの権威者の保証

そもそも、ナンプレの権威者って存在するのか?

権威者なら間違わないのか? 所詮人間であり、280合体ナンプレをノーミスで解くのは神でも無い限り無理だろう。

ということで却下。

第三者のプログラムで検証

人間が無理なら、プログラムで解くことになる。

第三者のプログラムで280合体を解けるプログラムが存在するかどうかよく分からない。

誰かに頼んでプログラムを作ってもらうのは可能かもしれないが、こういうのをホイホイ作るようなプログラマとは何らかの関係があったりして第三者として認められない。

他にも問題がある。

標準の9x9のナンプレ問題を解くプログラムでよく使われる、ルールと手筋を実装して調べるのでは、問題を自動生成するプログラムに使われている方法と本質的な差がなく、正当性の検証には無理がある。

280合体が完成するかどうかなかなか事前に予想ができなかった。

ギネス記録を達成したかどうか、詳しいことは、ニコニコ生放送のMATH POWER 2018を見てもらえばわかるのだが、全部で32時間30分もあるので大変かもしれない。

ということで、ここで手短に説明する。

こういう巨大な合体ナンプレは、問題の難易度よりも、どれだけのレベルの人が、どのくらい解き続けるかの影響が圧倒的に多いので、とても難しい。

しかし、結果は、ちゃんと完成して、ニコニコの動画はこんな感じになった。

nicoguiness8888.png

32:15:57

32時間より前に完成したのだが、1マスだけ残していて、ギネス記録達成の式典の直前に、最後の1マスを書き込んで完成しときのニコニコの画面が上である。

今年のMATH POWERでは、昨年247合体がフィナーレまでに終わらなくて、少々延長して何とか終わらせたので、ちゃんと時間内に終わらせるようにしようというのがあった。
そして、今回は、ギネス世界記録™を狙うというのもあった。
今までの合体ナンプレ(マルチ数独)の記録は、2015年の中国で樹立されたもので、去年の時点で既に世界記録だったのだが、今年はちゃんとギネス世界記録™を狙おうという魂胆があったのだ。
時間内に終わる、200合体を超えれば良い、という条件だけで問題を作るのは、問題作成者および参加者のモチベーションが上がらない。
それで、次のようにした。

Unix(Linux,...)では、lsは最もよく使用するコマンドではないだろうか。
ls は、ファイルとか、フォルダ(ディレクトリ)についての情報が分かる。

最近は、周辺機器をUSBで繋ぐのが一般的だ。
そして、何でも繋いでいるので、何がつながっているのか調べるのに困るくらいだ。
そうなると、lsコマンドと同じように、USBについてlsできないかと思うのが自然だろう。

実は、存在する。

lsusb(8)                                          Linux USB Utilities                                          lsusb(8)

NAME
       lsusb - list USB devices

SYNOPSIS
       lsusb [ options ]

DESCRIPTION
       lsusb is a utility for displaying information about USB buses in the system and the devices connected to them.

OPTIONS
       -v, --verbose
              Tells  lsusb  to be verbose and display detailed information about the devices shown.  This includes con‐
              figuration descriptors for the device's current speed.  Class descriptors will be shown, when  available,
              for USB device classes including hub, audio, HID, communications, and chipcard.

       -s [[bus]:][devnum]
              Show only devices in specified bus and/or devnum.  Both ID's are given in decimal and may be omitted.

以下省略
ということで、さっそく使ってみよう。
fuji$ lsusb
Bus 002 Device 001: ID 1d6b:0003 Linux Foundation 3.0 root hub
Bus 001 Device 003: ID 03f0:134a Hewlett-Packard Optical Mouse
Bus 001 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
fuji$ lsusb -t
/:  Bus 02.Port 1: Dev 1, Class=root_hub, Driver=xhci_hcd/8p, 5000M
/:  Bus 01.Port 1: Dev 1, Class=root_hub, Driver=xhci_hcd/16p, 480M
    |__ Port 7: Dev 3, If 0, Class=Human Interface Device, Driver=usbhid, 1.5M
fuji$ 
マウスは見えるが、キーボードが見えない。
実は、キーボードは、USBではなく、PS2でHHK(Happy Hacking Keyboard)をつないでいるからである。
ナンプレブームが今も続いていて、今年もMATH POWER 2018 に巨大合体ナンプレ世界一(?)を提供することになった。
去年は国政選挙に邪魔されて、六本木のニコファーレが使えず、会場が青山になったが、今年はニコファーレの予定である。
巨大合体ナンプレは現在鋭意制作中であり、世界一になるかどうかはまだ分からない。
さて今回は、合体ナンプレの話ではなく、サイズが9x9の単体のナンプレ問題の話をしよう。
NPSame1.png NPSame2.png
さて、この2つの問題、何が違うだろうか?
数学の祭典 MATH POWER が今年も開催される。
時期は、10月最初にある連休の最初の2日間に行われる。
今年の場合、10月6日昼から7日夜まで、31時間連続で夜を徹して数学を愛でるイベントだ。
場所は、六本木のニコファーレだ。

既に MATH POWER 2018 のサイトが公開されていて、参加申し込みも受け付けている。


MathPower2018SiteHeadImage.png

サイトは、まだまだ情報不足だが、どんなことが行われるかは、去年のサイト MATH POWER 2017 を見ると良いだろう。
去年は、イベントの最初から最後まで、多人数でやっと解ける程度の合体ナンプレを作って欲しいというので、247合体ナンプレを作った。
フィナーレまでには終わらなかったが、若干の延長で解き終えると思われたので、イベントをちょっと延長し、完成したのであった。
その問題がこれだ。

MP247Q.png
MATH POWER 2017 のサイトを見れば、ExcelとPDFで問題があるので、興味のある場合は解いてみよう。

さて、今年のMATH POWERでは、もうちょっとグレードアップした問題を提供することになっていて、現在鋭意製作中である。

去年は「世界最大級」というふうに級をつけていたが、今年はそんなに遠慮せずに、「世界最大」とすることにした。
そのために、去年よりもさらに大きくなってしまった。

去年のデザインは、美しいけれども単純な繰り返しなので、解き筋もモノトーンになってしまう。もっと色々な手筋が現れるように、もうちょっとデザインを頑張ってみた。
その他にも、色々なことにチャレンジしている。

しかし、そんなことをすると、どうやっても問題ができなくなることがある。

それに、いきなり巨大なものを作るのは危険だ。何時間、いや何日も連続でコンピュータを走らせても、何の結果も得られないことが多くなる。
そのため、小さい問題、といっても148合体とかなのだが、その程度の小ぶりな問題(?)で試作をしてみる。
この程度のサイズですんなり出来ない場合には、今年の問題サイズでは絶対に無理なのだ。

コンピュータ、ネットワークなど何でも同じなのだが、小さい場合にうまくいっても、そのまま拡大したら破綻することが多い。
サイズが2倍になったら、計算時間は10倍、100倍どころか永久に終わらなくなる。

ということで、色々な小さな問題を作っては問題生成の調子をみて、スケールアウトできそうだったら本番サイズで試すというのを繰り返している。
使っているアルゴリズムは、進化計算の一種である。
デタラメに問題をつくっては解き、どのくらい酷いかを判定し、ちょっと問題をいじっては酷さを判定している。
どんどんひどくない方向にヒントの数字をいじるのを繰り返しているだけである。
要するに、仕組みは簡単至極である。

問題の難易度はポイントで示される。
これを元に解くのにかかる時間が予想できる。
しかし、それだけでは十分ではない。
極端に易しい場所や、極端に難しい場所がないか、コンピュータに計算させている。
その結果を見て、ざっと判定し、良さそうな問題ができたら、実際に解いてみて、解き心地を調べる。

こういうのを繰り返して、イベントで解いてもらう問題を1問選定するのだ。
とても時間のかかる作業だ。

去年うまくいったので、さらにレベルアップして、来場者が驚くような、印象的なイベントにしようとしているのだ。
どんなサプライズがあるかは、イベントに参加して体感してみよう。

コピーの基礎的なことから書くので、話が無駄に長くなるのを最初に断っておく。 最後に、a[...] のような記述について書くので、そこだけ読みたい場合は最後から読もう。
まず、Pythonでの浅いコピーを示す。
>>> a = [[1,2,3],[4,5,6]]
>>> b = a
>>> a[0][0],a[1][1] = 100,200
>>> a
[[100, 2, 3], [4, 200, 6]]
>>> b
[[100, 2, 3], [4, 200, 6]]
aの要素だけを変更しようとしても、 b = a の代入により浅いコピーが行われているので、bの対応する要素も変わってしまう。

これを避けるためには、b=aの代わりに、copyのdeepcopy()を使う。
>>> import copy
>>> a = [[1,2,3],[4,5,6]]
>>> b = copy.deepcopy(a)
>>> a[0][0],a[1][1] = 100,200
>>> a
[[100, 2, 3], [4, 200, 6]]
>>> b
[[1, 2, 3], [4, 5, 6]]
さて、Pythonで色々計算しようとすると、Pythonではやってられなくて、NumPyを使うのが普通だ。 そもそも、Pythonには配列がなく、Deep Learningで必須の行列計算に困る。
では、numpyの配列で同じことをやってみよう。
>>> a = np.array([[1,2,3],[4,5,6]])
>>> b = np.array([[2,4,6],[3,6,9]])
>>> b = a
>>> a[0][0],a[1][1] = 100,200
>>> a
array([[100,   2,   3],
       [  4, 200,   6]])
>>> b
array([[100,   2,   3],
       [  4, 200,   6]])
単に代入ではコピーにならないようだ。
次に、numpyで用意されているcopy()を使ってみよう。


深いコピーができたようだが、念の為、サイズが歪なarrayでやってみよう。
>>> a = np.array([[1,2,3],[4,5]])
>>> b = np.array([[2,4,6],[3,6]])
>>> b = np.copy(a)
>>> a[0][0],a[1][1] = 100,200
>>> a
array([list([100, 2, 3]), list([4, 200])], dtype=object)
>>> b
array([list([100, 2, 3]), list([4, 200])], dtype=object)
歪んだarrayでやったら、元のaがリストの配列になってしまい、失敗したようだ。
numpyには、copy()はあるようだが、deepcopy()が存在しない。 それで、ここはやむなく、copy.deepcopy()でやるとどうなるか試してみよう。
>>> a = np.array([[1,2,3],[4,5,6]])
>>> b = np.array([[2,4,6],[3,6,9]])
>>> b = copy.deepcopy(a)
>>> a[0][0],a[1][1] = 100,200
>>> a
array([[100,   2,   3],
       [  4, 200,   6]])
>>> b
array([[1, 2, 3],
       [4, 5, 6]])
>>> a = np.array([[1,2,3],[4,5]])
>>> b = np.array([[2,4,6],[3,6]])
>>> b = copy.deepcopy(a)
>>> a[0][0],a[1][1] = 100,200
>>> a
array([list([100, 2, 3]), list([4, 200])], dtype=object)
>>> b
array([list([1, 2, 3]), list([4, 5])], dtype=object)
これで深いコピーができたわけだが、元の配列aは2次元配列ではなくて、リストの配列になっているので深いコピーができなかったようだ。
さて、配列の深いコピーをするのに、copy.deepcopy()を使えば問題ない。 しかし、普通のnumpyの配列なら、numpyのcopy()で深いコピーができる。


ごちゃごちゃ書いてきたが、最後に ...(3点)の使い方について書いておく。
>>> a = np.array([[1,2,3],[4,5,6]])
>>> a
array([[1, 2, 3],
       [4, 5, 6]])
>>> a[...]
array([[1, 2, 3],
       [4, 5, 6]])
配列aを表示するのに、単にaと書けば済むのだが、a[...]と書くこともできる。
ならば、a[...]に代入するとどうなるだろうか?
>>> a = np.array([[1,2,3],[4,5,6]])
>>> b = np.array([[2,4,6],[3,6,9]])
>>> b[...]=a
>>> a[0][0],a[1][1] = 100,200
>>> a
array([[100,   2,   3],
       [  4, 200,   6]])
>>> b
array([[1, 2, 3],
       [4, 5, 6]])
同じサイズの配列の場合、これで配列の深いコピーができている。 copy.deepcopy()やnumpy.copy()を使わなくてもできるのだが、事前に同じサイズの配列が存在していないといけない。

最後に、...が何者か示しておく。
>>> ...
Ellipsis
>>> type(...)

...はオブジェクトなので、引数として渡すなどもできる。
日本でも、大学の講義がビデオで公開されるようになったとはいうものの、通常行われている講義がそのまま公開されるのではなく、かなり短い特別な講義だけが公開される感じで、とても世界と比較てきるようなオープン性は見られない。

まあ、そんなことを言っても仕方がない、ここは日本だ。
それよりも、世界の大学でどんな講義が公開されているのか、探して勉強したほうが良い。

MITOPENCOURSEWAREでは、MITの実際の講義がそのままビデオでじゃんじゃん公開されている。
現在、2400コースあり、3億人が見たそうだ。
この数字は、MITだけでの数字である。

実際の正規のコース授業がそのまま公開されているようで、形態もいろいろあるようだが、VIDEOが一番気楽でよい。
VIDEOだけではなく、資料、問題、なども用意されていて、とても親切である。

日本の大学だと、あれこれ登録しないと見せてくれないケチな根性のところが多いが、ここは何の登録をしなくても、見せてくれる。
ちゃんと授業を受けて、試験も受けて、サーティフィケイトを貰いたいとかの場合は、登録などが必要みたいだ。

さて、最近、MITでパズルの授業を行っているというのを伝え聞いた。
それで、さっそく調べて見つけたのが、Programming for the Puzzled というコースだ。

レベルは学部生向けで、パズルでアルゴリズムを考えることで、プログラミング能力の基礎を鍛えようという意図らしい。
実際、この授業だけではなく、パズルやゲームを授業に使っている例は簡単に見つかる。

先生は、Srini Devadas教授で、インド人である。
あのIITマドラス校出身で、バークレーで学位を取得し、MITのFull Professorになっている。
ということで、ちょっと英語にインド訛りがあるが、そんなに気にしなくて良い感じだ。
そもそも、MITとかでコンピュータ関係を勉強しようとしたら、インド英語は必須科目だろう。
この講義には、トランスクリプション(発言内容を全部文字にしたもの)が用意されているので、聞き取りにくければ、テキストとして読むこともできる。

講義は全部で11本のビデオになっている。
毎回、色々なパズルを取り上げて、アルゴリズムについて細かく解説し、Pythonのプログラムを示しながら講義は進む。
Pythonのプログラムや、課題の解答プログラムも用意されていて、懇切丁寧だ。

講義の中に、SUDOKUがあるというので、この講義を知ったわけである。
SUDOKUの回は、再帰呼出しが話の中心であった。
最後の方で、再帰呼出しをしないで解くやりかた(普通にルールや手筋に基づく方法)の説明が簡単にされていた。
SUDOKUの問題を作ることには触れていなかった。
まあ、そこまでやると、さすがにMITでも、学部生向けの入門コースとしては無理があるのだろう。

第3回は、Puzzle 3: You Can Read Minds というタイトルで、トランプ手品が題材であった。
手品を1つ身につけたい場合には、ちょっと聴講するとよいだろう。

その他にも、アルゴリズムを考えないといけない、アルゴリズムによって大差がでてしまう例などが取り上げられている。

といっても、どれも基本的なものばかりだ。
パズルに関する高度な内容ではないので、プログラマなら出来て当然と思われるものばかりである。

去年の夏に、A1プリンタを入手し、幅60cm、長さ2mほどの大きさの印刷を良くしていた。
A1プリンタなのだが、ロングといって、ロール紙を使うことで、A1の標準よりも遥かに長い印刷ができるものだ。
このあたりは、以下の記事を参考にされたし。

通常はポスター程度の印刷なのだが、時々長い長い印刷物を印刷しなくてはならなくなることがあり、今年もそういう時期がやってきた。

それで、ちょっとプリンタの試運転ということで印刷してみた。

HPFalseDriverOutput.jpg

非常に大きなExcelの印刷を試したのだが、なぜか2mのうち、半分くらいが罫線が消えて文字だけになってしまった。
設定をいじっても、同様の現象になってしまう。

これは、大きくなって、ラスター化に失敗したということであろうか。
つまり、インクジェットプリンタに出力するのに、ピクセルにしないといけなくて、その変換途中でメモリ不足かなにかのトラブルで、罫線のラスター化を放棄したように思われる。

ということで、諦めてトボトボと帰っている途中で、原因を思い出した。
Windowsマシンから出力しているのだが、プリンタにインストールされていたドライバに問題があったのをプリンタメーカー(HP)のカスタマサポートから教えてもらったのを思い出した。
去年使っていたパソコンは動かなくなって、パソコンを新しくしたので、また同じ現象が起きてしまったのだ。

自動インストールされるものを使ってはいけないのだが、たぶんA1標準サイズまでなら、それでもとりあえずは動くのではないかと思う。
実際、普通のA1程度までは問題なかったのだ。
でも、勝手に入ってしまうというか、デフォルトのドライバがダメというのは要注意だ、というか酷い話だ。
メーカー提供の正式ドライバ以外が勝手にインストールされるような仕組は止めてもらいたい。

それで、自動でインストールされてしまうプリンタドライバを消去し、メーカー提供のドライバを入れてみた。
何も考えずに、標準、何でもやってくれる万能ドライバみたいなのがあったので、それを入れたら、A1サイズを指定しても、勝手にA4サイズまでしか印刷されない。
どうやら、小型プリンタ対応のドライバを入れたらしいので、また削除し、より機種を限定したドライバを入れてみた。

プリンタは、HPの DesignJet T520 というA1のロール紙も対応しているものだ。

ドライバを入れて、プリンタを確認すると使えるプリンタのリストが出てくるのだが、そのときの表示はこんなものが出てきた。

HPDesignJectT520-24inPCL-single.png
これは正しく動くものである。

PCL(Printer Control Language)は、HP(Hewlett-Packard)社が開発したページ記述言語であり、多くのプリンタで標準サポートされている。

さて、プリンタドライバが正しく動かなかったので、A1サイズ幅のゴミがいっぱいできてしまった。どうしよう。
PythonKivy.jpg
実践Pythonライブラリー

Kivyプログラミング

Pythonでつくるマルチタッチアプリ

監修  久保幹雄
著者  原口和也
発行日  2018年6月10日
サイズ   A5, 200頁  
ISBN  978-4-254-12896-3
価格   3200円(本体) 
発行所  朝倉書店


Pythonが流行っていて、人工知能関連のツール・ライブラリなどは選ぶのに困るくらいある。
しかし、GUIとなると、状況はまるで違って、とても少ない。

Pythonには標準のGUIとしてTkinterがついてくるのだが、ちょっと古いというか、かっこう悪いというか、いけていないのであった。

GUIをPythonのコードでガリガリ書いていくと、プログラムが肥大化するし、デザインがプログラムの中に入ってしまって、ごちゃごちゃしてしまう。
WEBページをHTMLだけで作るのではなく、デザイン部分はCSSで書くというのと同じように、分離できないものだろうか。

それに応えたのが、Kivyで、簡単な言語で記述することができる。
マルチプラットフォームであり、マルチタッチなどにも対応している。
詳細について書くと切りがないので、ネット上の情報を挙げておく。


このアーカイブについて

このページには、fujiが最近書いたブログ記事が含まれています。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。

月別 アーカイブ