2 日前にパズルゲームを解くプログラムを書いたが、 今日は数独を解くプログラムを考えていた。 シンプルなアルゴリズムで簡単にできそうな気がしたが、 気のせいだった。GNOME 数独で出てきた「超難解」の 問題を入れてみたらぜんぜん解けない。 あれれ...
この前のパズルとは違って、 「試してみる」 処理は必要なさそうな気がするんだけど違うのかなあ。
今週は、天気予報の外れっぷりが半端無かったな。 雨だっていうから傘を持って行ってたんだけど、そのせいか全然降らなかった。 いや、一時的には降ったりしていたけど、 お昼ご飯の時と通勤の時にはほとんど降ってないみたいな。
マモーっていうかルパン三世の劇場版第一弾、 何回見てるかわかんないくらい放送されてるやつだが今日も金曜ロードショーで 放送されてた。
こういうあまり字幕とかが出ない映画を見るときは、 テレビチューナーの「ズーム」機能を使うと画面一杯に表示されていい感じ。 ただしオープニングやエンディングのクレジット画面ははみ出してしまう。 昔のアナログ放送の時も拡大されていたと思うんだけど、 どうなっていたんだっけなぁ。 クレジットのところだけ縮小表示だったかな。 ディジタル放送になって、横長サイズが標準になったから、 無理に拡大する必要がなくなって、テレビ局の中の人は楽になったんだろうなー。
バックトラッキングが必要だというコメントをいただいたが、 やっぱりそれはやらないで解いてみたいと思った。 それぞれのマスに入り得ない数字を決定していくことで、 マスを埋めていくことができるのではないか。 そう思っているんだが、「超難問」の問題は解けない...
0 3 0 0 0 4 2 0 5 0 0 1 7 0 0 0 4 0 8 0 0 5 0 0 0 0 6 5 4 9 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 9 7 4 3 0 0 0 0 2 0 0 7 0 6 0 0 0 5 4 0 0 4 0 8 1 0 0 0 9 0
線はないし空きスペースが 0 になっているので見にくいが、GNOME 数独で 出た問題はこれ。 これを解かせると、今のところ、以下のところまでしか解けない。
0 3 0 0 0 4 2 0 5 0 5 1 7 0 0 0 4 9 8 0 4 5 0 0 7 0 6 5 4 9 0 0 0 0 2 0 0 0 0 0 0 0 0 5 0 0 8 0 0 5 0 9 7 4 3 0 5 0 0 2 0 6 7 0 6 0 0 0 5 4 0 0 4 0 8 1 0 0 5 9 0
ここまで解くのにも、プログラムには、 ルールから導き出せる「定理」を含めないと解けなかった。 やっぱりバックトラックするしかないのか。
結局バックトラッキングみたいな方法を使うプログラムを作った。 ソースコードは C でたったの 4 行、わずか 250 バイトだが、 ちゃんとすべての解を列挙するプログラムである。 縦横と 3x3 の太枠の中に同じ数字が複数入らないというルールに従って 空いているマスを埋めていき、全部埋まったら結果を表示する。 不正な入力を拒否する実装は省いてあるので、 負の数または 10 以上の数を含むテキストなどを入力すると予期しない結果となる。 実行例:
$ cat d.c
#define a(p) w[m/27][m%9/3][z[m]=n]p+w[3][m/9][n]p+w[4][m%9][n]p
int z[81],w[5][9][10],m=81;b(m,n){while(m--&&z[m]);if(m<0)for(n=81;n--;)
printf("%d%c",z[n],n%9?32:10);for(n++;n--;a(--))a(++)||b(m,9);}
main(n){for(;m--;a(++))scanf("%d",&n);b(81,9);}
$ wc d.c
4 7 250 d.c
$ gcc -include stdio.h d.c
$ cat d1
0 3 0 0 0 4 2 0 5
0 0 1 7 0 0 0 4 0
8 0 0 5 0 0 0 0 6
5 4 9 0 0 0 0 2 0
0 0 0 0 0 0 0 0 0
0 8 0 0 0 0 9 7 4
3 0 0 0 0 2 0 0 7
0 6 0 0 0 5 4 0 0
4 0 8 1 0 0 0 9 0
$ ./a.out < d1
7 3 6 9 1 4 2 8 5
2 5 1 7 6 8 3 4 9
8 9 4 5 2 3 7 1 6
5 4 9 6 8 7 1 2 3
1 2 7 3 4 9 6 5 8
6 8 3 2 5 1 9 7 4
3 1 5 4 9 2 8 6 7
9 6 2 8 7 5 4 3 1
4 7 8 1 3 6 5 9 2
我ながら、演算子を引数に取るマクロがいい感じ。 これを思いついて、かなりすっきりしたソースコードになった。 あ、もちろん、これはソースコードを短くするためのテクニックね。
最初は z を 2 次元配列にしていて、そのときのほうが実行時間は短かった。 コードを短くするために 1 次元配列に変えたが、 それに伴って無駄に割り算が増えてしまったため、 最適化オフの場合は性能面で不利なようだ。
136 円/l。 燃費計算 18.1km/l。 燃費表示 19.6km/l。
なんだか眠たいげつようびであった。
来週からは鉄道のダイヤが平常に戻っていくらしい。 結局のところ、電力不足と騒いだ東京電力は、 意外とあった原発以外の発電能力と、 優しい客の節電努力によって、10% 以上の余力を残して この夏を乗り切ったということに。
帰り道で交通事故の現場検証を見かけた。 何事もなさそうな乗用車が 2 台、 と思ったら、1 台は運転席側ドアーがめこめこにへこんで傷だらけになっており、 おまけに歩道には傷だらけのモーターバイクが 1 台あって警官が何かを調べている。 これはもしかして、右折待ちのバイクに車が追突、 バイクが対向車のドアーに突っ込んだとかそういうのか? 想像だけど。
朝出遅れてチャリ通勤。
帰りは雨こそ降ってなかったが、それまでに微妙に降ったらしくて、 サドルは濡れてるし一部路面も濡れてたりして。 泥よけがないので、 タイヤが濡れたままで走ると水を振りまいてたいへんなことになるので、 なんとかしてタイヤの水気をなくす必要があった。 最後の 1km ほどでまた小雨が来たが、道路が濡れる前になんとか帰り着いた。
帰り道の途中で、武蔵境にあるラーメン屋に寄ってみた。 ラーメンはしょうゆ系と塩系、 しょうゆ系のラーメンがあまり好きじゃないことを最近自覚してきたので、 あえてつけ麺にしてみた。 麺はよし、つけ汁はうまいがちょっと塩分が多すぎるように感じられた。 濃ゆさは指定できるようなので、つぎは薄目にしてもらおう。
そのあとブックオフに寄ったりしたから雨に降られそうになったわけだが...
USB TO IDE が足下から発見されたので←、SSD の ファームウェアアップデートを実行することにした。 アップデートは、CD イメージを インテルのウェブサイトからダウンロードして CD-R/RW などに書き込み、 その CD から PC を起動すれば良い。
まあ一言で言えばそれだけなのだが、 問題はこの PC が fit-PC2 という手のひらサイズの PC で、CD ドライブでさえも 外付けで接続するしかないことだ。 内蔵用の CD-R/RW ドライブは余っているので、USB TO IDE を探していたわけだが、 見つかったので作業開始。
ところがこの CD-R/RW ドライブ、3 年ぶりに通電した TEAC CD-W512EB なんだけど、 取り出しボタンを押すと、トレイが出てきたあと、 即座にトレイが閉まってしまうという謎の挙動を示している。 トレイが閉まらないように手で引っ張っても、再度開いた後、 また即座に閉まってしまう。 壊れている? 少々不安になりながらも、無理矢理 CD-RW を押し込んで、 一応 Linux 上で読めることだけは確認してから、開始。 何事もなく無事完了。 バージョンは 4PC10302 から 4PC10362 に更新された。
謎の挙動はいつの間にか治っていて、あとはもうふつうに操作できた。 いったい何だったんだ... この世代の TEAC のドライブは いかにも頑丈そうなんだけどなぁ。
ノート PC に使っている Transcend の SSD も、 新しいファームウェアが公開されていることがわかった。 これは更新しない手はないよね、 というわけでさっそく更新プログラムをダウンロードして実行を試みる。
どう見ても FreeDOS (GNU GPL) が使われているのにソースが見あたらないあたり、 いかにも怪しい会社風なのだが、まあそれはおいておく。 何回やっても USB メモリーから起動することができず。 それで USB メモリーをさしておいて SSD から 起動し、GNU GRUB から chainload したらうまく起動できたのであった。 どうなってんだ、ThinkPad X31 の BIOS は。
しかししかし。 ぽちぽちと進めると "This program will destroy all data in SSD, do you want to continue (Y/N)? " などという恐ろしいメッセージが表れて あわててキャンセル。"in SSD" のあたりに違和感を覚える文だが、"will" だからね、 確定的なメッセージ。 そこで初めてマニュアルの PDF を確認、"Using this tool will erase all data stored on your drive." という非常に重要な注意書きがあった。 つまり間違いなくデータは消されるということだ。 めんどくせぇw
ついでに、マニュアルに HW 6832 and HW 6872 only とあるが、 調べてみたら自分のは HW 6872 だった。
まじめにこの更新を適用するとなると、 手っ取り早いのは、dd で全部別の HDD に吸い出して、 アップデートして、書き戻すというやり方。 バックアップ・リストアーを無理に ThinkPad 上でやる必要はなくて、 というのはネットワークが 100Mbps しか出なくてしょぼいから、 外付けの HDD をつないでやるしかないとおもうので、 それよりは逆に SSD を適当にデスクトップ PC につないで 作業してしまうほうが簡単だろう。
で、噂によるとプチフリが改善するらしいのだが、Linux で NILFS を使っていると、 事実上プチフリには遭遇できない。 まぁホームディレクトリーやルートパーティションが ReiserFS なので、 こっちはプチフリ遭遇できるかな。 カーネルの再インストールでもやればわかりやすいか。
大きな変化を好まない人には SeaMonkey がおすすめです。 最新の Gecko エンジンに昔ながらの Netscape 6 風 UI が 載っていて、web も mail も compose も OK で、 アドオンは基本的に Fx と同じものが使えるはずです... たぶん。
職場で QEMU のコンパイルをやっていたところ、true が見つからないなどという なぞめいたエラーで停止した。 調べてみると、なぜか /bin/true が消滅していた。 いつの間に。
再起動したら定期的な fsck が始まったがエラーなし。 何もしてないのに壊れてるとしたら ext3fs こわすぎる。 手が滑って消したとすれば /bin の日付からして 2 月頃、心当たりはないけれども。
そういえば ext3fs や reiserfs って更新時刻とかが秒単位 なのな。NILFS2 や tmpfs はもっと細かい単位で保持してくれてるんだけど。
まずはバックアップ。 バッキバキになってる ThinkPad X31 のドライブカバー、 ねじに引っかかっている両端を引っ張ると良いようだ。 割れているのでねじは外さなくてもいいかも 知れない。2.5 インチの ATA デバイスを USB で 接続するための変換器はあったので、それを使う。 しかし、専用の USB ケーブル (両端のコネクターが A 端子で、 しかも片方が二股に分かれているタイプ) が見つからず、探す羽目に。 結局なんと、サブ PC の背面 USB ポートに刺さったままだったという... (汗;
んで FreeBSD の dd でバックアップ。 最初 bs=16384 でやっていたが 5MB/s 程度と妙に遅い。 そこで bs=1048576 にしたところ 15MB/s 程度に改善。4MiB まで大きくすると かえって遅くなるようだ。
そしてアップデート。GNU GRUB から chainload と書いたが、 ことはそう簡単ではない。 ウルトラベースの DVD-ROM ドライブに FreeDOS の CD-R をセットした 上で、USB メモリーも取り付けて、CD から起動。 次に、最初のプロンプトで HDD から起動を選択。 それで GNU GRUB が立ち上がるので、以下のコマンドにより USB メモリーから起動。
root (hd1,0) chainloader +1 boot
アップデート自体は数分で終わる。 アップデート後の中身を見てみるとこのざまだ。
kojima# hd /dev/da0 00000000 ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff |................| *
そしてバックアップを書き戻す。dd bs=1048576 で、12MB/s 程度。
起動確認、とりあえずカーネルのアップデートがあったので適用。ReiserFS で 運用している / パーティション上に tar ball を展開するという、 プチフリがよく発生するシチュエーションだが、確かに改善しているような気がする。 あとプチフリがひどかったのは Windows Update だったかな。 そもそも、このノート PC の Windows XP は、 きのうまで 1 年以上も起動していなかったという有様で、 というのはなぜか無線 LAN がつながらなくて、めんどくさかったから。 今は PC カードタイプのものに変わっているので、 あらためてドライバーをインストールしてみたが、これもつながらなかった。
Powered by Tomsoft Diary System 1.7.4
Hideki EIRAKU