View source for Aritalab:Lecture/Programming/Java/AlgorithmX

D KnuthのアルゴリズムXのJava実装です。Sudoku用です。

<pre>
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Iterator;
import java.util.Stack;

public class AlgorithmX {
	class Cell {
		Cell up, down, left, right;
		Header top;
		Object value = null;

		Cell() {
		}

		Cell(Object v) {
			value = v;
			left = right = this;
		}
	}

	class Header extends Cell {
		String label = null;
		int size = 0;

		Header(String l) {
			label = l;
			top = this;
			up = down = left = right = this;
		}
	}

	/**
	 * @author Masanori Arita
	 */
	class ExactCoverMatrix {
		Header head = new Header(null);

		Stack<Cell> stack = new Stack<Cell>();

		int colSize;

		/**
		 * Matrix for Exact Cover （行が集合の数、列が要素の数）における列成分を定義する。
		 * 
		 * @param labels
		 *            label for columns
		 */
		void initializeHeaders(String[] labels) {
			colSize = labels.length;
			for (int i = 0; i < colSize; i++) {
				Header h = new Header(labels[i]);
				h.right = head;
				h.left = head.left;
				head.left.right = h;
				head.left = h;
			}
		}

		/**
		 * 文字配列を受け取り、該当する列にセルを作成する。 受け取る配列はinitializeHeadersと同じ順序とする。
		 * 
		 * @param labels
		 *            文字配列
		 * @param values
		 *            相当するセルの値
		 */
		void addRow(String[] labels, Object[] values) {
			Cell first = null, last = null;
			Header h = (Header) head.right;
			for (int i = 0; i < labels.length; i++) {
				String l = labels[i];
				while (!h.label.equals(l)) {
					h = (Header) h.right;
					if (h == head) {
						System.err.println("No row of name: " + l);
						i++;
						break;
					}
				}
				// セルを挿入
				Cell tmp = new Cell(values[i]);
				tmp.top = h;
				h.size++;
				// 横のリンク
				if (first == null)
					first = last = tmp;
				else {
					last.right = tmp;
					tmp.left = last;
					last = tmp;
				}
				// 縦のリンク
				Cell above = h.up;
				above.down = h.up = tmp;
				tmp.up = above;
				tmp.down = h;
			}
			// 横のリンクを完成させる
			last.right = first;
			first.left = last;
		}

		/**
		 * Brute forceで探索する部分
		 * 
		 * @param k
		 *            探索の深さ。このプログラムでは使用せず。
		 */
		void search(int k) {
			if (head.right == head) {
				printSudokuSolution();
				return;
			}
			Header c = chooseColumn();
			coverColumn(c);
			for (Cell r = c.down; r != c; r = r.down) {
				stack.push(r);
				for (Cell j = r.right; j != r; j = j.right)
					coverColumn(j.top);
				search(k + 1);
				stack.pop();
				for (Cell j = r.left; j != r; j = j.left)
					uncoverColumn(j.top);
			}
			uncoverColumn(c.top);
		}

		void coverColumn(Header c) {
			colSize--;
			c.right.left = c.left;
			c.left.right = c.right;
			for (Cell i = c.down; i != c; i = i.down)
				for (Cell j = i.right; j != i; j = j.right) {
					j.down.up = j.up;
					j.up.down = j.down;
					j.top.size--;
				}
		}

		void uncoverColumn(Header c) {
			colSize++;
			for (Cell i = c.up; i != c; i = i.up)
				for (Cell j = i.left; j != i; j = j.left) {
					j.top.size++;
					j.down.up = j;
					j.up.down = j;
				}
			c.right.left = c;
			c.left.right = c;
		}

		/**
		 * マトリクス中で一番要素数の少ない列を返す
		 * 
		 * @return
		 */
		Header chooseColumn() {
			Header maxCol = (Header) head.right;
			Header h = maxCol;
			for (int i = 1; i < colSize; i++) {
				h = (Header) h.right;
				if (h.size < maxCol.size)
					maxCol = h;
			}
			return maxCol;
		}

		void printSolution() {
			for (Iterator<Cell> i = stack.iterator(); i.hasNext();) {
				Cell c = i.next();
				System.out.print(c.top.label + " ");
				for (Cell j = c.right; j != c; j = j.right)
					System.out.print(j.top.label + " ");
				System.out.println();
			}
		}

		void printSudokuSolution() {
			int[][] answer = new int[9][9];
			for (Iterator<Cell> I = stack.iterator(); I.hasNext();) {
				Cell c = I.next();
				while (!c.top.label.startsWith("S"))
					c = c.right;
				int i = c.top.label.charAt(1) - '0' - 1;
				int j = c.top.label.charAt(2) - '0' - 1;
				int n = c.right.top.label.charAt(2) - '0';
				answer[i][j] = n;
			}
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++)
					System.out.print(answer[i][j] + " ");
				System.out.println();
			}
		}

	}

	/*
	 * 数独読み込みルーチン
	 */
	public int[][] readSudoku(String file) {
		// スペース区切りの9x9数を読み込んで9x9の二次元配列を返す
		int[][] sudoku = new int[9][9];
		try {
			BufferedReader br = new BufferedReader(new FileReader(file));
			String line;
			int row = 0;
			while (((line = br.readLine()) != null) && row < 9) {
				if (line.startsWith(";"))
					continue;
				String[] numbers = line.split(" ");
				for (int i = 0; i < 9; i++)
					sudoku[row][i] = Integer.parseInt(numbers[i]);
				row++;
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
		return sudoku;
	}

	void solveSudoku(int[][] sudoku) {
		String[] label = new String[] { "S", "C", "R", "B" };
		String[] S = new String[9 * 9 * 4];
		for (int i = 0; i < 4; i++)
			for (int j = 0; j < 9; j++)
				for (int k = 0; k < 9; k++)
					S[i * 9 * 9 + j * 9 + k] = (label[i] + (j + 1)) + (k + 1);
		ExactCoverMatrix mat = new ExactCoverMatrix();
		mat.initializeHeaders(S);
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++) {
				if (sudoku[i][j] == 0) {
					for (int n = 1; n <= 9; n++) {
						mat.addRow(new String[] { ("S" + (i + 1) + (j + 1)),
								("C" + (j + 1) + n), ("R" + (i + 1) + n),
								("B" + ((i / 3) * 3 + (j / 3) + 1) + n) },
								new Object[] { null, null, null, null });
					}
				} else {
					int n = sudoku[i][j];
					mat.addRow(new String[] { ("S" + (i + 1) + (j + 1)),
							("C" + (j + 1) + n), ("R" + (i + 1) + n),
							("B" + ((i / 3) * 3 + (j / 3) + 1) + n) },
							new Object[] { null, null, null, null });
				}
			}
		mat.search(0);
	}

	static public void main(String[] args) {
		AlgorithmX dl = new AlgorithmX();
		int[][] sudoku = dl.readSudoku("c:/home/sudokuSample.txt");
		dl.solveSudoku(sudoku);
	}
}
</pre>