## 数独解题程序 原

悠悠然然

``````public class Sudoku {
int[][] data = new int[9][9];//填好的数字
List<Integer>[][] dataLeft = new ArrayList[9][9];//每个位置可能的数字

public Sudoku(int data[][]) {
this();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (data[i][j] != 0) {
putNumber(i, j, data[i][j]);
}
}
}
}

public Sudoku() {
//初始化数据
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
data[i][j] = 0;
dataLeft[i][j] = new ArrayList<Integer>();
for (int k = 1; k <= 9; k++) {
}
}
}
}

public void putNumber(int x, int y, Integer n) {
data[x][y] = n;//此点位置赋值
dataLeft[x][y].clear();//可能数字清空;
//清理水平和竖直
for (int i = 0; i < 9; i++) {
if (i != x) {
dataLeft[i][y].remove(n);
}
if (i != y) {
dataLeft[x][i].remove(n);
}
}
//清理小空格
int startX = x / 3;
int startY = y / 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i + startX * 3 != x && j + startY * 3 != y) {
dataLeft[i + startX * 3][j + startY * 3].remove(n);
}
}
}
}

public void compute() {
int count = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (dataLeft[i][j].size() == 1) {
putNumber(i, j, dataLeft[i][j].get(0));
count++;
}
}
}
if (count == 0) {
System.out.println("Compute completed.");
} else {
compute();
}
}

public void print() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.printf("%d ", data[i][j]);
}
System.out.println();
}
}
}``````

``````public class Test {
public static void main(String[] args) {
int[][]data={
{6,0,5,0,0,2,0,0,8},
{0,4,0,3,8,0,0,5,0},
{3,0,0,0,6,0,7,0,2},
{0,5,0,0,0,3,0,4,0},
{0,6,1,0,0,4,8,7,0},
{0,2,0,0,7,8,0,6,0},
{1,0,9,0,2,0,0,0,4},
{0,7,0,0,4,1,0,2,0},
{2,0,0,9,0,0,5,0,7}};
Sudoku sudoku=new Sudoku(data);
sudoku.compute();
sudoku.print();
}
}``````

``````Compute completed.
6 9 5 7 1 2 4 3 8
7 4 2 3 8 9 1 5 6
3 1 8 4 6 5 7 9 2
8 5 7 6 9 3 2 4 1
9 6 1 2 5 4 8 7 3
4 2 3 1 7 8 9 6 5
1 3 9 5 2 7 6 8 4
5 7 6 8 4 1 3 2 9
2 8 4 9 3 6 5 1 7``````

``````public class Test1 {
public static void main(String[] args) {
int[][]data={
{0,0,0,0,0,8,1,0,0},
{7,0,0,9,0,0,0,0,6},
{0,0,8,0,3,0,7,0,0},
{4,0,0,0,0,9,3,0,0},
{8,0,0,0,7,0,0,0,5},
{0,0,3,0,2,5,0,0,9},
{0,0,4,0,6,0,2,0,0},
{5,0,0,0,0,2,0,0,7},
{0,0,2,1,0,0,0,0,0}};
Sudoku sudoku=new Sudoku(data);
sudoku.compute();
sudoku.print();
}
}``````

``````Compute completed.
0 0 0 0 0 8 1 0 0
7 0 0 9 0 0 0 0 6
0 0 8 0 3 0 7 0 0
4 0 0 0 0 9 3 0 0
8 0 0 0 7 0 0 0 5
0 0 3 0 2 5 0 0 9
0 0 4 0 6 0 2 0 0
5 0 0 0 0 2 0 0 7
0 0 2 1 0 0 0 0 0``````

``````public class Sudoku {
int[][] data = new int[9][9];//填好的数字
List<Integer>[][] dataLeft = new ArrayList[9][9];//每个位置可能的数字

public Sudoku(int data[][]) {
this();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (data[i][j] != 0) {
putNumber(i, j, data[i][j]);
}
}
}
}

public Sudoku() {
//初始化数据
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
data[i][j] = 0;
dataLeft[i][j] = new ArrayList<Integer>();
for (int k = 1; k <= 9; k++) {
}
}
}
}

public void putNumber(int x, int y, Integer n) {
data[x][y] = n;//此点位置赋值
dataLeft[x][y].clear();//可能数字清空;
//清理水平和竖直
for (int i = 0; i < 9; i++) {
if (i != x) {
dataLeft[i][y].remove(n);
}
if (i != y) {
dataLeft[x][i].remove(n);
}
}
//清理小空格
int startX = x / 3;
int startY = y / 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i + startX * 3 != x && j + startY * 3 != y) {
dataLeft[i + startX * 3][j + startY * 3].remove(n);
}
}
}
}

public void compute() {
int count = 0;
//计算某个位置只有一个数字的情况
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (dataLeft[i][j].size() == 1) {//如果只有一个可能的数字，那就是它了
putNumber(i, j, dataLeft[i][j].get(0));
count++;
}
}
}
if (count == 0) {//如果没有唯一一个数的，则查找只出现过一次的
count += computeRow();
count += computeColumn();
count += computeBox();
}

if (count > 0) {
compute();
}
}

public int computeRow() {
int c = 0;
for (int i = 0; i < 9; i++) {//行
int[] count = new int[9];
for (int j = 0; j < 9; j++) {//列
for (int num : dataLeft[i][j]) {
count[num - 1]++;//统计个数
}
}
for (int k = 0; k < 9; k++) {
if (count[k] == 1) {//如果区域内的某个数字可能次数为1
for (int j = 0; j < 9; j++) {
if (dataLeft[i][j].contains(k + 1)) {
putNumber(i, j, k + 1);
c++;
}
}
}
}
}
return c;
}

public int computeBox() {
int c = 0;
for (int dx = 0; dx < 3; dx++) {
for (int dy = 0; dy < 3; dy++) {
//9个小格子
int[] count = new int[9];
List<Point>[] points = new ArrayList[9];
for (int i = 0; i < 9; i++) {
points[i] = new ArrayList<Point>();
}
for (int i = 0; i < 3; i++) {//行
for (int j = 0; j < 3; j++) {//列
for (int num : dataLeft[dx * 3 + i][dy * 3 + j]) {
count[num - 1]++;//统计个数
points[num - 1].add(new Point(dx * 3 + i, dy * 3 + j));
}
}
}
for (int k = 0; k < 9; k++) {
if (count[k] == 0) {//如果没有

} else if (count[k] == 1) {//如果区域内的某个数字可能次数为1
putNumber(points[k].get(0).x, points[k].get(0).y, k + 1);
} else {//如果出现次数大于1
Point point = points[k].get(0);
boolean sameRow = true;
boolean sameColumn = true;
for (int i = 1; i < points[k].size(); i++) {
Point p = points[k].get(i);
if (p.x != point.x) {
sameRow = false;
}
if (points[k].get(i).y != point.y) {
sameColumn = false;
}
}
if (sameRow) {// 且在一行上，则可以进行区块排除
cleanRow(point.x, dy, k + 1);
}
if (sameColumn) {// 且在一列上，则可以进行区块排除
cleanColumn(dx, point.y, k + 1);
}
}
}
}
}

return c;
}

private void cleanColumn(int dx, int y, Integer n) {
for (int i = 0; i < 3; i++) {
if (i != dx) {
for (int j = 0; j < 3; j++) {
dataLeft[i * 3 + j][y].remove(n);
}
}
}
}

private void cleanRow(int x, int dy, Integer n) {
for (int i = 0; i < 3; i++) {
if (i != dy) {
for (int j = 0; j < 3; j++) {
dataLeft[x][i * 3 + j].remove(n);
}
}
}
}
public int computeColumn() {
int c = 0;
for (int i = 0; i < 9; i++) {//行
int[] count = new int[9];
for (int j = 0; j < 9; j++) {//列
for (int num : dataLeft[j][i]) {
count[num - 1]++;//统计个数
}
}
for (int k = 0; k < 9; k++) {
if (count[k] == 1) {//如果区域内的某个数字可能次数为1
for (int j = 0; j < 9; j++) {
if (dataLeft[j][i].contains(k + 1)) {
putNumber(j, i, k + 1);
c++;
}
}
}
}
}
return c;
}

public void print() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.printf("%d ", data[i][j]);
}
System.out.println();
}
}

class Point {
private final int x;
private final int y;

Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}``````

``````Compute completed.
2 4 6 7 5 8 1 9 3
7 3 5 9 4 1 8 2 6
1 9 8 2 3 6 7 5 4
4 5 7 6 1 9 3 8 2
8 2 9 4 7 3 6 1 5
6 1 3 8 2 5 4 7 9
9 8 4 5 6 7 2 3 1
5 6 1 3 8 2 9 4 7
3 7 2 1 9 4 5 6 8``````

Yeah，居然算出了，这个大大超出我的意料。

a.基础摒除法

b.唯余解法

c.区块摒除法

### 评论(3)

#### 引用来自“夜色无边”的评论

Oh，欢迎分享~~

2010/03/02
4K
0

2010/03/02
2.9K
0

2014/11/27
437
1
JAVA代码—算法基础：数独问题（Sodoku Puzzles）

seagal890
2018/03/24
0
0

2016/12/14
87
0

WPF中的StaticResource和DynamicResource有什么区别？

javail
26分钟前
49
0
Day07继承中的面试题 答案

1. 每一个构造方法的第一条语句默认都是：super() Object类最顶层的父类。 class Zi extends Fu{ public int num = 20; public Zi(){ //super(); System.out.println("zi"); } 2.class Test......

Lao鹰
31分钟前
42
0

1 题目 Leetcode第18题,给定一个数组与一个target,找出数组中的四个数之和为target的不重复的所有四个数. 2 暴力 List<List<Integer>> result = new ArrayList<>();if (nums.length == 4 &......

Blueeeeeee
41分钟前
54
0
git clone --mirror和git clone --bare有什么区别

git clone帮助页面上有关于--mirror ： 设置远程存储库的镜像。 这意味着--bare 。 但没有详细介绍--mirror克隆与--bare克隆--mirror不同。 #1楼 克隆将从远程服务器复制参考，并将其填充到名...

57分钟前
72
0

53
0