?package test;
import java.util.LinkedList;
import java.util.Random;
/**
* 自动获取数独
* @author huangr 2013.02.19
*/
public class ShuDu {
public static void main(String []args){
ShuDu sd = new ShuDu();
sd.initShuDu();
sd.startShuDu(1);
}
int length;//长度
int currPs;//当前正在处理的位置
byte[] num = null;//结果
byte[] ansPs = null;//可用解在解集合中的位置
byte[][] ansVal = null;//可用解集合
Random rd = new Random();
public ShuDu(){
length = 9;
}
/**
* 初始化数独
*/
public void initShuDu(){
//初始化结果
if(num==null){
num = new byte[length*length];
}
ansPs = new byte[length*length];
ansVal = new byte[length*length][length];
currPs = 0;
//初始化赋值
for(int i=0;i
num[i] = 0;
ansPs[i] = 0;
for(int j=0;j ansVal[i][j] = 0;
}
}
}
/**
* 开始进行数独
* @param count 需获取数独的个数,-1代表所有.
*/
public void startShuDu(int count){
//当前正在解的结果标记
int currCount = 0;
//循环获取结果的解
while(currCount < count || count == -1){
//若当前解的位置为0,则获取可用解集合
if(ansPs[currPs]==0){
getAns();
}
//获取当前可用解个数
int ans = getAnsCount();
//若当前位置为0并且解可用解为0,则视为无解,跳出循环结束.
if(currPs==0&;&;ans==0){
break;
}else if(ansPs[currPs]==ans||ans==0){ //若当前解位置为可用解的个数或可用解为0,则返回上一个位置的下一个可用解重新开始
num[currPs] = 0;
ansPs[currPs] = 0;
currPs--;
continue;
}else{ //解可用,赋值
setAns();
ansPs[currPs]++;
currPs++;
}
if(length*length==currPs){ //若当前位置进行到数独的最大值,打印获取的数独结果,手动返回上一个位置获取下一个不同的数独解.
outData();
currCount++;
currPs--;
num[currPs] = 0;
ansPs[currPs] = 0;
System.out.println("");
}
}
}
/**
* 获取当前位置的所有可用解
*/
public void getAns(){
//默认设置所有可用解
for(byte i=1;i ansVal[currPs][i-1] = i;
}
//当前位置在数组中的行
int beginR = currPs/length;
//当前位置
在数组中的列
int beginC = currPs%length;
for(int i=0;i //若当前行有数据则删除解集合中同样的解
if(num[beginR*length+i]!=0){
ansVal[currPs][num[beginR*length+i]-1] = 0;
}
//若当前列中有数据则删除解集合中同样的解
if(num[length*i+beginC]!=0){
ansVal[currPs][num[length*i+beginC]-1] = 0;
}
}
//小九宫的个数
int subBox = (int)Math.sqrt(length);
//小九宫位于第几行
int boxR = beginR/subBox;
//小九宫位于第几列
int boxC = beginC/subBox;
//循环判断九宫中的数据,若解集合中有则删除
for(int i=subBox*boxR; i for(int j=subBox*boxC; j if(num[i*length+j]!=0){
ansVal[currPs][num[i*length+j]-1] = 0;
}
}
}
//将备选答案随机调换位置
randomAns();
}
/**
* 获取当前位置的可用解个数
* @return 可用解个数
*/
public int getAnsCount(){
int count = 0;
for(int i=0;i if(ansVal[currPs][i]!=0){
count++;
}
}
return count;
}
/**
* 给当前位置赋值
*/
public void setAns(){
int ansCount = 0;
for(int i=0;i //可用解的位置必须为解位置集合的值
if(ansVal[currPs][i]!=0&;&;ansCount==ansPs[currPs]){
num[currPs] = ansVal[currPs][i];
break;
}else if(ansVal[currPs][i]!=0){
ansCount++;
}
}
}
/**
* 随机调换当前位置可用解在当前解集合中的位置
*/
public void randomAns(){
//将解集合赋值给linklist
LinkedList linkList = new LinkedList<>();
for(int i=0;i linkList.add(ansVal[currPs][i]);
}
//随机获取linklist长度之内的值,并赋值给解集合,然后删除赋值了的linklist的值
for(int i=length-1;i>=0;i--){
int rdNum = Math.abs(rd.nextInt())%linkList.size();
ansVal[currPs][i] = linkList.get(rdNum);
linkList.remove(rdNum);
}
}
/**
* 格式化输出
*/
public void outData() {
for (int i = 0; i < length * length; i++) {
if (i % length == 0) {
System.out.println();
}
System.out.print((num[i] != -1 ? num[i] : " ") + " ");
}
}
}