vol2‎ > ‎

[話題] ナンプレ&魔方陣

NEW  2016年05月30日に行われた「ナンプレと魔方陣 解いたり作ったり数えたり」 SHOSEN の動画です.


前半

YouTube 動画



後半

YouTube 動画


関連動画 マルチカノニカル法によるレアイベントサンプリング

YouTube 動画




ナンプレ関係(とん)

本文を読んで興味を持った方は、暗黒通信団より刊行された 『ヒントの少ないナンプレの作り方』 もどうぞ。

手筋集

ナンプレを解く際に使うテクニック(手筋)のリスト

色々な手筋を使ってヒント数17のナンプレ49,157問を解いた結果

使った手筋 解けた数
Hidden Single  17,233問 (35.06%)
Naked Single  0              (0%)
Singles  21,905     (44.56%)
Singles + Locked Candidates (※)  37,375     (76.03%)
Singles + Hidden Pair  31,398     (63.87%)
Singles + Naked Pair  27,577     (56.10%)
Singles + Locked Candidates + Hidden Pair  41,428     (84.28%)
Singles + Locked Candidates + Subsets + Basic Fish  41,669     (84.77%)
※ 本文中の実験で使った組合せ

問題作成のためのナンプレソルバー

高速なソルバー

・Brian Turner, BB Sudoku, v1.0, October 2009,

・Mladen Dobrichev, Fast Simple Sudoku Solver, v8.6, February 2010,
 ・https://sites.google.com/site/dobrichev/fsss


魔方陣の数を数える(北島)

論文

Trump氏による推定値


比熱の正体はフィッシャー情報量(伊庭)

比熱の正体はフィッシャー情報量 途中の計算全部(PDF)


レプリカ交換法とマルチカノニカル法(伊庭)

 マルチカノニカル法によるレアイベントサンプリング(DSオリジナル)約20分 上のほうに出てるのと同じです

YouTube 動画



レプリカ交換法の講義動画(統計数理研究所) 約2時間

レプリカ交換モンテカルロ法講義(伊庭)



計算統計II」(岩波書店) の第1部にレプリカ交換モンテカルロ法とラテン方陣の数の計算の解説がある

「確率的情報情報処理と統計力学」(サイエンス社)に福島氏によるレプリカ交換モンテカルロ法の解説がある(が在庫切れの模様)

マルチカノニカル法をレアイベントの観点から解説した総合報告 (Iba, Saito and Kitajima (2014))

以前に書いた拡張アンサンブル法のまとめ論文(Iba(2001))
http://arxiv.org/abs/cond-mat/0012323

菊池誠氏の解説(レプリカ交換モンテカルロ法,マルチカノニカル法にも触れている)
・モンテカルロで行こう! または、ダイスをころがせ
http://www.cp.cmc.osaka-u.ac.jp/~kikuchi/texts/MonteCarlo.pdf
・モンテカルロ法のアヴァンギャルド
http://www.cp.cmc.osaka-u.ac.jp/~kikuchi/texts/tenbou98.pdf



個数の推定とMCMC,その他関連リンク集(伊庭)

業界が違うと交流が少なく分かれている感じがするので,この際いろいろ集めてみました.詳しくない分野や読んでない論文・解説も自分のメモ代わりに入れてあります.※「数え上げ」というのは本当に全数を調べることなので「個数の推定」に修正しました.

◇レプリカ交換法を使って数独を作る話

レプリカ交換法はサンプリング法というより最適化手法として使われていると思われる.
著者の渡辺宙志氏による解説ページ
(論文)Difficult Sudoku Puzzles Created by Replica Exchange Monte Carlo Method

◇ありとあらゆる「意味のある整数列」のデータベース

いろんな数字の列がこれでもかと.中にはラテン方陣・魔方陣の個数も含まれる.
On-Line Encyclopedia of Integer Sequences

◇正確確率検定とMCMC/SMC(統計学系)

一番簡単な原型の解説.
フィッシャーの正確確率検定とは(奥村 晴彦氏のサイト)

複雑な表をMCMCで扱う.動かし方を工夫して規則を破らないで動かすという考え方.
マルコフ基底と分割表解析への応用について(原尚幸氏のIBISでの発表スライド)
MCMC in I×J×K (Bunea and Besag ,この本の一部のプレプリント)

逐次モンテカルロ法で中身が01の表を扱う(Chen et al (2005) JASA).

ダイアコニス氏によるMCMCの応用についての紹介.分割表も一瞬だけ出てくる.

◇MCMCによる個数の推定(統計物理系)

参照→「魔方陣の数を数える」「レプリカ交換法とマルチカノニカル法」

すごく大きなラテン方陣・N-queenの個数の推定をMCMCでやっている論文.大きいサイズのラテン方陣で比熱が二峰性になっているがホントだろうか.計算手法は引用論文にあるが,simulated temperingをワン・ランダウっぽくした感じか.
Counting Solutions for the N-queens and Latin Square Problems by Efficient Monte Carlo Simulations

福島孝治氏の昔の仕事(N-queenの数とか.Hukushima (2002))
Extended ensemble Monte Carlo approach to hardly relaxing problems

マルチカノニカル法でラマヌジャングラフの個数を推定する(Saito and Iba(2011))
Probability of graphs with large spectral gap by multicanonical Monte Carlo

◇MCMCによる個数の推定(組み合わせ論系)

組み合わせ論系・応用数理系の研究者もMCMCでの個数の推定を研究しているらしいが,魔方陣のような難しい対象(物理でいうフラストレート系)よりもより易しいものを厳密に扱う(たとえば大偏差不等式+パーフェクトシミュレーション)ことに興味があるようにみえる.
MCMC法と近似精度保証(来嶋秀治氏による解説)
Approximate Counting (Martin Dyer氏の講義のスライド)

以下はこの業界の重鎮と思われる先生方のサイトへのリンク.

◇ラテン方陣(ラテン方格)


ラテン方陣をランダムに生成する.JacobsonとMatthewsのアルゴリズムというラテン方陣専用のMCMCがあって「わずかに制約をやぶるだけ」でうまく動かせるとのこと.
Random Latin squares (Peter J. Cameron氏による解説.上のMCMCの解説を含む)
Generation of Random Latin Squares Step By Step and Graphically (Ignacio Gallego Sagastume氏による解説,MCMCを実装した報告)

ラテン方陣の穴埋めの相転移.「ラテン方陣に穴を開けてそこを埋める」という数独を簡易化したタスクについて「解が唯一でなくてもよい」とすると,穴の比率がある割合のときに「難しさ最大」になるという研究.相転移とかedge of chaosのノリだと思う.
Completing Latin Squares (論文の著者の一人Carla Gomes氏による一般向き解説)

◇その他

「Latin square」でarxivを検索

「数独」 でarxivを検索

眺めてるといろいろ出てきて面白い.