数独,求解 - 黑马程序员技术交流社区

import static java.util.Arrays.*;
public class Puzzler{
public static final int SIZE =9;
private boolean[][] fixed =new boolean[SIZE][SIZE];
private int[][] number =new int[SIZE][SIZE];
public Puzzler(){
}
public Puzzler(int[][] p){
setPuzzler(p);
}
/**
* 用一个二维数组去设置该数独
* 注意:这个二维数组应该只包含0~9中的数字,为0时表示该处留空
* 该方法假设p的数据是合法的,不对其进行任何检查
*/
public void setPuzzler(int[][] p){
for(int i=0;i<SIZE;i++)
for(int j=0;j<SIZE;j++){
if(p[i][j] ==0){
fixed[i][j] =false;
number[i][j] =0;
} else{
number[i][j] =p[i][j];
fixed[i][j] =true;
}
}
}
/**
* 清除
*/
public void clear(){
for(int n=0;n<SIZE;n++){
fill(fixed[n],false);
fill(number[n],0);
}
return;
}
/**
* 位置i,j是否固定,如果固定表示该处的数字不能更改
*/
public boolean isFixed(int i,int j){
return fixed[i][j];
}
/**
* 得到位置i,j处的数字
*/
public int getNumber(int i,int j){
return number[i][j];
}
/**
* 设置i,j处的数字.如果该处数字是固定的,将抛出异常
*/
public void setNumber(int i,int j,int num){
if(num<0||num>9) throw new IllegalArgumentException("number is out of 0~9 :"+num);
if(isFixed(i,j)) throw new IllegalStateException("puzzler("+i+","+j+") is fixed");
number[i][j] =num;
}
}

复制代码

/**
*
*/
package Gmae;
import static java.util.Arrays.*;
public class Puzzler
{
/**
* 这个类是参照李易烜代码,以下是他的链接
* http://bbs.itheima.com/space-uid-65776.html
* ----------------属性说明-------------
* 属性:
* 一个数独对应两个二维数组;
* 数组 boolean fixed[][] 表示这个数组是否是固定值,
* 数组int number[][]是数独中的各个数.(如果这个位置是空时,它的值是0)
* 方法:
* setPuzzler 把数独中原有的固定数赋值给属性数组.
* isFixed 判断坐标位置属性,是否可修改(是否是初始化参数)
* getNumber 获得坐标对应的数组内容
* setNumber 填充数据到指定位置.
*/
private boolean[][] fixed =new boolean[SIZE][SIZE];
private int[][] number =new int[SIZE][SIZE];
public Puzzler()
{
}
public Puzzler(int[][] p)
{
setPuzzler(p);
}
/**
* 用一个二维数组去设置该数独
* 注意:这个二维数组应该只包含0~9中的数字,为0时表示该处留空
* 该方法假设p的数据是合法的,不对其进行任何检查
*/
public void setPuzzler(int[][] p)
{
for(int i=0;i<SIZE;i++)
for(int j=0;j<SIZE;j++){
if(p[i][j] ==0){
fixed[i][j] =false;
number[i][j] =0;
} else{
number[i][j] =p[i][j];
fixed[i][j] =true;
}
}
}
/**
* 清除
*/
public void clear()
{
for(int n=0;n<SIZE;n++)
{
fill(fixed[n],false);
fill(number[n],0);
}
return;
}
/**
* 位置i,j是否固定,如果固定表示该处的数字不能更改
*/
public boolean isFixed(int i,int j)
{
return fixed[i][j];
}
/**
* 得到位置i,j处的数字
*/
public int getNumber(int i,int j){
return number[i][j];
}
/**
* 设置i,j处的数字.如果该处数字是固定的,将抛出异常
*/
public void setNumber(int i,int j,int num)
{
if(num<0||num>9) throw new IllegalArgumentException("number is out of 0~9 :"+num);
if(isFixed(i,j)) throw new IllegalStateException("puzzler("+i+","+j+") is fixed");
number[i][j] =num;
}
}
public JieShuDu
{
/**
* 思路:
* 每一个位置都有候选成员,当某一个位置的值确定以后,和这个位置想的位置的候选名单中就要清除这个数据.根据这一原则去写程序
* 添加候选名单,
* 剔除相关位置的某一数据
*
*/
public static final int SIZE =9;
private ArrayList[][] al =new ArrayList[SIZE][SIZE] ;
private boolean[][] alflexd =new boolean[SIZE][SIZE];
private int[][] sd= int[SIZE][SIZE];
private Puzzler djsd =new Puzzler(sd);
public static void main(String[] args)
{
//初始化数独
setShuDu();
//初始化求解数独资源
setCandidate(djsd);
//求解数独
while(over())
{
for(int i=1;i<=SIZE;i++)
for(int j=1;j<=SIZE;j++)
if alflexd[i][j]
remove(alflexd[i][j].get(0),i,j);
}
}
public static void setShuDu()
{
for(int i=1;i<=SIZE;i++)
for(int j=1;j<=SIZE;j++)
sd[i][j]=0;
sd[1][3]=8;
sd[1][4]=3;
sd[1][6]=9;
sd[1][7]=1;
sd[2][1]=9;
sd[2][5]=6;
sd[2][9]=4;
sd[3][3]=7;
sd[3][4]=5;
sd[3][6]=4;
sd[3][7]=8;
sd[4][2]=3;
sd[4][3]=6;
sd[4][7]=5;
sd[4][8]=4;
sd[5][3]=1;
sd[5][7]=6;
sd[6][2]=4;
sd[6][3]=2;
sd[6][7]=9;
sd[6][8]=7;
sd[7][3]=5;
sd[7][4]=9;
sd[7][6]=7;
sd[7][7]=3;
sd[8][1]=6;
sd[8][5]=1;
sd[8][9]=8;
sd[9][3]=4;
sd[9][4]=6;
sd[9][6]=8;
sd[9][7]=2;
}
/**
* 为数独中,未填写的位置,填写可以候选名单
*/
public static void remove(int num,int nrow,int ncol)
{
/**
* 同一行只允许存在一个数字,所以,移除同行其他的候选名单.
* */
for(int i=1;i<=SIZE ;i++)
if !alFixed[nrow][i]
{
al[nrow][i].contains(num);
if al[nrow][i].size=1
alFixed[nrow][i](nrow,i)=true;
}
/**
* 同一列只允许存在一个数字,所以,移除同列其他的候选名单.
* */
for(int i=1;i<=SIZE ;i++)
if !alFixed[i][ncol]
{
al[i][ncol].contains(num);
if al[i][ncol].size=1
alFixed[i][ncol]=true;
}
int nr= (int)nrow / 3;
int nc= (int)ncol / 3;
for(int i=nr*3+1 ;i<=nr*3+3;i++)
for(int ji=nc*3+1 ;j<=nc*3+3;j++)
if !alFixed[i][j]
{
al[i][j].contains(num);
if al[i][j].size=1
alFixed[i][j]=true;
}
}
public static boolean over()
{
for(int i=1 ;i<=SIZE;i++)
for(int j=1 ;j<=SIZE;j++)
if !alflexd[i][j]
return true;
}
/**
* 默认所有的空白地方都可以填写1~9,填充所有信息
* */
public void setCandidate(Puzzler pr)
{
for(int i=1;i<=SIZE;i++)
for(int j=1;j<=SIZE;j++)
if pr.isFixed(i,j)
alflexd[i][i]=true;
else
{
for(int num=1;num<=SIZE;num++)
al[i][j].add(num);
alflexd[i][j]=false;
}
}
}

复制代码