[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[jfriends-ml 13320] 数独のソースコード
前橋です。
合宿に参加された皆様、お疲れ様でした。
特に幹事の高橋智弘さん、お世話になりました。
さて、うちのチームの課題だった数独のソルバですが、
昼食時に回していたバージョンはやはりバグっていたようで、
無限ループに陥っていました。修正して動くようになりましたので
展開します。
私の環境で30秒くらいかかります。総当りなのもありますし、
ArrayListから頻繁に要素を出し入れしたりArrayListの2次元配列を
頻繁に複製したりで効率が悪いんでしょう。
しかしまあ、それはさておき、実のところ私はJavaはTiger以降は
ろくに使っていなかったのですが、今回、ジェネリックなArrayListの
2次元配列を作ろうとしていきなりはまって、なんだこりゃと
思ったことですよ。確かにJavaのGenericsは実態は単なるObjectであり、
Javaの配列は実行時型情報を持っている(ArrayStoreException用)ので
当たり前ではあるのですが。使えねえ……
今回のプログラムでジェネリックでないArrayListを使っているのは
それが理由です。
今回の合宿はたいへん刺激になりました。ありがとうございました。
--
------------------------------------------------------------
前橋 和弥 Mail: PXU00211@xxxxxxxxxxx
URL: http://kmaebashi.com
------------------------------------------------------------
import java.util.*;
class SuDoku {
static int[][] src = {
{0, 0, 8, 0, 0, 5, 9, 0, 0},
{2, 0, 0, 0, 3, 0, 0, 4, 0},
{1, 9, 0, 0, 0, 7, 0, 0, 5},
{0, 0, 0, 8, 0, 0, 5, 0, 0},
{0, 4, 0, 3, 9, 6, 0, 7, 0},
{0, 0, 3, 0, 0, 2, 0, 0, 0},
{4, 0, 0, 5, 0, 0, 0, 1, 9},
{0, 8, 0, 0, 1, 0, 0, 0, 6},
{0, 0, 5, 7, 0, 0, 2, 0, 0},
};
static int[][] src2 = {
{3, 6, 8, 1, 4, 5, 9, 2, 7},
{2, 5, 7, 6, 3, 9, 1, 4, 8},
{1, 9, 4, 2, 8, 7, 3, 6, 5},
{6, 2, 9, 8, 7, 1, 5, 3, 4},
{5, 4, 1, 3, 9, 6, 8, 7, 2},
{8, 7, 3, 4, 5, 2, 6, 9, 1},
{4, 3, 6, 5, 2, 8, 7, 1, 9},
{7, 8, 2, 9, 1, 3, 4, 5, 6},
{9, 1, 5, 7, 6, 4, 2, 8, 3},
};
public static void solve(Board board, int startRow, int startCol) {
if (!board.refine()) {
return;
}
if (board.fixed()) {
if (!board.check()) {
return;
}
board.dump();
System.out.println(new Date());
System.exit(0);
}
for (int row = startRow; row < 9; row++) {
int col;
if (row == startRow) {
col = startCol;
} else {
col = 0;
}
for (; col < 9; col++) {
if (board.board[row][col].size() == 1)
continue;
Board newBoard = board.deepCopy();
for (int i = 0; i < board.board[row][col].size(); i++) {
ArrayList al = new ArrayList();
al.add(board.board[row][col].get(i));
newBoard.board[row][col] = al;
solve(newBoard, row, col);
}
}
}
}
public static void main(String[] args) {
/*
Board b = new Board(src2);
System.out.println("check result.." + b.check());
*/
Board b = new Board(src);
System.out.println(new Date());
solve(b, 0, 0);
/*
b.refine();
b.dump();
*/
}
}import java.util.*;
class Board {
ArrayList[][] board = new ArrayList[9][9];
Board() {
super();
}
Board(int [][] src) {
for (int row = 0; row < src.length; row++) {
for (int col = 0; col < src[row].length; col++) {
ArrayList al = new ArrayList();
if (src[row][col] != 0) {
al.add(src[row][col]);
this.board[row][col] = al;
} else {
for (int i = 1; i <= 9; i++) {
al.add(i);
}
this.board[row][col] = al;
}
}
}
}
boolean refineHorizontal(int row) {
ArrayList fixed = new ArrayList();
for (int col = 0; col < this.board[row].length; col++) {
if (this.board[row][col].size() == 1) {
fixed.add(this.board[row][col].get(0));
}
}
for (int col = 0; col < this.board[row].length; col++) {
if (this.board[row][col].size() == 1) {
continue;
}
for (int i = 0; i < fixed.size(); i++) {
this.board[row][col].remove(fixed.get(i));
if (this.board[row][col].size() == 0) {
return false;
}
}
}
return true;
}
boolean refineVertical(int col) {
ArrayList fixed = new ArrayList();
for (int row = 0; row < this.board[col].length; row++) {
if (this.board[row][col].size() == 1) {
fixed.add(this.board[row][col].get(0));
}
}
for (int row = 0; row < this.board[col].length; row++) {
if (this.board[row][col].size() == 1) {
continue;
}
for (int i = 0; i < fixed.size(); i++) {
this.board[row][col].remove(fixed.get(i));
if (this.board[row][col].size() == 0) {
return false;
}
}
}
return true;
}
boolean refineBox(int top, int left) {
ArrayList fixed = new ArrayList();
for (int row = top; row < 3; row++) {
for (int col = left; col < 3; col++) {
if (this.board[row][col].size() == 1) {
fixed.add(this.board[row][col].get(0));
}
}
}
for (int row = top; row < 3; row++) {
for (int col = left; col < 3; col++) {
if (this.board[row][col].size() == 1) {
continue;
}
for (int i = 0; i < fixed.size(); i++) {
this.board[row][col].remove(fixed.get(i));
if (this.board[row][col].size() == 0) {
return false;
}
}
}
}
return true;
}
boolean refine() {
for (int i = 0; i < this.board.length; i++) {
if (!this.refineHorizontal(i)) {
return false;
}
}
for (int i = 0; i < this.board.length; i++) {
if (!this.refineVertical(i)) {
return false;
}
}
for (int row = 0; row < 9; row += 3) {
for (int col = 0; col < 9; col += 3) {
if (!refineBox(row, col)) {
return false;
}
}
}
return true;
}
boolean checkHorizontal(int row) {
for (int col1 = 0; col1 < this.board[row].length; col1++) {
for (int col2 = col1 + 1; col2 < this.board[row].length; col2++) {
if (this.board[row][col1].get(0)
.equals(this.board[row][col2].get(0))) {
return false;
}
}
}
return true;
}
boolean checkVertical(int col) {
for (int row1 = 0; row1 < 9; row1++) {
for (int row2 = row1 + 1; row2 < 9; row2++) {
if (this.board[row1][col].get(0)
.equals(this.board[row2][col].get(0))) {
return false;
}
}
}
return true;
}
boolean checkBox(int top, int left) {
ArrayList al = new ArrayList();
for (int row = top; row < top + 3; row++) {
for (int col = left; col < left + 3; col++) {
if (this.board[row][col].size() == 1) {
if (al.contains(this.board[row][col]))
return false;
al.add(this.board[row][col]);
}
}
}
return true;
}
boolean check() {
for (int i = 0; i < this.board.length; i++) {
if (!this.checkHorizontal(i)) {
return false;
}
}
for (int i = 0; i < this.board.length; i++) {
if (!this.checkVertical(i)) {
return false;
}
}
for (int row = 0; row < 9; row += 3) {
for (int col = 0; col < 9; col += 3) {
if (!checkBox(row, col)) {
return false;
}
}
}
return true;
}
private ArrayList deepCopyArrayList(ArrayList src) {
ArrayList ret = new ArrayList();
for (int i = 0; i < src.size(); i++) {
ret.add(src.get(i));
}
return ret;
}
Board deepCopy() {
Board newBoard = new Board();
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
newBoard.board[row][col]
= deepCopyArrayList(this.board[row][col]);
}
}
return newBoard;
}
boolean fixed() {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (this.board[row][col].size() > 1) {
return false;
}
}
}
return true;
}
void dump() {
for (int row = 0; row < this.board.length; row++) {
for (int col = 0; col < this.board[row].length; col++) {
for (int i = 0; i < this.board[row][col].size(); i++) {
System.out.print("" + (Integer)board[row][col].get(i)
+ " ");
}
if (col < this.board[row].length - 1) {
System.out.print(", ");
}
}
System.out.print("\n");
}
}
}