[話題] ナンプレ＆魔方陣
前半
後半
関連動画 マルチカノニカル法によるレアイベントサンプリング
ナンプレ関係（とん）
本文を読んで興味を持った方は、暗黒通信団より刊行された 『ヒントの少ないナンプレの作り方』 もどうぞ。
手筋集
ナンプレを解く際に使うテクニック（手筋）のリスト
Solving Technique - Sudopedia Mirror
色々な手筋を使ってヒント数17のナンプレ49,157問を解いた結果
※ 本文中の実験で使った組合せ
問題作成のためのナンプレソルバー
・NPSfG (Number Place Solver for Generators)
高速なソルバー
・Brian Turner, BB Sudoku, v1.0, October 2009,
・https://sites.google.com/site/bbsudokufiles/
・Mladen Dobrichev, Fast Simple Sudoku Solver, v8.6, February 2010,
・https://sites.google.com/site/dobrichev/fsss
魔方陣の数を数える（北島）
論文
Kitajima A, Kikuchi M (2015) Numerous but Rare: An Exploration of Magic Squares. PLoS ONE 10(5): e0125062. doi:10.1371/journal.pone.0125062
Pinn K, Wieczerkowski C (1998) Number of Magic Squares from Parallel Tempering Monte Carlo. Int J Mod Phys C9: 541–546. doi: 10.1142/S0129183198000443. [arxiv]
大石弥幸(1992) 「ランダムサンプリングによる6次魔方陣の総数の推定」『数芸パズル』177号, pp.13-20. （大石氏のWebサイト の脚注に、本文PDFへのリンクあり）
Trump氏による推定値
比熱の正体はフィッシャー情報量（伊庭）
レプリカ交換法とマルチカノニカル法（伊庭）
マルチカノニカル法によるレアイベントサンプリング（DSオリジナル）約20分 上のほうに出てるのと同じです
レプリカ交換法の講義動画（統計数理研究所） 約２時間
「計算統計II」（岩波書店） の第1部にレプリカ交換モンテカルロ法とラテン方陣の数の計算の解説がある
「確率的情報情報処理と統計力学」（サイエンス社）に福島氏によるレプリカ交換モンテカルロ法の解説がある（が在庫切れの模様）
マルチカノニカル法をレアイベントの観点から解説した総合報告 (Iba, Saito and Kitajima (2014))
Multicanonical MCMC for Sampling Rare Events
以前に書いた拡張アンサンブル法のまとめ論文(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
個数の推定とＭＣＭＣ，その他関連リンク集（伊庭）
業界が違うと交流が少なく分かれている感じがするので，この際いろいろ集めてみました．詳しくない分野や読んでない論文・解説も自分のメモ代わりに入れてあります．※「数え上げ」というのは本当に全数を調べることなので「個数の推定」に修正しました．
◇レプリカ交換法を使って数独を作る話
レプリカ交換法はサンプリング法というより最適化手法として使われていると思われる．
（論文）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)．
Sequential Monte Carlo methods for statistical analysis of tables
ダイアコニス氏によるMCMCの応用についての紹介．分割表も一瞬だけ出てくる．
The Markov Chain Monte Carlo Revolution
◇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のノリだと思う．
Generating Satisfiable Problem Instances （Achlioptas et al）
Completing Latin Squares （論文の著者の一人Carla Gomes氏による一般向き解説）
◇その他
眺めてるといろいろ出てきて面白い．