| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 10191 人关注过本帖
标题:[分享]数独的JAVA解法
只看楼主 加入收藏
Eastsun
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:32
帖 子:802
专家分:0
注 册:2006-12-14
  问题点数:0  回复次数:24   
[分享]数独的JAVA解法

本来想做个GUI版的数独游戏的,不过做到一半又不想做了.现在把数独求解部分的代码发出来:
数独的数据结构:


package sodoku.puzzler;

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


搜索更多相关主题的帖子: JAVA  解法  分享  
2007-06-23 13:27
Eastsun
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:32
帖 子:802
专家分:0
注 册:2006-12-14
  得分:0 

求解Sodoku Puzzler的工具类


package sodoku.puzzler;

/**
* 求解Sodoku Puzzler的工具类
* @author Eastsun
*/
public class Solver{
protected static final int SIZE = Puzzler.SIZE;
//避免生成该类实例
protected Solver(){
}
public static boolean solve(Puzzler p){
int[][] num =new int[SIZE][SIZE];
boolean[][] rFlags =new boolean[SIZE][SIZE+1],
cFlags =new boolean[SIZE][SIZE+1],
zFlags =new boolean[SIZE][SIZE+1];
for(int r=0;r<SIZE;r++)
for(int c=0;c<SIZE;c++)
if(p.isFixed(r,c)){
int t =p.getNumber(r,c);
num[r][c] =t;
rFlags[r][t] =true;
cFlags[c][t] =true;
zFlags[r/3*3+c/3][t] =true;
}

int r =0,c =0;

outLoop:
for(;;){//&#
if(p.isFixed(r,c)){
c ++;
if(c>=SIZE){
c =0;
r ++;
if(r>=SIZE) break outLoop;
}
continue outLoop;
} //&#if(p.isFixed())
int t =SIZE;
for(c++;;){//&#
if(t>=SIZE){
c --;
if(c<0){
c =SIZE -1;
r --;
if(r<0) break outLoop;
}
if(p.isFixed(r,c)) continue;
t =num[r][c];
if(t!=0){
rFlags[r][t] =false;
cFlags[c][t] =false;
zFlags[r/3*3+c/3][t] =false;
num[r][c] =0;
}
} else{
t ++;
if(!(rFlags[r][t]||
cFlags[c][t]||
zFlags[r/3*3+c/3][t])
) break;
}
}//&#for(c++;;);
num[r][c] =t;
rFlags[r][t] =true;
cFlags[c][t] =true;
zFlags[r/3*3+c/3][t] =true;
c ++;
if(c>=SIZE){
c =0;
r ++;
if(r>=SIZE) break outLoop;
}
}
if(r<0) return false;
for(r=0;r<SIZE;r++)
for(c=0;c<SIZE;c++)
if(!p.isFixed(r,c)) p.setNumber(r,c,num[r][c]);
return true;
}
//test
public static void main(String[] args){
Puzzler p =new Puzzler();
int[][] data ={{0,0,0, 0,0,4, 0,7,6},
{8,0,1, 0,0,0, 0,3,0},
{0,4,6, 0,0,3, 0,0,0},

{0,0,0, 0,2,0, 7,0,1},
{1,0,0, 7,0,6, 0,0,5},
{5,0,7, 0,3,0, 0,0,0},

{0,0,0, 9,0,0, 8,1,0},
{0,5,0, 0,0,0, 2,0,4},
{9,1,0, 8,0,0, 0,0,0}
};
p.setPuzzler(data);
System.out.println(solve(p));
for(int r =0;r<SIZE;r++){
for(int c=0;c<SIZE;c++) System.out.print(p.getNumber(r,c)+\" \");
System.out.println();
}
}
}


My BlogClick Me
2007-06-23 13:28
Eastsun
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:32
帖 子:802
专家分:0
注 册:2006-12-14
  得分:0 
回复:(Eastsun)[分享]数独的JAVA解法
未完成的游戏,在JRE6.0下运行


ps:注意,游戏里面的画面都是出来的,而不是用图片
附件: 您没有浏览附件的权限,请 登录注册

My BlogClick Me
2007-06-23 13:30
千里冰封
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:灌水之王
等 级:版主
威 望:155
帖 子:28494
专家分:59
注 册:2006-2-26
  得分:0 

太牛B了

人才也


可惜不是你,陪我到最后
2007-06-23 14:41
pity1115
Rank: 1
等 级:新手上路
威 望:2
帖 子:184
专家分:0
注 册:2006-9-15
  得分:0 
界面太漂亮了
把GUI部分的代码贴出来让我学习一下嘛!

[此贴子已经被作者于2007-6-23 16:55:38编辑过]


2007-06-23 16:53
可可熊
Rank: 3Rank: 3
等 级:新手上路
威 望:9
帖 子:553
专家分:0
注 册:2007-6-15
  得分:0 
能不能把源代码也打个包提供下载呢?"
2007-06-23 17:11
Eastsun
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:32
帖 子:802
专家分:0
注 册:2006-12-14
  得分:0 
以下是引用可可熊在2007-6-23 17:11:21的发言:
能不能把源代码也打个包提供下载呢?"

呵呵,如你所愿~
本文中的代码打包:

附件: 您没有浏览附件的权限,请 登录注册

My BlogClick Me
2007-06-23 18:12
kingstarer
Rank: 1
等 级:新手上路
帖 子:24
专家分:0
注 册:2007-4-12
  得分:0 

巧啊,我也在做

ps:LZ数独部分就有这么长吗

2007-09-26 23:48
Eastsun
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:32
帖 子:802
专家分:0
注 册:2006-12-14
  得分:0 

LS嫌数独求解部分代码太长了吗?
那就来个精简版的吧:


public class S{
static void r(char[]b,int p){
long u=0;
if(--p<0) System.out.print(b);
else if(b[p]>48) r(b,p);
else{
for(int i=81;i-->0;)
u|=(p-i)%9*(p/9^i/9)*(p/27^i/27|p%9/3^i%9/3) ==0?1L<<b[i]:0;
for(b[p]=58;--b[p]>48;)
if((u>>b[p]&1)<1)
r(b,p);
}
}
public static void main(String[] a){
r(a[0].toCharArray(),81);
}
}

编译后,在控制台上运行: java S 00000..000
其中0000000..0000000是一个包含81个数字的字符串,代表一个数独,按从左到右,从上到下的顺序连接而成,其中的0表示要放入的空位置.
输出就是这个数独的解.


My BlogClick Me
2007-09-27 00:04
缘吇弹
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:抄底吧
等 级:版主
威 望:43
帖 子:3037
专家分:7
注 册:2007-7-2
  得分:0 
嗯,真牛

Repeat  Life=Study;Until (death);
2007-09-27 00:07







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.053593 second(s), 7 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved