用java解数独
其实也就是用到了回溯算法。
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
首先定义一个Sudoku类，用来保存和处理9*9的数组
import java.util.ArrayList;
import java.util.List;
/**
* Created shellingford on 2017/3/4.
*/
public class Sudoku {
private int[][] src;
private List<IRule> ruleList = new ArrayList<>();
private List<Result> resultList = new ArrayList<>();
private boolean findOne = true;
/**
* 判断是否符合规则
* @param x
* @param y
* @return
*/
private boolean check(int x,int y){
if(ruleList.size()>0){
for (IRule iRule : ruleList) {
boolean flag=iRule.check(src,x,y);
if(flag==false){
return false;
}
}
}
return true;
}
public Result backTrace(int x,int y){
if(x==8 && y==9){
//已经解出答案
Result result = new Result(src,x,y);
resultList.add(result);
return result;
}
//行末换行
if(y==9){
x++;
y=0;
}
if(src[x][y]==0){
//该值可以替换
for (int i = 1; i <=9 ; i++) {
//先暂时赋值
src[x][y] = i;
if(check(x,y)){
//如果没有问题
Result result = backTrace(x,y+1);
if(result.isSuccess() && findOne){
//只要找一个答案 并且已经找到
return result;
}
}
src[x][y]=0;
}
//已经替换完所有的可能了，还是没有正确的
return new Result(x,y);
}else{
//固定值，不能变换
Result result = backTrace(x,y+1);
return result;
}
}
public List<Result> getResultList() {
return resultList;
}
public void addRule(IRule rule){
ruleList.add(rule);
}
public void clearRule(){
ruleList.clear();
}
public Sudoku(String[] str){
int[][] x=new int[9][9];
for (int i = 0; i <9 ; i++) {
for (int j = 0; j <9 ; j++) {
x[i][j]=Integer.parseInt(str[i].charAt(j)+"");
}
}
src=x;
}
public Sudoku(int[][] x){
src=x;
}
public void display(){
for (int i = 0; i <src.length ; i++) {
for (int j = 0; j <src[i].length ; j++) {
System.out.print(src[i][j]);
}
System.out.println();
}
}
public boolean isFindOne() {
return findOne;
}
public void setFindOne(boolean findOne) {
this.findOne = findOne;
}
}
可以看到主要的解题算法在backTrace函数中，通过不断尝试，正确的则继续调用自身，错误的则返回上层尝试其他数值。
check方法用来判断当前数组是否符合规范，这里为了扩展一些其他特殊数独规则，使用了接口，把判断依据放入了ruleList里面。
接着看一下规则接口
/**
* Created shellingford on 2017/3/4.
* 数独规则接口
*/
public interface IRule {
public boolean check(final int[][] src,int x,int y);
}
只是简单的定义入参，和判断返回boolean值
接着是基础的规则，横竖判断不能重复
import java.util.ArrayList;
import java.util.List;
/**
* Created shellingford on 2017/3/4.
* 行列规则
*/
public class BaseSudokuRule implements IRule {
private final boolean isX;
public BaseSudokuRule(boolean isX) {
this.isX = isX;
}
@Override
public boolean check(int[][] src, int x, int y) {
if(isX){
//判断X
List<Integer> list = new ArrayList<>(9);
for (int i = 0; i <9 ; i++) {
if(src[i][y]!=0){
Integer one = new Integer(src[i][y]);
if(list.contains(one)){
return false;
}
list.add(one);
}
}
}else{
//判断Y
List<Integer> list = new ArrayList<>(9);
for (int i = 0; i <9 ; i++) {
if(src[x][i]!=0){
Integer one = new Integer(src[x][i]);
if(list.contains(one)){
return false;
}
list.add(one);
}
}
}
return true;
}
}
还有3*3不能重复规则
import java.util.ArrayList;
import java.util.List;
/**
* Created shellingford on 2017/3/4.
* 3*3规则
*/
public class SubSudokuRule implements IRule{
@Override
public boolean check(int[][] src, int x, int y) {
int startX=x/3;
int startY=y/3;
List<Integer> list = new ArrayList<>(9);
for (int i = startX*3; i <startX*3+3 ; i++) {
for (int j = startY*3; j <startY*3+3 ; j++) {
if(src[i][j]!=0){
Integer one = new Integer(src[i][j]);
if(list.contains(one)){
return false;
}
list.add(one);
}
}
}
return true;
}
}
以及保存正确结果的返回对象
/**
* Created shellingford on 2017/3/4.
* 数独解析结果
*/
public class Result {
private int x;
private int y;
private int[][] src;
private boolean success=true;
public boolean hasNext(){
if(x==8 && y>=9){
return false;
}
return true;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public int[][] getSrc() {
return src;
}
public boolean isSuccess() {
return success;
}
public void display(){
if(src!=null){
for (int i = 0; i <src.length ; i++) {
for (int j = 0; j <src[i].length ; j++) {
System.out.print(src[i][j]);
}
System.out.println();
}
}
}
public Result(int x,int y){
this(null,x,y);
}
public Result(int[][] data,int x,int y){
this.x=x;
this.y=y;
if(data==null){
success=false;
}else{
src=new int[9][9];
for (int i = 0; i <9 ; i++) {
for (int j = 0; j <9 ; j++) {
src[i][j]=data[i][j];
}
}
}
}
}
可以额外增加规则，例如与之上下左右相邻的总和等于多少的规则
import java.util.ArrayList;
import java.util.List;
/**
* Created shellingford on 2017/3/4.
* 相邻四格之和规则
*/
public class SumRule implements IRule{
private final int destX;
private final int destY;
private final int sum;
public SumRule(int destX, int destY, int sum) {
this.destX = destX;
this.destY = destY;
this.sum = sum;
}
@Override
public boolean check(int[][] src, int x, int y) {
//首先判断是否相邻
boolean needCheck=false;
if(destX == x && destY==y){
needCheck=true;
}else if(destX==x){
if(destY==y-1 || destY==y+1){
needCheck=true;
}
}else if(destY==y){
if(destX==x-1 || destX==x+1){
needCheck=true;
}
}
if(needCheck==false){
//这里是因为变动数据并不影响这个规则，所以返回检查通过
return true;
}
List<Integer> list = new ArrayList<>();
list.add(src[destX-1][destY]);
list.add(src[destX+1][destY]);
list.add(src[destX][destY]);
list.add(src[destX][destY+1]);
list.add(src[destX][destY-1]);
int sum=0;
for (Integer integer : list) {
if(integer==0){
//这里是因为有存在未填充的数据，所以不用检查
return true;
}
sum=sum+integer;
}
return this.sum==sum;
}
}
最后是main函数调用
import java.util.List;
/**
* Created shellingford on 2017/3/4.
*/
public class Demo {
public static void main(String[] args) {
String x[]={
"001000500",
"020000010",
"500000009",
"000000000",
"000000000",
"000000000",
"900000004",
"010000060",
"004000100"
};
Sudoku sudoku = new Sudoku(x);
//构造基础规则
BaseSudokuRule xRule = new BaseSudokuRule(true);
BaseSudokuRule yRule = new BaseSudokuRule(false);
sudoku.addRule(xRule);
sudoku.addRule(yRule);
SubSudokuRule subSudokuRule = new SubSudokuRule();
sudoku.addRule(subSudokuRule);
//增加特殊规则
sudoku.addRule(new SumRule(1,4,17));
sudoku.addRule(new SumRule(2,2,29));
sudoku.addRule(new SumRule(2,6,22));
sudoku.addRule(new SumRule(4,1,34));
sudoku.addRule(new SumRule(4,4,23));
sudoku.addRule(new SumRule(4,7,20));
sudoku.addRule(new SumRule(6,2,22));
sudoku.addRule(new SumRule(6,6,29));
sudoku.addRule(new SumRule(7,4,33));
sudoku.backTrace(0,0);
List<Result> list = sudoku.getResultList();
for (Result result : list) {
if(result.isSuccess()){
System.out.println("============");
result.display();
System.out.println("============");
}
}
}
}
CPA学习网
商学院
名人名言
论文服务