世界一難しい数独 数学者作成

http://headlines.yahoo.co.jp/hl?a=20100824-00000018-zdn_g-ent

さっそく解いてみました。
47ms で解けました！＼（＾ｏ＾）／

まぁ、自分で解いたわけではなく、プログラムに解かしてみました。
実際に解いたのは、昔、nimoさんが作ったプログラムです。
http://d.hatena.ne.jp/keyword/%BF%F4%C6%C8

計算時間だけからいうと、日経サイエンス2006年9月号P55の方が難しいんじゃ
ないかな？＞43438ms
それに最初の数字の個数も日経サイエンスの方が圧倒的に少ないです。

/**
 * Sudoku
 *
 * @author nimo
 * @date   2006/08/01
 */

import java.util.*;

/**
 * ９×９専用。
 * ニモさんが作った数独を解くプログラム。
 * ルールに従って候補を絞る。
 * 絞りきれなかったら、網羅的に試して成り立つ解を探す。
 */
public class SudokuNimo {
    /** 数字盤 */
    private int [][] 数字盤;
    
    //020075010100004508056800200810000700900000003002000045009001430301700009070390020
    //{0,2,0,0,7,5,0,1,0},   // 4 2 8 9 7 5 3 1 6
    //{1,0,0,0,0,4,5,0,8},   // 1 9 3 2 6 4 5 7 8
    //{0,5,6,8,0,0,2,0,0},   // 7 5 6 8 1 3 2 9 4
    //{8,1,0,0,0,0,7,0,0},   // 8 1 5 4 3 9 7 6 2
    //{9,0,0,0,0,0,0,0,3},   // 9 4 7 5 2 6 1 8 3
    //{0,0,2,0,0,0,0,4,5},   // 6 3 2 1 8 7 9 4 5
    //{0,0,9,0,0,1,4,3,0},   // 2 8 9 6 5 1 4 3 7
    //{3,0,1,7,0,0,0,0,9},   // 3 6 1 7 4 2 8 5 9
    //{0,7,0,3,9,0,0,2,0},   // 5 7 4 3 9 8 6 2 1
    
    //000010000301400860900500200700160000020805010000097004003004006048006907000080000
    //{0,0,0,0,1,0,0,0,0},   // 4 5 2 6 1 8 3 7 9
    //{3,0,1,4,0,0,8,6,0},   // 3 7 1 4 2 9 8 6 5
    //{9,0,0,5,0,0,2,0,0},   // 9 8 6 5 7 3 2 4 1
    //{7,0,0,1,6,0,0,0,0},   // 7 3 4 1 6 2 5 9 8
    //{0,2,0,8,0,5,0,1,0},   // 6 2 9 8 4 5 7 1 3
    //{0,0,0,0,9,7,0,0,4},   // 8 1 5 3 9 7 6 2 4
    //{0,0,3,0,0,4,0,0,6},   // 2 9 3 7 5 4 1 8 6
    //{0,4,8,0,0,6,9,0,7},   // 1 4 8 2 3 6 9 5 7
    //{0,0,0,0,8,0,0,0,0},   // 5 6 7 9 8 1 4 3 2
    
    //200370009009200007001004002050000800008000900006000040900100500800007600400089001
    //{2,0,0,3,7,0,0,0,9},  // 2 8 4 3 7 5 1 6 9
    //{0,0,9,2,0,0,0,0,7},  // 6 3 9 2 1 8 4 5 7
    //{0,0,1,0,0,4,0,0,2},  // 5 7 1 9 6 4 3 8 2
    //{0,5,0,0,0,0,8,0,0},  // 1 5 2 4 9 6 8 7 3
    //{0,0,8,0,0,0,9,0,0},  // 3 4 8 7 5 2 9 1 6
    //{0,0,6,0,0,0,0,4,0},  // 7 9 6 8 3 1 2 4 5
    //{9,0,0,1,0,0,5,0,0},  // 9 6 7 1 4 3 5 2 8
    //{8,0,0,0,0,7,6,0,0},  // 8 1 3 5 2 7 6 9 4
    //{4,0,0,0,8,9,0,0,1},  // 4 2 5 6 8 9 7 3 1
    
    // 問題0024
    //000007200061020080200900030700000400090000060004000009020003004030060170009700000
    //{0,0,0, 0,0,7, 2,0,0},
    //{0,6,1, 0,2,0, 0,8,0},
    //{2,0,0, 9,0,0, 0,3,0},
    //{7,0,0, 0,0,0, 4,0,0},
    //{0,9,0, 0,0,0, 0,6,0},
    //{0,0,4, 0,0,0, 0,0,9},
    //{0,2,0, 0,0,3, 0,0,4},
    //{0,3,0, 0,6,0, 1,7,0},
    //{0,0,9, 7,0,0, 0,0,0},
    
    // 日経サイエンス
    
    // メイン
    public static void main(String[] args) {
//        String 問題 = "000007200061020080200900030700000400090000060004000009020003004030060170009700000";
    	// 日経サイエンス2006年9月号P52中央	結果 time:15ms
        //String 問題 = "900630004010258000000700008640020500000000000820500090000000870300005040001076000";
    	// 日経サイエンス2006年9月号P55 SF	結果 time:43438ms
        //String 問題 = "010000009000300800000000600000012400703000000500000000800600000000040020000700050";
        // 解けたら天才！ フィンランドの数学者が作った「世界一難しい数独」結果 time:47ms
    	String 問題 = "005300000800000020070010500400005300010070006003200080060500009004000030000009700";
        if (args.length > 0) {
            問題 = args[0];
        }
        SudokuNimo sudoku = new SudokuNimo(問題);
        System.out.println("問題");
        sudoku.print();
        
        Date start = new Date();
        String result = sudoku.解析実行();
        Date end = new Date();
        
        System.out.println("結果 time:" + (end.getTime() - start.getTime()) + "ms");
        sudoku.print();
    }
    
    /** Constructor */
    public SudokuNimo(String 問題) {
        convert(問題);
    }
    
    // 解析実行
    private String 解析実行() {
        boolean flg = true;
        boolean forceFlg = false;
        String before = toString();
        String result = null;
        while (flg) {
            flg = !解析処理(forceFlg);
            result = toString();
            if (before.equals(result)) {
                if(forceFlg) {
                    System.out.println("むりぽ");
                    flg = false;
                }
                // 最初は普通に埋めていき、手が進まないので数字を入れて試してみる
                forceFlg = true;
            }
            before = result;
        }
        return result;
    }
    
    // 解析処理
    private boolean 解析処理(boolean forceFlg) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (数字盤[i][j] == 0) {
                    int num = get数値(i, j, forceFlg);
                    if (num > 0) 数字盤[i][j] = num;
                }
            }
        }
        return toString().indexOf("0") == -1;
    }
    
    // 指定された場所で使用できる数値のリスト
    private List get候補値の取得(int row, int col) {
        List list = new ArrayList();
        for (int num = 1; num <= 9; num++) {
            list.add(new Integer(num));
        }
        
        // グループで使用されている数字は除外
        int g_row = row / 3;
        int g_col = col / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                list.remove(new Integer(数字盤[g_row * 3 + i][g_col * 3 + j]));
            }
        }
        
        // 行と列から既にある数字は除外
        for (int i = 0; i < 9; i++) {
            list.remove(new Integer(数字盤[row][i]));
            list.remove(new Integer(数字盤[i][col]));
        }
        if (list.size() == 0) {
            throw new IllegalStateException("手詰まり");
        }
        
        return list;
    }
    
    // 指定された場所の数値を取得
    private int get数値(int row, int col, boolean forceFlg) {
        List list = get候補値の取得(row, col);
        if (list.size() == 1) {
            // 使えるのが1つしかないので確定!
            return ((Integer)list.get(0)).intValue();
        } else {
            return 候補値から数値の絞込み(row, col, list, forceFlg);
        }
    }
    
    // 指定された場所の数値を取得
    private int 候補値から数値の絞込み(int row, int col, List list, boolean forceFlg) {
        int num;
        int g_row = row / 3;
        int g_col = col / 3;
        int p_row = row % 3;
        int p_col = col % 3;
        for (int k = 0; k < list.size(); k++) {
            num = ((Integer)list.get(k)).intValue();
            int[][] グループ = new int[3][3];
            // 3×3のグループで見てみる
            // グループと同じ列又は行のグループで候補の数字が使用されている状態を調べる
            // A X X X X X X X X
            // X X X X A X X X X
            // X X X X X X B C ? この場合?はAになる
            for (int i = 0; i < 3; i++) {
                System.arraycopy(数字盤[g_row * 3 + i], g_col * 3, グループ[i], 0, 3);
            }
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 9; j++) {
                    if (num == 数字盤[g_row * 3 + i][j]) {
                        for (int l = 0; l < 3; l++) {
                            グループ[i][l] = num;
                        }
                        break;
                    }
                }
                for (int j = 0; j < 9; j++) {
                    if (num == 数字盤[j][g_col * 3 + i]) {
                        for (int l = 0; l < 3; l++) {
                            グループ[l][i] = num;
                        }
                        break;
                    }
                }
            }
            
            // 他に0のところが無ければ確定!
            boolean flg = true;
            グループ[p_row][p_col] = num;
            for (int i = 0; i < 9; i++) {
                if (グループ[i / 3][i % 3] == 0) {
                    flg = false;
                    break;
                }
            }
            if (flg) return num;
        }
        
        // ここにいいロジックがあればええんだけど・・・
        
        
        // 最終手段として、候補の値を入れてみて試してみる。(w
        if (forceFlg) {
            for (int k = 0; k < list.size(); k++) {
                num = ((Integer)list.get(k)).intValue();
                try {
                    数字盤[row][col] = num;
                    String res = new SudokuNimo(toString()).解析実行();
                    //System.out.println("result = " + res);
                    convert(res);
                    return num;
                } catch (Exception e) {
                    // 手詰まりの場合は次の候補で試してみる
                    //System.out.println("(" + row + ", " + col + ") = " + num + " is failed.");
                }
            }
        }
        return 0;
    }
    
    // 文字列→int[][]に変換
    private void convert(String data) {
        int datas[][] = new int[9][9];
        int num;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                try {
                    num = data.charAt(i * 9 + j) - '0';
                    if (num < 0 || num > 9) num = 0;
                } catch (Exception e) {
                    num = 0;
                }
                datas[i][j] = num;
            }
        }
        数字盤 = datas;
    }
    
    // 数字盤の文字列表現を取得する
    public String toString() {
        StringBuffer buf = new StringBuffer();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                buf.append(数字盤[i][j]);
            }
        }
        return buf.toString();
    }
    
    // 数字盤を標準出力へ出力する
    void print() {
        StringBuffer buf = new StringBuffer();
        for (int i = 0; i < 9; i++) {
            if (i % 3 == 0) buf.append("+-------+-------+-------+\n");
            for (int j = 0; j < 9; j++) {
                if (j % 3 == 0) buf.append("| ");
                buf.append(数字盤[i][j]);
                buf.append(" ");
            }
            buf.append("|\n");
        }
        buf.append("+-------+-------+-------+\n");
        System.out.println(buf.toString());
    }
}