実行ボタンを押すと，それぞれのプログラムが実行され，約１５秒ほどで答えが戻ります

数独インデックスから解盤面へ

解盤面から数独インデックスへ

数独インデックス

概要

数独の解盤面は，大ざっぱにいうと， 約 60 垓個（6 の後ろに 0 が 21 個並ぶ）通りあることが知られています．
我々は， その解盤面一つ一つに番号付け（数独インデックス）を与えました．
このページでは， 解盤面→数独インデックス，数独インデックス→解盤面の両方が， 約 10 秒程度で計算できます．
右のフォームから実行できるので， 試してみてください．

注釈：

1. 「数独」はニコリの登録商標．一般名は Number Place です． 対象とするのは１〜９までの数を埋める通常の数独です．
2. B. Felgenhauer and F. Jarvis (2005) の結果． このインデックスも彼らの考え方に基づいています（詳しくは解説参照）．
3. この番号付けを参照する際には Togami-Watanabe Index と呼んで頂けると幸いです．

質問等は watanabe(at)is.titech.ac.jp まで．
リンクをはる際の許可は不要ですので回答は省略させて頂きます． ご自由にはって下さい．

更新履歴

1. 値が帰ってこない，間違ったIndexが出力される等の不具合を修正しました． (2007/6/10)

解説とリンク先

１．どんな計算をしているの？

解盤面から数独インデックスを求める際， 全部の解盤面を探索する方法では 5000 万年かかってしまいます． 一方， すべての解盤面を保存しておけば，数秒でできますが， そのためには 1億 Peta Byte の記憶領域が必要になります．

Felgenhauer と Jarvis は 2005 年の論文で， すべての解盤面を 71 通りに分類することに成功し， それにより，解盤面の総数を数えました． 我々も，この 71 通りのパターン各々ごとに， そのパターンに分類される解盤面をすべて探索する方法を前計算し， それを探索補助データとして用いることで計算の高速化に成功しました． 上記の，解盤面→数独インデックス，数独インデックス→解盤面，の計算は， その探索補助データ（圧縮形式で 4 GB）を用いた計算です．

補足：

1. 正確には彼らの分類を 67 パターンまでに改良しました．
2. 探索補助データの計算には東工大のスパコングリッドTSUBAMEを使いました．
   1 万 CPU 中の 60 CPU を使って，約４時間の計算でした．

２．プログラムについて

基本的には，バックトラック法により 解盤面を次々に生成していくことによって番号付けを実現しています． 同型変換と名づけた変換を用いることにより，また， ある区間に対する解盤面の存在数を予めファイルに 保存しておくことにより，探索する範囲を狭くしています． 更に探索速度そのものを早くする試みとして， 先に述べた探索補助データを用いています．

３．各種リンク

1. Sudoku enumeration problems ：Felgenhauer 氏が作成したプログラムやデータのページ．
2. 数独の解生成と解に対する番号付け(概要) ：S.Togamiの卒業論文概要(PDF, 102KB)
3. 数独の解生成と解に対する番号付け ：S.Togamiの卒業論文(PDF, 802KB)
4. 数独の解生成と解に対する番号付け(pptx) ：S.Togamiの卒業論文発表資料(PDF, 1.01MB)