HaskellでNクイーンとナイトツアー

所用で行き当たりばったりなJavaScript書いてたら飽きたので前から手を付けようと思って手を付けてなかったHaskellにでも手つけてみっかという感じ。すごいH本は暇つぶしに何回も読んでるので「りろんはしってる」状態。

Nクイーン

のチェス盤に個のクイーンを互いに移動先が塞がれないように配置するパズル。クイーンは上下左右と斜め方向どこまでも動ける（飛車と角を足した動き）。例えばならこんな配置。

Q . . . .
. . . Q .
. Q . . .
. . . . Q
. . Q . .

とりあえず例とかは検索せず知ってる知識だけで書いていこー。

実践

type Pos = (Int,Int)

isPlace :: Pos -> Pos -> Bool
isPlace x y | fst x == fst y = False
            | snd x == snd y = False
            | abs(fst x - fst y) == abs(snd x - snd y) = False
            | otherwise = True

コマの位置はタプルで行と列を表し、それと置けるかどうか判定する関数。

placeble :: [Pos] -> [Pos]
placeble hist = [(x,length hist) | x <- [0..], all (isPlace (x,length hist)) hist]

前の行までの置いてあるコマの位置のリストを取って次の行に置ける位置を返す。Haskellらしく？無限リスト使ってみたりした。

search :: Int -> Int -> [[Pos]] -> [[Pos]]
search 1 m p = p
search n m p = search (n-1) m (concat (map (\q->(map (\r->q++[r]) (takeWhile (\s->fst s<m) (placeble q)))) p))

探す深さ（行）と深さの最大値、それから解候補を入れて解候補の次の位置に置ける位置を連結する関数。ポイントは次の位置における位置がない場合空リストが返ってくるのでバックトラッキングができてること……だと思う。リスト内包使えばもっときれいに書けたんでないか、と言うかナイトツアーの方ではそうしてる。

solve :: Int -> [[Pos]]
solve n = search n n [[(x,0)]|x<-[0..n-1]]

あとは1行目に置く位置のリスト作ってsearchに突っ込む関数作っておしまい。

Prelude> :l eightqueen.hs
[1 of 1] Compiling Main             ( eightqueen.hs, interpreted )
Ok, modules loaded: Main.
*Main> length $ solve 8
92

の時の回転合同とかも含めた時における解の数と一致、うまくいきました。あとで調べたら解候補は順列作ってやれば楽って出てきてあーってなったけどきちんとバックトラッキングしてるおかげかこっちのほうが速い気がするのでそれはそれでいいんじゃないかという事にしておいた。

ナイトツアー

別名「騎士の巡歴」。のチェス盤でナイトが一筆書できる手順を探すパズル。ナイト（N）はXの位置に動ける。

. X . X .
X . . . X
. . N . .
X . . . X
. X . X .

の解の例は以下の通り。

 1   8   3
 4  11   6
 7   2   9
10   5  12

同じく実装例自体は検索せず行ってみる。

import Data.List

type Pos = (Int,Int)

nextmove :: Pos -> [Pos]
nextmove p = [(fst p + x,snd p + y)| x<-[-2,-1,1,2], y<-[-2,-1,1,2], abs x /= abs y]

movable :: Int -> Int -> [Pos] -> [[Pos]]
movable x y hist = [hist++[q]| q<- (nextmove $ last hist), notElem q hist, crop q]
  where crop r = foldl (&&) True  [fst r>=0, snd r>=0, fst r<x, snd r<y]

あとで使うのでData.Listをimport。位置はまたタプルで行列の順。nextmoveは次動ける場所を返す。movableは盤面の縦横と今まで動いてきた位置を取って次動ける場所を連結して返す。はみ出しの処理とかはここ。

isEnd :: Int -> Int-> [Pos] -> Bool
isEnd x y p =  x*y == (length $ nub p)

search :: Int -> Int -> [[Pos]] -> [[Pos]]
search x y p = if null cand then [r | r<-p, isEnd x y r]
  else search x y cand
  where cand = concat[movable x y q | q<-p]

isEndで解候補が終了してるか判定。通ってきた位置の数が盤面の数と一致すればゴールにしてある。一応同じ位置はnubで排除してるけど無くていい。searchで次置ける場所を再帰的に探索。ここでも次動ける場所がなければ連結されないのでバックトラッキングになってる、はず。

solve :: Int -> Int -> [[Pos]]
solve x y = concat[search x y [[(a,b)]| a<-[0..x-1], b<-[0..y-1]]]

Prelude> :l knighttour.hs
[1 of 1] Compiling Main             ( knighttour.hs, interpreted )
Ok, modules loaded: Main.
*Main> length $ solve 3 4
16

一応全スタート地点から探索する関数も書いたけど、そもそも探索範囲が大きすぎてえらい遅い。でも一応正しい結果は出ているということで。

雑感

手続き型だと結構長くなっちゃうけどHaskellだとかなり簡潔に書けたなーという印象。Haskellの力と言うよりリスト内包とかの威力の気もするので他の言語（Python）でも割りと完結に書けそうな気はしますが。

あまりHaskell的？なファンクタ？とかモナド？とかに触れてなかったのでそういうのも触れていきたいですね。

その前に冬コミの原稿しなきゃ……。

スマホ買い替えの話

自分のスマホがどんくらい古いのかなーとAndroidのバージョンを見たら2.3.5だった。原稿が6.xなのでかなり開きがある。IEで言うと5くらいを使っていることになる。Webデザイナに殴りかかられても申し開きができないレベルである。3月くらいをめどに買い換えたい。

で、買い換えるにしても何にしようかなーと迷ってしまう。安く抑えたいが、あんまり性能が低いとWeb閲覧にまで支障をきたすのでそれなりに処理速度も欲しい所。ゲームのたぐいはフリーのパズルとかしかやらないのでそこまでの性能はいらないけど。予算を決め打ちしてそっから決めるのもありだろうか。ヨドバシでも行って触ってみよう。

あと通信料が高いのでMVNOとかゆーやつに乗り換えていきたいですね。月5000円くらい安くなるのは大きい。年にしたら6万円浮くので同人誌がもう1冊出せるぞ*1。ただMNPの手続きで何日か電話受け付けられないことがあるのが面倒ですね。

フォントワークスの更新作業をすっかり忘れていた。本当に面倒くさい。なんとかしてくれ。

*1:おそらく割増料金へと消える

Evernote

最近になってEvernoteを使い出した。正確には学生時代に勉強の補助ツールのためと使っていたのだが、紙の利便性に負けて、と言うよりそんなに真面目に勉強していなかったので結局放置したままであった。

今回Evernoteを使い出したのは創作のネタ集めが目的です。一応紙のネタ帳は作ってるんですけど、挿入したり順序入れ替えとか不可能に近いのでその不便さを解消できたらなと思いまして。あとはTwitterで呟いた雑多なネタとかもぼんぼん放り込めるのはブレインストーミング的で良いのかなーと。他にも疑問に思ったこととか後でネタに使えそうな資料とか万年筆にインク入れるタイミングとかまとめてメモしておけるのは便利そうです。いろいろ溜まってきたらノートリンクも試していきたいですね。

モチベーション

ブログからカビの臭いがすると思ったら2ヶ月ぶりくらいらしい。マジか。継続が苦手な人間なのでほっとくとすぐにやらなくなる。報酬がフィードバックが内的に完結してるものだったら続くんだけど、外的なフィードバックに頼ってるやつは継続が難しい。

絵を描くというのも最初書き始めた頃は内的に完結していた（自分で面白ければよし）のでそれなりに継続しつつだらだら描いていたんだけど、ネットをはじめて、特にSNSとやらが普及し始めてからは大分モチベーションを外的フィードバックに頼るようになってしまって継続が不安定になってしまう。モチベーションの安定のためにももーちょっと内的な面に立ち返りたいなあと思った。絵を描くのは楽しいんだよ。本当は。多分。ニコ動見てる方楽しいけど。

と考えて絵を書き始めた当時を鑑みても別そんなに継続してなかった。普通に今のほうが描く頻度高かった。何だったんだこの無駄な日記は。ただ内的で素朴な喜びってのは忘れられがちなので大切にしたいという気持ちには変わりがないと思います。

モリサワ～（ごまだれ～のリズムで）

モリサワパスポート買いました。

フォントワークスのフォントも使いこなさないうちに買ってしまった……。筑紫明朝はかっこいいけど、筆文字の雰囲気残りすぎてキザったらしくなることもよくあるのでもうちょいお硬い感じの明朝が欲しかった。マティスでええやん、となるかもしれないけどもうちょっと字形とか字面の広さとかそのへん違うの使いたいっていう色気もあったし、A1明朝を使ってみたいというミーハーな理由もある。というかそれ。早速新刊で使っていきたい。と思って新刊表紙で試しに組んでみたら微妙にキマらず、マティスでええやん、ってなりそう。マジか。

フォントの良し悪しはともかく、モリサワのフォントインストーラーが使いにくい。ソフト上で書体見本が確認できないのが辛い。Web上で確認してねってことなんだろうと思うけど肝心のWeb書体見本がレスポンス悪くて使いたくない。だったらせめて紙媒体での見本がほしい……。あとフォントインストールする度に再起動が必要なのも辛い。一気にフォントインストールしてねってことなんだろうけどあんまりインストールするとフォント選びにくくなるから様子を見つつインストールしたいのに。多分ライセンス周りの処理のせいな気がするんだけど、この辺の使い勝手はLETSのほうがいいよなーなんて思いました。でもこっちはこっちで契約更新が郵送書類なのが辛い、と届いた更新書類の封筒を見て思う。

原稿あんまり進んでねえ。

C89 2日目Q-45a

コミックマーケット89、スペース頂きました。1冊目かげぬい本、2冊目木曾大井本、3冊目は秘密、というか出せるかどうか怪しい。2冊目もカツカツである。3冊目ヘタすると60p行く気がする（プロットすらできていない）のでよく考えると本当に無理な気がしてきた。一応最後まで戦いたい。冬コミ3冊を諦めない（いざとなったら3冊目を12pくらいのあたたか本にするプランBがある）。

原稿もあるけどウェブサイト作りなおしたり、特設サイト作りたいしとやることめっちゃあるな……。

手術をした話

水曜日に手術しました。と言っても粉瘤（皮膚内に老廃物のたまり出来ちゃう腫瘍）の切除なんでめっちゃ軽いやつなんですけど。
「あーこれ赤くなっちゃってるから早めにやらないとね。今日キャンセル出たんだっけ？じゃあその時間にやりましょう」
「何分くらいかかります……？」
「30分」
スナック感覚かよ。

とは言ってもメス入れる手術は初めてだったので恐怖感はあった。局部麻酔なので意識あるし、局部麻酔の注射は痛い。痛覚無いけどメス入れられてんなーってのは皮膚引っ張られる感覚でなんとなくわかり、そのあたりが怖い。手術は滞り無く30分で終わった。腫瘍とはいえ自分から体の一部が切り離される経験をしたのは初めてなので不思議な感じだ。テセウスの船を思い出す。

一番きっついのは微小ながらも体にメスで切り込み入れたんでしばらく禁酒ってことですねーーー。5日間禁酒とか地獄かよ。酒飲んで無理矢理寝て生活リズムを無理矢理整えるという無理矢理な生活をしてたんですけど、酒飲まないと寝付きが良くなく生活が崩壊している。粉瘤より先にこの生活を直すべきだったか……。飲酒量に関しては禁酒前でもその前より減ってるのでなんとかなってるとは信じたい。

原稿はジリジリ進んでいる。2冊は確定で出せそうだけど3冊目60pはしんどいかもしれない。いざとなれば12pくらいで終わるネタはあるのでそれを出せば3冊出したことになるし大丈夫。大人は汚い。