あらゆる数独パズルを解く
Peter Norvig / 青木靖 訳 このエッセイでは、 あらゆる数独パズルを解くという問題に取り組む。制約伝播と探索という2つのアイデアを使うと、ごく簡単に解けるということがわかる(主要なアイデアはコードにして1ページたらずで、補足的なコードが2ページある)。 数独の記法と予備概念 最初に記法をいくつか決めておこう。数独パズルは81個のマス(square)からなる盤面を使う。数独ファンの多くはカラムを1-9で、行をA-Iでラベル付けしており、カラム、行、ボックスのような9個のマスの集まりをユニット(unit)と呼び、ユニットを共有するマスをピア(peer)と呼んでいる。パズルではマスのいくつかが空いており、他は数字が入っている。パズルの目的はこうだ。 それぞれのユニットのマスが1から9の数字の順列によって埋められるようにする。 つまり、1つのユニットに同じ数字が2度現れてはならず、そ
頑張りすぎずに生産性を上げるには：行き詰まりを起こす「プラトー」8つの要因 | ライフハッカー・ジャパン
FarnamStreet：一生懸命やっているのに、全然うまくいかないことってありますよね。ハードな練習を重ねているのに、ピアノがなかなか上達しないとか...。Bob Sullivan氏とHugh Thompson氏によると、それは「プラトー」（一時的な停滞）と呼ばれる現象だそうです。 両者は共著『The Plateau Effect（プラトー現象）』の中で、「ただ頑張り続けるのは間違った戦略です」といっています。「宇宙は毎日、頑張ることが答えだと人々に信じ込ませようとしています。私たちが伝えたいのはそのことです」 頑張ることが答えでないとしたら、何が答えなのでしょうか？ Thompson氏とSullivan氏は、プラトーが起きる8つの要因を挙げ、それを乗り越える方法を教えています。 要因 1：免疫 生活習慣、人間関係、ビジネス、どんな領域でも、同じやり方やテクニックを続けていると、免疫がで
TimeComplexity - Python Wiki
This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or still-under development versions of CPython) may have slightly different performance characteristics. However, it is generally safe to assume that they are not slower by more than a factor of O(log n). Generally, 'n' is the number of elements current
就活分析録 『数独プログラミング』 ~~「解答が1通り」の数独の問題を自動生成するプログラムの実装と性能評価 ~~
就活・インターンのための情報サイト。Webテスト・ES・志望理由・OB訪問・会社説明会・面接・TOEIC・英語の勉強など 【プログラミングのトピックとしての数独】 数独は9×9のマス目に1~9の数字を単純なルールに基づいて埋めていくパズルです。 http://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%AC 2005年頃から雑誌のパズル欄に登場して以来、世界的に有名になりました。最近では、数独のパズルだけを数百個収録した本も売っているくらいです。電車で数独を説いている人を見たことのある人も多いのではないでしょうか。 数独はプログラミングのトピックとしてとても興味深いです。ルール自体は誰でも1分で理解できる単純明快なものですが、 ・「問題を解くための戦略が複数種類存在する」 ・「解答が1通りになるような数独の問題を生成する時に許される『空白マス数の最大値』が問
数独の高速化 - Cybozu Inside Out | サイボウズエンジニアのブログ
「サイボウズ・アドベントカレンダー」の4日目です（これまでの記事一覧）。どうやら三日坊主は免れたようです（笑）。 (0) はじめに こんにちは。サイボウズ・ラボの川合秀実です。私は主にサイボウズ製品の高速化のお手伝いをしています。しかし先日、製品とは関係ないものを高速化したので、今日はそれを発表します。 サイボウズには社内勉強会がいくつかあって、その中にはC++の勉強会もあります。私はサイボウズの勉強会に参加するのが好きなので、このC++の勉強会に参加してみました。この勉強会では、「数独」というパズルを解くプログラムをC++で書いてみよう、というのが最初のテーマでした。参加者各自がプログラムを書き、翌週にお互いにレビューしあうということが行われました。 ここで私はやらかしてしまいました。ええ、そうです、高速化してしまったのです！ 言うまでもないですが、誰もこんなことは望んでいません。そもそ
グラフ理論（Graph theory） - kanetaiの二次記憶装置
(無向)グラフの要素 要素が頂点(vertex), 点(point), 節点(node)の集合 辺(edge)と呼ばれる頂点の順序対の集合 隣接(adjacent) : 辺(u,v)が存在するとき頂点は隣接するという。 接続(incident) : が辺の端点(endpoint)であるとき、はに接続するという。 多重グラフ(multigraph) : 多重辺(multiple edges)または自己ループ(roop)を含むグラフ ※多重辺やループのない多重グラフをグラフと定義している。 部分グラフ(subgraph) : induced subgraph : 両端点がにある辺を全てが含むならば、をによって生成された(generated)部分グラフと呼ぶ。 次数(degree) 次数(degree) : に接続する辺の個数 孤立点(isolated vertex) : 次数0の頂点 の倍数
三分探索と黄金分割探索 - naoya_t@hatenablog
はい、毎度おなじみのグラフ描きたいだけのエントリですw 今回のお題は「三分探索（ternary search）」。 二分探索（binary search）は割とおなじみかと思うのですが、二分探索が単調増加(減少)関数fについてf(x)=kとなるxを求めるのに対し、三分探索（とか黄金分割探索）は凸関数の極値を求めるのに用います。 詳しくは http://d.hatena.ne.jp/ir5/20090630/1246349028 http://d.hatena.ne.jp/nodchip/20090303/1236058357 辺りを見て頂くとして。 三分探索 探索領域(x0,x3)を三等分するx1,x2を選びます。(x0,x1,x2,x3) で、f(x1)とf(x2)を比べ、f(x)が下に凸な関数なら値が大きい方、上に凸な関数なら値が小さい方の外側（x1ならx0-x1, x2ならx2-x3
Wavelet Treeをもう一度 - 気ままなブログ
文字列本のメインであるウェーブレット木をもう一度素直に見直すことにした。 高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 15人 クリック: 324回この商品を含むブログ (5件) を見る Wavelet Treeに関する著者のスライドは以下である。 http://www.slideshare.net/pfi/ss-15916040 ふらふらと論文を眺めていたら、Navarro神の「Wavelet Trees for All」というサーベイ論文が加筆されて更新されていた。内容自体はあまり変わっていないと思うが図が増えていた。以下がその論文である。 http://www.dcc.uchile.cl/~gnavarro/ps/jda13.pdf 大半の内
Non-Uniform Random Variate Generation
Non-Uniform Random Variate Generation (originally published with Springer-Verlag, New York, 1986) Luc Devroye School of Computer Science McGill University Preface to the Web Edition When I wrote this book in 1986, I had to argue long and hard with Springer Verlag to publish it. They printed a small number of copies, and never bothered with a second printing, even though, surprisingly, there seemed
SIGGRAPH 2012 Course
Instructors Alexander Keller, NVIDIA CorporationSimon PremožeMatthias Raab, NVIDIA CorporationLeonhard Gruenschloss, Weta DigitalSyllabus SyllabusPresentations IntroductionVariance ReductionQuasi-Monte Carlo Methods in Photorealistic Image SynthesisBidirectional Path TracingMetropolis Light TransportCourse Notes Variance Reduction, Bidirectional Path Tracing, Metropolis Light Transport (preliminar
高速な文字列マッチング - 気ままなブログ
最近は、簡潔データ構造を中心に調べたりしていたけど、文字列マッチングを考えた場合、別のアプローチもあります。そう、grepのような逐次文字列検索ですね。以下の解説がおもしろいです。 http://www.i.kyushu-u.ac.jp/~takeda/papers/IPSJMagazineCPM.pdf CSAとかFM-Indexに隠れてしまっていますが、実はかなり強力です。特に、クエリが固定で、テキストが頻繁に変更されるようなケースでは有効です。中でも使いやすのは、Aho-Corasick法(AC法)ですね。複数のパターンを同時に検索することができます。KMPを拡張した方法です。 AC法については、日本語だと 情報検索アルゴリズム 作者: 北研二,津田和彦,獅々堀正幹出版社/メーカー: 共立出版発売日: 2002/01メディア: 単行本購入: 6人 クリック: 552回この商品を含むブ
シャッフルアルゴリズム - Negative/Positive Thinking
はじめに 配列が与えられたとき、それをバラバラに並び替えたい。 C++のSTLのrandom_shuffle関数を実現したい。 Fisher-Yates shuffle http://en.wikipedia.org/wiki/Fisher-Yates_shuffle 一番使われていると思われるシャッフルアルゴリズム。 n個の配列のうち、n番目の数字と、1番目からn番目のどれかをswap。n番目はもう決定したので、これを除いたn-1個の配列 について同様のことを繰り返す。O(N)。 //http://www.cplusplus.com/reference/algorithm/random_shuffle/ template <class RandomAccessIterator, class RandomNumberGenerator> void random_shuffle ( Rand
今年の研究振り返り - Preferred Networks Research & Development
吉田です。弊社では主に研究開発に携わっていますが、最近は顧問的なポジションになっている気がします。 普段は国立情報学研究所 (NII)という所で研究していて、よく論文を国際会議に投稿するということをします。 先日、CIKMという会議の結果が帰ってきて、今年開催される国際会議の結果が全て出そろったので、思い出話をしてみたいと思います。 紹介する論文の順番は、各会議が開催された(る)順です。 所々、専門用語を説明なしに使っていますがご容赦ください。 Yoichi Iwata and Yuichi Yoshida, Exact and Approximation Algorithms for the Constraint Satisfaction Problem over the Point Algebra. (STACS’13) 初めて東大の岩田君と書いた論文です。 岩田君は弊社でインターンや
三角形の内接円と傍接円 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "三角形の内接円と傍接円" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2016年5月) 三角形（黒） 内接円（青）と内心(I) 傍接円（オレンジ）と傍心(JA,JB,JC) 内角の二等分線（赤）と外角の二等分線（緑） 初等幾何学において三角形の内接円（ないせつえん、英: incircle / inscribed circle (of a triangle)）とは、その三角形の内部にあり3辺に接する円である。三角形の内部にある円の中で最も面積が大きい円である。内接円の中心を内心（ないしん、incenter）と呼ぶ。 傍接円（ぼうせつえ
.htm)
「ロボットの運動学と力学」
「詳説ロボットの運動学」補足説明１ ロボットの運動解析に必要な数学と力学 ２００８．４．１ １． ベクトル演算 ２． ロボットの運動解析によく使う関数 ３． 剛体の運動 ４． 剛体の静力学 ５． 剛体の動力学 ロボットの運動を論じることは，幾何学的な運動解析をすることと静力学・動力学解析をすることである．ここで述べるのはロボットの解析に必要な基本的なベクトル演算と力学である． ロボットの解析を理解するためにもっと必要なことは専門書を参照して戴きたい． １． ベクトル演算(vector analysis)と図形のベクトル表現 ロボットの運動で扱う数学は３次元ベクトル演算が大半である．ここではベクトル演算の基本を述べる． ３次元ベクトルを (1.1) と置く．ただ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
就活分析録 Sudoku(数独)の問題自動生成アルゴリズム第2弾
サービス終了のお知らせ
WUPC2nd E問題
慶應大学 理工学部 講義 数値計算法 第十ニ回 モンテカルロ法
三角形の面積を外接円の半径を使って求める