# 生成数独矩阵--《编程之美》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

}
}

}
}

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

}

}

//检查每列是否数字不重复
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
}

}

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

}
}

}
}

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

}

}

//检查每列是否数字不重复
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
}

}

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++) {

}
}

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;
}
}```

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊

《编程之美》读书笔记(七)：数独游戏解析 前言：说实话，所有游戏都是有一定规律可循的，只要掌握游
其实一直都很想写个数独的游戏，最近刚好看了《编程之美》，得到了一些启发。 　　好，这时第一

3、题目：能否快速找出一个数组（简单起见，数组中元素值各不一样）中的两个数字，让这两个数字之和