关于数独地图的产生

如何生成一个数独的地图，并且保证是有解的？我能想到的办法就是先产生一个解，然后做减法，产生解的过程可以通过迷宫的回溯方法解决，每个位置有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;
	}
}

评论

1 楼 albertshaw 2011-04-02  

init()里面

for (int i = 1; i < 10; i++) {
	for (int j = 1; j < 10; j++) {
		map[i][j] = 0;
	}
}

这是在干嘛,删掉吧?
额,我也就能看看这种无关紧要的小问题了...