あらゆる数独パズルを解く
Peter Norvig / 青木靖 訳 このエッセイでは、 あらゆる数独パズルを解くという問題に取り組む。制約伝播と探索という2つのアイデアを使うと、ごく簡単に解けるということがわかる(主要なアイデアはコードにして1ページたらずで、補足的なコードが2ページある)。 数独の記法と予備概念 最初に記法をいくつか決めておこう。数独パズルは81個のマス(square)からなる盤面を使う。数独ファンの多くはカラムを1-9で、行をA-Iでラベル付けしており、カラム、行、ボックスのような9個のマスの集まりをユニット(unit)と呼び、ユニットを共有するマスをピア(peer)と呼んでいる。パズルではマスのいくつかが空いており、他は数字が入っている。パズルの目的はこうだ。 それぞれのユニットのマスが1から9の数字の順列によって埋められるようにする。 つまり、1つのユニットに同じ数字が2度現れてはならず、そ
SQLで数独を解く - y-kawazの日記
Before After Oracle RDBMS 11gR2 - Solving a Sudoku using Recursive Subquery Factoringという海外の記事を見つけて、これはスゲーｗｗと思ったんだ。 で、Oracleなんかよりも自分が慣れ親しんだ PostgreSQL でも、8.4で再帰SQLが出来るようになったからやってみたい！ってことでやってみた。 Oracleスペシャルな関数とかが無かったりしたのでちょこちょこと直したけど基本は同じです*1。 こうして上手く動くと感動するわー。 WITH RECURSIVE x(s, ind) AS ( SELECT sud, position(' ' in sud) AS ind FROM (SELECT '53 7 6 195 98 6 8 6 34 8 3 17 2 6 6 28 419 5 8 79'::text
地球にやさしいアルゴリズム---目次 - 地球にやさしいアルゴリズム：ITpro
アルゴリズムを構成している楽しい仕組みを紹介しながら，あなたに「おおっ」と言わせることが，本連載の最初の目的です。興味を持てたなら，アルゴリズムに関する文献や情報を抵抗なく読めるようになるはずです。アルゴリズムを使いこなしたり，作ることも無理なくできるようになるでしょう。 まずはいろいろなアルゴリズムの面白いところを見て，楽しんでみましょう 第1回 ナンプレを解いてみよう 第2回 パズルみたいに楽しいデータ圧縮 第3回 「場面」の移り変わりに注目する 第4回 できるだけ短いルートでゴールに到達する 第5回 隣の区画と異なる色で地図を四色に塗り分ける 第6回 上手なアルゴリズムの見つけ方 第7回 多対多の関係を賢く扱う 第8回 倉庫番を解くアルゴリズム 第9回 プロトコルを実現するアルゴリズム 第10回 麻雀の役を判定する 第11回 プログラム同士の対戦ゲーム 第12回 対戦ゲームの戦略を考
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
