数独
nimoさんから許可が出たので載せます。
/** * Sudoku * * @author nimo * @date 2006/08/01 */ import java.util.*; /** * 9×9専用。 */ public class Sudoku { /** 数字盤 */ 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"; if (args.length > 0) { 問題 = args[0]; } Sudoku sudoku = new Sudoku(問題); 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 Sudoku(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 Sudoku(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()); } }
半角で(( と ))をはさむと特殊な記法になっちゃうので、3箇所スペースを入れてます。
))*1(( 囲めばOKなんですね。元のソースに戻しました。
*1: こういうふうに