生成数独矩阵--《编程之美》1.15节

生成数独矩阵，定义参见《编程之美》第1.15节.
程序可以直接运行

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

/**
 * 生成数独矩阵，定义参见《编程之美》第1.15节.
 * 
 * @author LC
 */
public class Sudoku {
	Cell g[][] = new Cell[9][9];

	public Sudoku() {
		for (int i = 0; i < g.length; i++) {
			for (int j = 0; j < g[i].length; j++) {
				g[i][j] = new Cell();
			}
		}
	}

	//检查整个矩阵是否满足数独的条件，不允许有空格
	boolean check() {
		//检查每行是否数字不重复
		Set<Integer> s = new TreeSet<>();

		//检查每个小块是否数字不重复
		for (int r = 0; r < 3; r++) {
			for (int c = 0; c < 3; c++) {
				int rShift = r * 3;
				int cShift = c * 3;
				s.clear();

				for (int i = 0; i < 3; i++) {
					for (int j = 0; j < 3; j++) {
						Cell cell = g[rShift + i][cShift + j];
						if (!cell.isValid() || s.contains(cell.number)) {
							System.out.println("error in block (" + r + ", "
									+ c + ") with duplicated " + cell.number);

							return false;
						} else
							s.add(cell.number);

					}
				}

			}
		}

		for (int i = 0; i < g.length; i++) {
			s.clear();
			for (int j = 0; j < g[i].length; j++) {
				Cell cell = g[i][j];
				if (!cell.isValid() || s.contains(cell.number)) {
					System.out.println("error in row " + i
							+ " with duplicated " + cell.number);
					return false;
				} else
					s.add(cell.number);

			}

		}

		//检查每列是否数字不重复
		for (int j = 0; j < g[0].length; j++) {
			s.clear();
			for (int i = 0; i < g.length; i++) {
				Cell cell = g[i][j];
				if (!cell.isValid() || s.contains(cell.number)) {
					System.out.println("error in column " + j
							+ " with duplicated " + cell.number);
					return false;
				} else
					s.add(cell.number);
			}

		}

		return true;

	}

	//检查整个矩阵是否满足数独的条件，允许有空格；该方法可以用于游戏中检测选手的输入是否有误
	boolean checkCurrent() {
		//检查每行是否数字不重复
		Set<Integer> s = new TreeSet<>();

		//检查每个小块是否数字不重复
		for (int r = 0; r < 3; r++) {
			for (int c = 0; c < 3; c++) {
				int rShift = r * 3;
				int cShift = c * 3;
				s.clear();

				for (int i = 0; i < 3; i++) {
					for (int j = 0; j < 3; j++) {
						Cell cell = g[rShift + i][cShift + j];
						if (!cell.isValid())
							continue;

						if (s.contains(cell.number)) {
							System.out.println("error in block (" + r + ", "
									+ c + ") with duplicated " + cell.number);

							return false;
						} else
							s.add(cell.number);

					}
				}

			}
		}

		for (int i = 0; i < g.length; i++) {
			s.clear();
			for (int j = 0; j < g[i].length; j++) {
				Cell cell = g[i][j];
				if (!cell.isValid())
					continue;

				if (s.contains(cell.number)) {
					System.out.println("error in row " + i
							+ " with duplicated " + cell.number);
					return false;
				} else
					s.add(cell.number);

			}

		}

		//检查每列是否数字不重复
		for (int j = 0; j < g[0].length; j++) {
			s.clear();
			for (int i = 0; i < g.length; i++) {
				Cell cell = g[i][j];
				if (!cell.isValid())
					continue;

				if (s.contains(cell.number)) {
					System.out.println("error in column " + j
							+ " with duplicated " + cell.number);
					return false;
				} else
					s.add(cell.number);
			}

		}

		return true;

	}

	//生成合法的数独矩阵，尝试性的生成，选取数字用了随机化方法
	boolean generateValidMatrix() {
		int rollBackCount = 0;

		int i = 0;
		int j = 0;
		//生成数独矩阵，每个单元逐次生成，顺序为从左到右，从上到下
		while (i < g.length) {
			int rShift = i / 3 * 3;
			int cShift = j / 3 * 3;

			Cell cell = g[i][j];

			//剔除该列已有的数字
			for (int r = 0; r < i; r++) {
				cell.alternativeNumbers.remove((Integer) g[r][j].number);
			}

			//剔除该行已有的数字
			for (int c = 0; c < j; c++) {
				cell.alternativeNumbers.remove((Integer) g[i][c].number);
			}

			//剔除该块已有的数字
			for (int r = rShift; r <= i; r++) {
				for (int c = cShift; c < cShift + 3; c++) {
					cell.alternativeNumbers.remove((Integer) g[r][c].number);
				}
			}
			if (cell.hasAlternativeNumber()) {
				cell.pickAnAlternativeNumberRandomlyAndRemoveIt();//这一步中已经将当选的数字从可选数字列表中删除了
				//转到下一个要处理的cell
				j++;
				if (j == g[0].length) {
					j = 0;
					i++;
				}
			} else {//回退
				rollBackCount++;
				cell.init();
				//找到上一个cell
				if (j > 0) {
					--j;
				} else {
					--i;
					j = g[0].length - 1;
				}

				Cell lastCell = g[i][j];//没这一步也行
				lastCell.number = 0;

			}
		}

		System.out.println("生成该数独矩阵时回退了" + rollBackCount + "步");
		return true;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < g.length; i++) {
			for (int j = 0; j < g[i].length; j++) {
				sb.append(g[i][j].toString());
				if (j % 3 == 2)
					sb.append(' ');
			}
			sb.append('\n');
			if (i % 3 == 2 && i != g.length - 1)
				sb.append('\n');
		}

		return sb.toString();
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Sudoku s = new Sudoku();
		s.generateValidMatrix();
		System.out.println(s);
		boolean b = s.check();

		System.out.println("生成的数独矩阵是否通过了检测?  " + b);
	}
}

//数独的一个单元格
class Cell {
	int number = 0;//该单元中的数字，为0表示为空， 有效数字为1~9
	List<Integer> alternativeNumbers;//当前可选的数字, 生成数独矩阵时使用

	void init() {
		number = 0;
		alternativeNumbers = new ArrayList<>();//当前可选的数字
		for (int i = 1; i <= 9; i++) {
			alternativeNumbers.add(i);

		}
	}

	public Cell() {
		init();
	}

	/**
	 * @return 该单元 是否还有满足数独规则的数字可用
	 */
	boolean hasAlternativeNumber() {
		return alternativeNumbers.size() > 0;
	}

	/**
	 * 随机选取一个满足数独规则的数字作为该单元的数字，并将其从可选数字集合中剔除
	 */
	void pickAnAlternativeNumberRandomlyAndRemoveIt() {
		int idx = (int) (Math.random() * alternativeNumbers.size());
		number = alternativeNumbers.get(idx);
		alternativeNumbers.remove(idx);
	}

	@Override
	public String toString() {
		//		System.out.println(number);
		return number <= 0 ? " " : String.valueOf(number);
	}

	/**
	 * @return 当前单元中是否有有效的数字
	 */
	boolean isValid() {
		return number > 0 && number < 10;
	}
}