生成数独矩阵,定义参见《编程之美》第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;
}
}
分享到:
相关推荐
最近看别人玩数独游戏,了解了游戏规则后,编写了一个简洁高效的数独矩阵生成器,可任意设值矩阵阶数,算法简洁高效,欢迎大家下载
数独矩阵完成生成,显示,保存,功能,等功能,详情请见头文件内所有详细注释,当前版本不支持逆向计算,凡是正常生成的矩阵都是有具体参考,答案,由于可能根据你的设置不同,答案不唯一,但是会有个系统标准答案,...
数独游戏-少儿编程scratch项目源代码文件案例素材.zip
自写小数独游戏。 自写算法!mfc实现。
这是一个微信小程序项目源码,是经典怀旧的数独游戏, 数独游戏逻辑非常简单,能训练大脑和观察能力,适合新手入门参考学习。 相关指导教程请看作者发表的文章 ...
这是一个h5或小程序,是经典怀旧的数独游戏,是uniapp项目源码,用HBuilderX开发工具编写而成, 数独游戏逻辑非常简单,能训练大脑和观察能力,适合新手入门参考学习。 相关指导教程请看作者发表的文章 ...
回溯法解决数独问题-2.docx
数独入门-儿童数独游戏第级-二余法x.docx
花了30块银子到当当网上买了编程之美>>找到其中的章节,看完之后大失所望.其中的算法实现藏头露尾,寥寥几行.让人看的云里雾里.连类定义都没有给全. 这里只好自己用基拙挖掘法实现了一个完整的算法,现共享之.其核心...
数独游戏-c语言编写
数独题目-难度系数.pdf
python数独游戏-34-abs和round.ev4.rar
python数独游戏-33-了解高阶函数.ev4.rar
python数独游戏-35-体验高阶函数的思路分析.ev4.rar
matlab数独游戏-shudu.m 各位大师们 帮帮忙啊 怎么用matlab编一个九宫格的游戏啊 也就是数独游戏啊 急着用啊 做什么课程设计,小妹很不幸抽到这个题啦 有会的或者有现成的拜托发到邮箱啊 谢谢啊 835111816@...
matlab数独游戏-sudoku.m 各位大师们 帮帮忙啊 怎么用matlab编一个九宫格的游戏啊 也就是数独游戏啊 急着用啊 做什么课程设计,小妹很不幸抽到这个题啦 有会的或者有现成的拜托发到邮箱啊 谢谢啊 835111816@...
适合学生、团队,个人、教师等参考学习
找了半天没找到,就自己写了,一般迭代个100次就完了
解数独神器用于帮助你解决数独的难题,只要输入一个数独题,该工具就能自动给出解答,快速、高效,适合那些做数独题慢,又想提高速度的人。 使用C++开发,对于学习编程开发,算法,人工智能的人都有一定参考价值
数独游戏仅使用 Python 编程语言创建。该应用程序用户友好,可以轻松适应您的需求。该应用程序克隆了真实数独的实际机制,其目标是用数字填充 9 × 9 网格,以便每一列、行和组成网格的 9 个 3 × 3 子网格都包含从 ...