package com.feng.testproject.algorithm;
import java.util.*;
public class L37 {
public static void main(String[] args) {
char[][] board = {{'.','.','.','2','.','.','.','6','3'},
{'3','.','.','.','.','5','4','.','1'},
{'.','.','1','.','.','3','9','8','.'},
{'.','.','.','.','.','.','.','9','.'},
{'.','.','.','5','3','8','.','.','.'},
{'.','3','.','.','.','.','.','.','.'},
{'.','2','6','3','.','.','5','.','.'},
{'5','.','3','7','.','.','.','.','8'},
{'4','7','.','.','.','1','.','.','.'}};
solveSudoku(board);
sout(board, board.length);
}
public static void solveSudoku(char[][] board) {
int length = board.length;
Table[][] table = new Table[length][length];
PriorityQueue queue = new PriorityQueue<>();
boolean flag = true;
while (flag) {
flag = false;
queue.clear();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < length; j++) {
if (board[i][j] != '.') {
char c = board[i][j];
table[i][j] = new Table(c);
} else {
Set all = getAll();
findValues(board, length, i, j, all);
if (all.size() == 0) {
sout(board, length);
return;
} else if (all.size() == 1) {
board[i][j] = all.iterator().next();
flag = true;
} else {
table[i][j] = new Table(all,i,j);
queue.add(table[i][j]);
}
}
}
}
}
sout(board,length);
System.out.println("--------------------------");
diedai(board, length, table, queue);
}
private static int diedai(char[][] board, int length, Table[][] table, PriorityQueue queue) {
boolean flag;
if (queue.size()>0) {
Table poll = queue.poll();
int x = poll.getI();
int y = poll.getJ();
Set set = poll.getSet();
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
Character next = iterator.next();
board[x][y] = next;
PriorityQueue queueTwo = new PriorityQueue<>();
flag = true;
boolean yiwai = false;
List list = new ArrayList<>();
while (flag) {
flag = false;
queueTwo.clear();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < length; j++) {
if (board[i][j] != '.') {
char c = board[i][j];
table[i][j] = new Table(c);
} else {
Set all = getAll();
findValues(board, length, i, j, all);
if (all.size() == 0) {
sout(board, length);
System.out.println("------------------------------------------------------");
flag = false;
yiwai = true;
break;
} else if (all.size() == 1) {
board[i][j] = all.iterator().next();
Table t = new Table(i,j);
list.add(t);
flag = true;
} else {
table[i][j] = new Table(all,i,j);
queueTwo.add(table[i][j]);
}
}
}
if (yiwai) {
break;
}
}
}
if (!yiwai && queueTwo.size() == 0) {
return 0;
} else if (!yiwai && queueTwo.size() > 0) {
int diedai = diedai(board, length, table, queueTwo);
if (diedai == 0) {
return diedai;
}
if (queueTwo.size() > 0) {
for (Table table1 : list) {
board[table1.getI()][table1.getJ()] = '.';
}
}
} else {
board[x][y] = '.';
for (Table table1 : list) {
board[table1.getI()][table1.getJ()] = '.';
}
}
}
}
return -1;
}
private static void sout(char[][] board, int length) {
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println("");
}
}
private static void findValues(char[][] board, int length, int i, int j, Set all) {
for (int k = 0; k < length; k++) {
if (board[i][k] != '.') {
all.remove(board[i][k]);
}
if (board[k][j] != '.') {
all.remove(board[k][j]);
}
}
for (int k = i/3*3; k < i/3*3+3; k++) {
for (int l = j/3*3; l < j/3*3+3; l++) {
if (board[k][l] != '.') {
all.remove(board[k][l]);
}
}
}
}
private static Set getAll() {
Set all = new HashSet<>();
all.add('1');
all.add('2');
all.add('3');
all.add('4');
all.add('5');
all.add('6');
all.add('7');
all.add('8');
all.add('9');
return all;
}
static class Table implements Comparable{
private char value;
private Set set = new HashSet<>();
private int length;
private int i;
private int j;
public Table(Set set, int i, int j) {
this.set = set;
this.i = i;
this.j = j;
this.length = set.size();
}
public Table(int i, int j) {
this.i = i;
this.j = j;
}
public int getI() {
return i;
}
public void setI(int i) {
this.i = i;
}
public int getJ() {
return j;
}
public void setJ(int j) {
this.j = j;
}
public Table(Set set) {
this.set = set;
this.length = set.size();
}
public Table(char value) {
this.value = value;
}
public void add(char c) {
set.add(c);
length = set.size();
}
public void remove(char c) {
set.remove(c);
length = set.size();
}
public char getValue() {
return value;
}
public void setValue(char value) {
this.value = value;
}
public Set getSet() {
return set;
}
public void setSet(Set set) {
this.set = set;
this.length = set.size();
}
public int getLength() {
return length;
}
public void setLength(int length) {
this.length = length;
}
@Override
public int compareTo(Table o) {
return this.getLength() - o.getLength();
}
}
}
总结
我认为问题的难点在于 怎么表示不确定的点的值，这里我引入了内部类来做，为了减少遍历次数对内部类做了排数，按照可能的值的个数从小到大排列。
问题：
思维上的：使用Java做业务过多，导致表示一个值的时候更喜欢key，value形式，对于使用数组下标这种隐式的表示一中含义不能想到，以后要多注意
回溯算法在做的时候要考虑 回溯时是否完整的将做过的修改已经改回去了
位运算需要在学习一下
