数独の高速化 - Cybozu Inside Out | サイボウズエンジニアのブログ
「サイボウズ・アドベントカレンダー」の4日目です（これまでの記事一覧）。どうやら三日坊主は免れたようです（笑）。 (0) はじめに こんにちは。サイボウズ・ラボの川合秀実です。私は主にサイボウズ製品の高速化のお手伝いをしています。しかし先日、製品とは関係ないものを高速化したので、今日はそれを発表します。 サイボウズには社内勉強会がいくつかあって、その中にはC++の勉強会もあります。私はサイボウズの勉強会に参加するのが好きなので、このC++の勉強会に参加してみました。この勉強会では、「数独」というパズルを解くプログラムをC++で書いてみよう、というのが最初のテーマでした。参加者各自がプログラムを書き、翌週にお互いにレビューしあうということが行われました。 ここで私はやらかしてしまいました。ええ、そうです、高速化してしまったのです！ 言うまでもないですが、誰もこんなことは望んでいません。そもそ
新雑誌「n月刊ラムダノート」の『「コルーチン」とは何だったのか？』の草稿を公開します - まめめも
『Ruby でつくる Ruby』などでお世話になっているラムダノートが、新しい雑誌「n月刊ラムダノート」を創刊しました。 www.lambdanote.com コンピュータ関係の技術情報の記事だけが載るそうです。創刊号は、『TCPの再送制御機構』、『「コルーチン」とは何だったのか？』、『MLOpsの歩き方』、の 3 本です。 『TCP の再送制御機構』は、パケットを送ってから返事が来るまでの RTT (Round-Trip Time) を計測する方法や、RTT を使った再送のアルゴリズムや、RTT を使わない再送のアルゴリズムなど、TCP の再送に関する仕様・実装の歴史から最新提案までを、日本語話者の中では間違いなく世界一詳しい第一人者である西田佳史さん（@nsd）が広く深く紹介しています。 『「コルーチン」とは何だったのか？』は、ぼくが書きました。伝統的なコルーチンの説明から、JavaS
SAT ソルバで数独を解く方法 - まめめも
数独は非常に SAT に変換しやすい問題です。全部参考文献 *1 に載っている内容ですが、なるべくわかりやすく説明してみます。ちょっと長いです。 SAT とは まず SAT をごく簡単に説明します。すでに SAT を知っている人はここは読み飛ばしてください。 命題論理式の形の一つに乗法標準形のというのがあります。変数か変数の否定 (リテラルと言います) を or だけでつないだ式 (節と言います) を and だけでつないだ論理式のことを言います。つまり以下みたいな形です。 ( a1 or !a2 or ... or an) and ( b1 or !b2 or ... or !bn) and ... and (!z1 or z2 or ... or !zn)SAT は「a1 や zn などの変数にうまく true か false を代入して、上の式全体を true にできるか」という問題
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
