如何生成一个数独的地图,并且保证是有解的?我能想到的办法就是先产生一个解,然后做减法,产生解的过程可以通过迷宫的回溯方法解决,每个位置有9个选择。
初始化时,可以把前9个位置按照乱序的1-9进行排列,然后顺序求出下面的解。但是这样随机性不怎么好,应该可以指定地图上任何9个不重复的数据,这个是肯定无害的,当回溯的时候,不能改变这些固定数据的值,即在地图上随机产生9个位置。
不过显然这样可以求出解,但性能不高,因为从来没有过滤过重复的比较判定,实际上,每次判定过程中的可以推理出N种可能,但我们只取得了一种,下次又会重复判定。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Sudoku {
private int[][] map = new int[10][10];
public static void main(String[] args){
Sudoku su = new Sudoku();
for(int i=0;i<10;i++){
su.run();
System.out.println();
}
}
public void run(){
init();
draw();
print();
}
private void init(){
for(int i=1;i<10;i++){
for(int j=1;j<10;j++){
map[i][j] = 0;
}
}
randomInit();
}
private void print(){
for(int i=1;i<10;i++){
for(int j=1;j<10;j++){
System.out.print(map[i][j] + "\t");
}
System.out.println();
}
}
private static class Point{
public Point(int x, int y){
this.x = x;
this.y = y;
}
int x,y;
}
public void draw(){
Point p = new Point(2, 1);
int s = 1;
while(p != null){
if(!lay(p.x, p.y, s)){
p = previous(p.x, p.y);
s = map[p.x][p.y] + 1;
}else{
p = next(p.x, p.y);
s = 1;
}
}
}
private void randomInit() {
List<Integer> startNumbers = new ArrayList<Integer>();
for(int i=1;i<=9;i++){
startNumbers.add(i);
}
Collections.shuffle(startNumbers);
for(int i=1;i<=9;i++){
map[i][1] = startNumbers.get(i - 1);
}
}
public boolean lay(int x, int y, int s){
for(int v=s;v<10;v++){
map[x][y] = v;
if(isValid(x, y)){
return true;
}
}
map[x][y] = 0;
return false;
}
private Point next(int x, int y){
if(x == 9 && y == 9){
return null;
}else if(x == 9){
return new Point(1, y+1);
}else{
return new Point(x+1, y);
}
}
private Point previous(int x, int y){
if(x == 1 && y == 1){
throw new RuntimeException("Nan solution found!");
}else if(x == 1){
return new Point(9, y-1);
}else{
return new Point(x-1, y);
}
}
private boolean isValid(int x, int y){
for(int i=1;i<10;i++){
if(i != y && map[x][i] == map[x][y]){
return false;
}
if(i != x && map[i][y] == map[x][y]){
return false;
}
}
int xStart = getZone(x)*3;
int yStart = getZone(y)*3;
for(int i=xStart+1;i<=xStart+3;i++){
for(int j=yStart+1;j<=yStart+3;j++){
if(map[i][j] == map[x][y] && !(x == i && y == j)){
return false;
}
}
}
return true;
}
private int getZone(int n){
return (n -1)/3;
}
}
分享到:
相关推荐
输入数独当前数组,通过计算机计算。就能得到当前数独的解法
数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏...
数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码数独代码...
数独游戏,能产生数独,用户可选择难度,可获得游戏提示,可核对答案。黑白界面。
小巧的数独编辑器,现在可以编辑标准数独、宫格数独、锯齿数独、超级数独(或者叫窗口数独)、杀手数独、时钟数独等,并且数独的尺寸不限定为3x3,比如宫格数独可以编辑3x2及3x4等等的地图尺寸。压缩包中附带了若干...
数独验证器
小巧的数独编辑器,现在可以编辑标准数独、宫格数独、锯齿数独、超级数独(或者叫窗口数独)、杀手数独、时钟数独等,并且数独的尺寸不限定为3x3,比如宫格数独可以编辑3x2及3x4等等的地图尺寸。压缩包中附带了若干...
小巧的数独编辑器,现在可以编辑标准数独、宫格数独、锯齿数独、超级数独(或者叫窗口数独)、杀手数独、时钟数独等,并且数独的尺寸不限定为3x3,比如宫格数独可以编辑3x2及3x4等等的地图尺寸。压缩包中附带了若干...
小巧的数独编辑器,现在可以编辑标准数独、宫格数独、锯齿数独、超级数独(或者叫窗口数独)、杀手数独、时钟数独等,并且数独的尺寸不限定为3x3,比如宫格数独可以编辑3x2及3x4等等的地图尺寸。压缩包中附带了若干...
小巧的数独编辑器,现在可以编辑标准数独、宫格数独、锯齿数独、超级数独(或者叫窗口数独)、杀手数独、时钟数独、连体数独等,并且数独的尺寸不限定为3x3,比如宫格数独可以编辑3x2及3x4等等的地图尺寸。...
数独计算器 数独游戏 数独秒算 本数独游戏 采用分为闯关模式和 随机模式,随机模式中的题库更多,闯关模式会随着 关数的增加而越来越难。2个互不影响。 另外还有个数独计算器,妙算数独。 修复了上次数独计算器的2...
winform数独C#的数独游戏 本程序基于.netframework使用C#语言开发,实现功能: 1、各个难度随机出题(New); 2、数独解题提示(Compute); 3、输入的合法性校验; 思路分享 说一下开发步骤及思路: 1、验证合法性...
关于数独的算法有很多种,最基本的有基拙挖掘法,唯一解法,侯选数置换法.查了很多资料但都没有找到完整的算法实现.花了30块银子到当当网上买了编程之美>>找到其中的章节,看完之后大失所望.其中的算法实现藏头露尾,...
制作了一个简单的数独游戏,使用了非递归的算法数独结果。
数独 J2ME 数独 J2ME 数独 J2ME 数独 J2ME
每个9x9方格的数独游戏都有唯一的解,利用C++可以写出一个代码求出这一唯一解,并输出
数独
微信小程序 小游戏类 数独小游戏 (源代码+截图)微信小程序 小游戏类 数独小游戏 (源代码+截图)微信小程序 小游戏类 数独小游戏 (源代码+截图)微信小程序 小游戏类 数独小游戏 (源代码+截图)微信小程序 小...
数独labview实现的源代码
手动输入原始数独,可得结果matlab代码,根据确定性原理