[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");
	}
    }
}