数独,求解

黄玉昆

本帖最后由江华于 2013-3-15 15:25 编辑

说明:
刚才在百度看到了数独,做了一回,有点没头绪了.于是我就想,能不能用程序来解数独

我这里想做的是求解数据的程序,不是数独程序

我试着写了一下,头绪比较乱,
(1,1)    (1,2) (1,3) | (1,4) (1,5) (1,6) | (1,7) (1,8) (1,9)
(2,1)    (2,2) (2,3) | (2,4) (2,5) (2,6) | (2,7) (2,8) (2,9)
(3,1)    (3,2) (3,3) | (3,4) (3,5) (3,6) | (3,7) (3,8) (3,9)
------------------------|---------------------------|-----------------------
(4,1)    (4,2) (4,3) | (4,4) (4,5) (4,6) | (4,7) (4,8) (4,9)
(5,1)    (5,2) (5,3) | (5,4) (5,5) (5,6) | (5,7) (5,8) (5,9)
(6,1)    (6,2) (6,3) | (6,4) (6,5) (6,6) | (6,7) (6,8) (6,9)
------------------------|---------------------------|-------------------------
(7,1)    (7,2) (7,3) | (7,4) (7,5) (7,6) | (7,7) (7,8) (7,9)
(8,1)    (8,2) (8,3) | (8,4) (8,5) (8,6) | (8,7) (8,8) (8,9)
(9,1)    (9,2) (9,3) | (9,4) (9,5) (9,6) | (9,7) (9,8) (9,9)

我是这么想的:
把上边列出的的每个坐标当成一个对象
如果这个对象是空值,
      那么它就是一个Map集合
         键值是坐标,内容是arraylist 数据集合,默认是 1~9
如果它有值,
      那么它就是一个数字

这个对象有一个方法,
当它的值从空值变成数字时,它就清除同一行中,其他8个空值对象的arraylist集合中对象的数字

江华 · 江华

只是一个初步的设想,还未完善,贴出来,大家一起想想

李易烜 · 李易烜

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;
}
}

复制代码

江华 · 江华

李易烜发表于 2013-3-15 12:27

你的这个类,设计的很好,采用了,
只是没有求解数独的方法.
不过这个,我来完善吧

江华 · 江华

根据楼上的这个类,我是这么设想解法的

每一个空白未填数据的位置都有一个候选名单

假设
第一行第一个是空,它的候选名单是 123456
而第一行第三个的值确定了,它就是3,那么第一个的候选名单只能是12456了,一次类推
应该可以求解出数独的值,
不知道行不行?

谁有更优化的方法说一下!

江华 · 江华

本帖最后由江华于 2013-3-15 18:29 编辑

这个是根据以上想法写的代码,
还未调试通过,先贴出来,大家看下
这是我找的一个数独的图片,和程序对照一下

/**
*
*/
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;
}
}
}

复制代码

江华 · 江华

好吧,我的代码有点重复了

江华 · 江华

什么是问题解决?
不能加过技术分以后,就不再讨论了!!!

李易烜 · 李易烜

呵呵我原来也做过这个的！

江华 · 江华

李易烜发表于 2013-3-15 23:04
呵呵我原来也做过这个的！

你做的那个源码能分享一下吗

帐号		自动登录	找回密码
密码			加入黑马

数独,求解

点评

评分

9 个回复

评分

点评

黑马骑士勋章