2007/12/11

数独ソルバー

数独ソルバーを書いてみました。

http://pa-n.sakura.ne.jp/200712/sudoku/


いきさつ

あーPS3買ったのにやりたいゲームないなー

体験版やるか

GT5 prologue体験版も飽きたなー
てか、prologueの体験版かー
GT5は来年12月って.....

レミング........

ぽちゃぽちゃあひるちゃん.............(買った \840)

.................

カズオ........


他の数独ソルバーのアルゴリズム

http://www.sudoku.name/sudoku-solver/jp

  • 解いている様子が見れるのでおもしろい

http://d.hatena.ne.jp/bellbind/20060712/1152692054

  • 改良版はコードが簡潔
  • 再帰をうまく使っている

http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html

  • コードが簡潔
  • 再帰をうまく使っている

http://echoo.yubitoma.or.jp/weblog/MASA-WA/eid/520627

  • コードは公開されていない?

ところで、これらの(コード公開の)ソルバーには次の共通点があります。

  • どのマスを仮定するかを決める際、候補の少なさを基準にしていない
  • 左上から右下にみていって、空白だったら確定マスに矛盾しないように仮定する

これをちょっと変更して、今回自分が書いたやつみたいに、「候補が少ないところを優先して仮定する」ようにすることで、

空白マスがたくさんある(=仮定がたくさん必要な)問題に対しては目に見えて高速に解けるようになります。

直感的には、次の2つのループ回数

(外側)9×9×9×...×9×8×5×2(内側)

(外側)2×5×8×9×...×9×9×9(内側)

との違いといいますか。(ループ回数はイメージです)

ループの内側にいくにしたがって、仮定したことによる候補の絞りこみで結構すぐに矛盾があらわになりがちだと思うんですね。

なので、最外ループの反復回数が少ないと、わりとすぐに探索木が半分になったりするわけです。

2007/12/10

second life, home

について。

(PS3のhomeはいつ始まるかわからんですが...)


誰か(友達とか)に会うためには、「今」、「自分がいる場所」にその人が居る必要があると思うんですが、

自分が居る場所付近に、過去にいた誰かの痕跡を表示したりする仕組みがあれば、条件が緩くなって誰かに会える可能性が上がって、コミュニケーションが取りやすくなるんじゃないかと思いました。

ニコニコ動画とか、ふつうの掲示板とか、ふつうのメールみたいに。

「今」が重要なんだ、という考えかもしれませんが、今じゃなくていいぜというオプションはあっても困らないような気がします。

2007/12/06

if文と三項演算子

カツマさんのところで、javascriptのif文と三項演算子の速度比較をされたようです。

三項演算子の方が速い場合が多い理由(の予想)

if文は「文」なのに対し、三項演算子は「式」なので、解釈系(インタプリタ)や翻訳系(コンパイラ)が分岐除去の最適化をしやすいんじゃないかと思います。

なぜ式だと分岐除去がしやすいかというと、任意の式が2つ与えられたときに、「それらが同程度の計算で実行できるかどうか」の判断が文2つのときよりも簡単に求まるからかな、と思います。

if文の場合も三項演算子の場合も、then節とelse節とがどちらも十分単純で、異なる部分に分岐の有無の差がなかったりする場合に、分岐を除去して2つを投機的に計算して、後から条件の結果より2つの結果を選択するという最適化ができそうですが、

式の場合、true-exprとfalse-exprが関数呼び出しを含まなければ分岐除去できそうなのに対し、文の場合はthen節とelse節が全く同じ構造を持つ文でないと分岐除去できなさそう、という。

処理系の最適化モジュールを書くのに必要な手間が、式の場合の方が少ないからなんじゃないか、という予想です。

個別の処理系に関しては、処理系の実装次第なのでしょう。

ちなみに、gcc 3.4, -O2 の場合は



int main(int args, char** argv)
{
return (int)(args==5 ? "1022" : "1050");
}


でも



int main(int args, char** argv)
{
if(args==5) return (int)"1022"; else return (int)"1050";
}


でも同様に分岐除去されていないアセンブリが出てきました。



ちなみに!Cell/B.E. の SPU は分岐のペナルティが18cyclesくらいあって結構でかいので、できるだけ三項演算子や spu_sel を使って処理系が分岐を除去しやすくする、または明示的に分岐除去する、という方法がオススメされているようであるッッ......!!!