世界最高難度の数独

世界最高難易度の数独が公開されたというニュースを伝え聞いた．自分ではほとんどこういうパズルはしないのだが，コンピュータで解いたらどのくらい時間が掛かるのだろうか，という好奇心で，試してみた．

SageにはSudokuというクラスがあって，その名の通り数独のソルバーである．問題を入力し，ボタン一発で回答が得られる．問題を与える形式には幾つかの方法があるが，下では$9\times 9$の整数行列として与えている．空欄は$0$とする．

A=matrix(ZZ,[[8,0,0,0,0,0,0,0,0],[0,0,3,6,0,0,0,0,0],[0,7,0,0,9,0,2,0,0],[0,5,0,0,0,7,0,0,0],[0,0,0,0,4,5,7,0,0],[0,0,0,1,0,0,0,3,0],[0,0,1,0,0,0,0,6,8],[0,0,8,5,0,0,0,1,0],[0,9,0,0,0,0,4,0,0]]) q=Sudoku(A) print "The problem is\n", q ans = q.solve() print "The answer is\n", ans.next()

解答はあっという間にえられて，問題を入力している時間の方が長いのだった．

Linear functional

Sageをblogに埋め込むテスト第2弾として，以前線形代数の講義で配布した，SageTeXのデモのプリントをblog記事にしてみる． Linear functionalの例．内積の入ったベクトル空間でLinear functional（係数体への線型写像のこと）が内積で実現されることの例を与える．実数係数の1変数，高々2次の多項式の空間$P_2(\mathbf{R})$を，多項式の和と定数倍で実ベクトル空間と考える．内積は，二つの多項式の積を，$[0,1]$区間で積分することで定める: $$\langle p, q\rangle = \int_0^1 p(x)q(x)\, dx,\quad p, q\in P_2(\mathbf{R}).$$ 更に，考えるlinear functionalは，多項式に$\cos(\pi x)$ を掛けて，$[0,1]$区間で積分するものとする: $$\varphi(p) = \int_0^1 p(x)\cos(\pi x)\,dx. $$ すると，$q\in P_2(\mathbf{R})$がただ一つ存在して，$\varphi(p) = \langle p, q\rangle$となるのだった．しかも，この$q$は，$$q(x) = \sum_{j=1}^n \varphi(e_j) e_j$$で与えられる．但し $(e_1,\dots, e_n)$は考えているベクトル空間の正規直交基底である（今の場合だと，例えば$(1, x, x^2)$という基底から，Gram-Schmidtの直交化を施してえられる）． こういった計算を，実際にSage cell serverを使い，blogの上で実行できるのである．

上の，「Evaluate」のボタンを押して頂きたい．詳しくは，Sage Cell Serverのドキュメントを参照のこと．特に，Exampleが参考になる．

最初のテスト

階乗を計算する：

その他の例を試してみよう： 他の例を自分で入力して試してみよう（evaluateのボタンを押すこと）．