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

编程技术  /  houtizong 发布于 3年前   131

生成数独矩阵，定义参见《编程之美》第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;} elses.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;} elses.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;} elses.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;} elses.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;} elses.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;} elses.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();//这一步中已经将当选的数字从可选数字列表中删除了//转到下一个要处理的cellj++;if (j == g[0].length) {j = 0;i++;}} else {//回退rollBackCount++;cell.init();//找到上一个cellif (j > 0) {--j;} else {--i;j = g[0].length - 1;}Cell lastCell = g[i][j];//没这一步也行lastCell.number = 0;}}System.out.println("生成该数独矩阵时回退了" + rollBackCount + "步");return true;}@Overridepublic 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~9List<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);}@Overridepublic String toString() {//System.out.println(number);return number <= 0 ? " " : String.valueOf(number);}/** * @return 当前单元中是否有有效的数字 */boolean isValid() {return number > 0 && number < 10;}}