Android開發實例-自動生成題庫的數獨(一)

本系列文章主要介紹如何利用Android開發一個自動生成題目的數獨游戲。涉及的知識和技術如下所示：

看著市場上千篇一律的數獨應用，他們大都來自於同一個開源應用，題目都是固定不變的那麼100多道。我們就沒有方法改變數獨題目嗎？經過百度搜索，終於找到了一篇自動生成數獨題庫的算法，感謝原作者的理論以及網絡上的部分代碼。算法文檔題庫： IBTlo2hrjqcUOMcQ39ddYx1PaOnF0wjQycQTSYKIHJ5JUK-7WCK9Tz_BvDXQcio8I22k_xu1RZkwUYlUqFTZSa-jzyxgDfY3Ga93U34u

算法思想在文檔中已經描述的十分具體，我們根據算法以及網絡上的部分代碼封裝了可以生成任意難度數獨的實體Sudoku，代碼如下所示：

import java.util.ArrayList;
import java.util.Random;

/**
 * 采用挖洞算法實現。不同難度將會有不同的最小填充格子數和已知格子數
 * 
 */
public class Sudoku {
	private int[][] orginData;	//保存初始狀態的數獨
	// 初始化生成數組
	private int[][] sudokuData = { { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 } };
	// 終盤數組
	private int[][] resultData;
	// 最小填充格子數
	private int minFilled;
	// 最小已知格子數
	private int minKnow;
	// 當前難度級別;1-2簡單難度；3普通難度；4高級難度；5骨灰級難度
	private int level;
	
	private Random ran = new Random();

	public Sudoku() {
//		this(3); // 默認為普通難度
	}

	public Sudoku(int level) {
		if (level < 0 || level > 6) {
			this.level = 3;
		} else {
			this.level = level;
		}
		switch (level) {
		case 1:
		case 2:
			int ranNum = ran.nextInt(10);
			if(ranNum > 4) {
				minKnow = 5;
			} else {
				minKnow = 4;
			}
			minFilled = 45 + ranNum;
			break;
//		case 2:
//			minFilled = 45 + ran.nextInt(5);
//			minKnow = 4;
//			break;
		case 3:
			minFilled = 31 + ran.nextInt(10);
			minKnow = 3;
			break;
		case 4:
			minFilled = 21 + ran.nextInt(10);
			minKnow = 2;
			break;
		case 5:
			minFilled = 17 + ran.nextInt(10);
			minKnow = 0;
			break;
		default:
			break;
		}
		genSuduku();
		orginData = new int[9][9];
		for(int i = 0; i < 9; i++) {
			System.arraycopy(sudokuData[i], 0, orginData[i], 0, 9);
		}
	}

	/**
	 * 生成唯一解的數獨
	 */
	public void genSuduku() {
		int startX = ran.nextInt(9), startY = ran.nextInt(9); // 初始挖洞格子
		int orignStartX = startX, orignStartY = startY; // 暫存初始格子
		int filledCount = 81; // 當前已知格子數
//		int curMinKnow = 9; // 當前已知行列已知格子的下限
		genShuduKnow(11);
		if (solve(sudokuData, true)) {
			// 將終盤賦值給初始數獨數組
			for (int i = 0; i < 9; i++) {
				System.arraycopy(resultData[i], 0, sudokuData[i], 0, 9);
			}
			// 實行等量交換
			sudokuData = equalChange(sudokuData);
			Point nextP; // 下一個挖洞位置
			do {
				int temMinKnow = getMinknow(sudokuData, startX, startY);
				if (isOnlyAnswer(sudokuData, startX, startY)
						&& temMinKnow >= minKnow) {
					sudokuData[startX][startY] = 0;
					filledCount--;
//					curMinKnow = temMinKnow;
				}
				nextP = next(startX, startY);
				startX = nextP.x;
				startY = nextP.y;
				//校驗此洞是否已挖
				while(sudokuData[startX][startY] == 0 && (orignStartX != startX || orignStartY != startY)) {
					nextP = next(startX, startY);
					startX = nextP.x;
					startY = nextP.y;
				}
				//初級難度處理
				if(level == 1 || level == 2) {
					while(startX == orignStartX && startY == orignStartY) {
						nextP = next(startX, startY);
						startX = nextP.x;
						startY = nextP.y;
					}
				}
			} while (filledCount > minFilled
					&& (orignStartX != startX || orignStartY != startY));
		} else {
			// 重新生成唯一解數獨，直到成功為止
			genSuduku();
		}
	}

	/**
	 * 獲取下一個挖洞點
	 * 
	 * @param x
	 * @param y
	 * @return
	 */
	public Point next(int x, int y) {
		Point p = null;
		switch (level) {
		case 1:
		case 2: // 難度1、2均為隨機算法
			p = new Point(ran.nextInt(9), ran.nextInt(9));
			break;
		case 3: // 難度3 間隔算法
			if (x == 8 && y == 7) {
				p = new Point(0, 0);
			} else if (x == 8 && y == 8) {
				p = new Point(0, 1);
			} else if ((x % 2 == 0 && y == 7) || (x % 2 == 1) && y == 0) {
				p = new Point(x + 1, y + 1);
			} else if ((x % 2 == 0 && y == 8) || (x % 2 == 1) && y == 1) {
				p = new Point(x + 1, y - 1);
			} else if (x % 2 == 0) {
				p = new Point(x, y + 2);
			} else if (x % 2 == 1) {
				p = new Point(x, y - 2);
			}
			break;
		case 4: // 難度4 蛇形算法
			p = new Point();
			if (x == 8 && y == 8) {
				p.y = 0;
			} else if (x % 2 == 0 && y < 8) { // 蛇形順序，對下個位置列的求解
				p.y = y + 1;
			} else if ((x % 2 == 0 && y == 8) || (x % 2 == 1 && y == 0)) {
				p.y = y;
			} else if (x % 2 == 1 && y > 0) {
				p.y = y - 1;
			}

			if (x == 8 && y == 8) { // 蛇形順序，對下個位置行的求解
				p.x = 0;
			} else if ((x % 2 == 0 && y == 8) || (x % 2 == 1) && y == 0) {
				p.x = x + 1;
			} else {
				p.x = x;
			}
			break;
		case 5: // 從左至右，從上到下
			p = new Point();
			if (y == 8) {
				if (x == 8) {
					p.x = 0;
				} else {
					p.x = x + 1;
				}
				p.y = 0;
			} else {
				p.x = x;
				p.y = y + 1;
			}
		default:
			break;
		}
		return p;
	}

	/**
	 * 生成指定個數的已知格子
	 * 
	 * @param n
	 */
	public void genShuduKnow(int n) {
		// 生成n個已知格子
		Point[] knowPonits = new Point[n];
		for (int i = 0; i < n; i++) {
			knowPonits[i] = new Point(ran.nextInt(9), ran.nextInt(9));
			// 檢測是否重復
			for (int k = 0; k < i; k++) {
				if (knowPonits[k].equals(knowPonits[i])) {
					i--;
					break;
				}
			}
		}
		// 填充數字
		int num;
		Point p;
		for (int i = 0; i < n; i++) {
			num = 1 + ran.nextInt(9);
			p = knowPonits[i];
			sudokuData[p.x][p.y] = num;
			if (!validateIandJ(sudokuData, p.x, p.y)) {
				// 生成格子填充數字錯誤
				i--;
			}
		}

	}

	/**
	 * 等量交換
	 * 
	 * @param data
	 * @return
	 */
	public int[][] equalChange(int[][] data) {
		Random rand = new Random();
		int num1 = 1 + rand.nextInt(9);
		int num2 = 1 + rand.nextInt(9);
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (data[i][j] == 1) {
					data[i][j] = num1;
				} else if (data[i][j] == num1) {
					data[i][j] = 1;
				}

				if (data[i][j] == 2) {
					data[i][j] = num2;
				} else if (data[i][j] == num2) {
					data[i][j] = 2;
				}
			}
		}
		return data;
	}

	/**
	 * 判斷挖去i,j位置後，是否有唯一解
	 * 
	 * @param data
	 * @param i
	 * @param j
	 * @return
	 */
	public boolean isOnlyAnswer(int[][] data, int i, int j) {
		int k = data[i][j]; // 待挖洞的原始數字
		for (int num = 1; num < 10; num++) {
			data[i][j] = num;
			if (num != k && solve(data, false)) {
				// 除待挖的數字之外，還有其他的解，則返回false
				data[i][j] = k;
				return false;
			}
		}
		data[i][j] = k;
		return true;
	}

	/**
	 * 刪除指定位置後，新的行列下限
	 * 
	 * @param data
	 * @param p
	 * @param q
	 * @return
	 */
	public int getMinknow(int[][] data, int p, int q) {
		int temp = data[p][q];
		int minKnow = 9;
		int tempKnow = 9;
		data[p][q] = 0;
		for (int i = 0; i < 9; i++) {
			// 行下限
			for (int j = 0; j < 9; j++) {
				if (data[i][j] == 0) {
					tempKnow--;
					if (tempKnow < minKnow) {
						minKnow = tempKnow;
					}
				}
			}
			tempKnow = 9;
		}
		tempKnow = 9;
		for (int j = 0; j < 9; j++) {
			// 列下限
			for (int i = 0; i < 9; i++) {
				if (data[i][j] == 0) {
					tempKnow--;
					if (tempKnow < minKnow) {
						minKnow = tempKnow;
					}
				}
			}
			tempKnow = 9;
		}
		data[p][q] = temp;
		// 返回刪除後的下限
		return minKnow;
	}

	/**
	 * 判斷數獨是否能解
	 * 
	 * @param data
	 * @return
	 */
	public boolean solve(int[][] data, boolean flag) {
		int blankCount = 0; // 保存空位個數
		int[][] tempData = new int[9][9]; // 中間數組
		ArrayList blankList = new ArrayList(70); // 保存各個空格坐標
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				tempData[i][j] = data[i][j];
				if (tempData[i][j] == 0) {
					blankCount++;
					blankList.add(new Point(i, j));
				}
			}
		}
		// 校驗數獨合法性
		if (!validate(tempData)) {
			return false;
		}
		if (blankCount == 0) {
			// 玩家已經成功解出數獨
			return true;
		} else if (put(tempData, 0, blankList)) {
			if(flag) {
				// 智能解出答案，供生成數獨終盤使用
				resultData = tempData;
			}
			return true;

		}
		return false;
	}

	/**
	 * 在第n個空位子放入數字
	 * 
	 * @param data
	 * @param n
	 * @param blankList
	 * @return
	 */
	public boolean put(int[][] data, int n, ArrayList blankList) {
		if (n < blankList.size()) {
			Point p = blankList.get(n);
			for (int i = 1; i < 10; i++) {
				data[p.x][p.y] = i;
				if (validateIandJ(data, p.x, p.y)
						&& put(data, n + 1, blankList)) {
					return true;
				}
			}
			data[p.x][p.y] = 0;
			return false;
		} else {
			return true;
		}
	}

	/**
	 * 校驗x, y位置填充的數字是否可行
	 * 
	 * @param data
	 * @param x
	 * @param y
	 * @return
	 */
	public boolean validateIandJ(int[][] data, int x, int y) {
		int m = 0, n = 0, p = 0, q = 0; // m,n是計數器，p,q用於確定測試點的方格位置
		for (m = 0; m < 9; m++) {
			if (m != x && data[m][y] == data[x][y]) {
				return false;
			}
		}
		for (n = 0; n < 9; n++) {
			if (n != y && data[x][n] == data[x][y]) {
				return false;
			}
		}
		for (p = x / 3 * 3, m = 0; m < 3; m++) {
			for (q = y / 3 * 3, n = 0; n < 3; n++) {
				if ((p + m != x || q + n != y)
						&& (data[p + m][q + n] == data[x][y])) {
					return false;
				}
			}
		}
		return true;
	}

	/**
	 * 校驗整個數獨數組的合法性
	 * 
	 * @param data
	 * @return
	 */
	public boolean validate(int[][] data) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (data[i][j] != 0 && !validateIandJ(data, i, j)) {
					// 任何一個數字填充錯誤，則返回false
					return false;
				}
			}
		}
		return true;
	}
	
	/**
	 * 獲取沖突列表
	 * @return
	 */
	public ArrayList validateForList() {
		ArrayList pList = new ArrayList();
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (sudokuData[i][j] != 0 && !validateIandJ(sudokuData, i, j)) {
					pList.add(new Point(i, j));
				}
			}
		}
		return pList;
	}

	public int[][] myResultData() {
		return resultData;
	}
	
	public int[][] myInitData() {
		return orginData;
	}
	
	public int[][] mySudoku() {
		return sudokuData;
	}
	
	/**
	 * 判斷格子是否為已知格子
	 * @param x
	 * @param y
	 * @return
	 */
	public boolean isKnownCell(int x, int y) {
		return orginData[x][y] != 0;
	}
	
	public void makeToInitData() {
		for(int i = 0; i < 9; i++) {
			System.arraycopy(orginData[i], 0, sudokuData[i], 0, 9);
		}
	}
	
	public void set(int x, int y, int num) {
		sudokuData[x][y] = num;
	}
	
	public boolean isSuccess() {
 		for(int i = 0; i < 9; i++) {
 			for(int j = 0; j < 9; j++) {
// 				if(sudokuData[i][j] == 0 || sudokuData[i][j] != resultData[i][j]) {
// 					return false;
// 				}
 				if(sudokuData[i][j] == 0) {
 					return false;
 				}
 			}
 		}
 		return validate(sudokuData);
// 		return true;
	}

	public void setOrginData(int[][] orginData) {
		this.orginData = orginData;
	}

	public void setSudokuData(int[][] sudokuData) {
		this.sudokuData = sudokuData;
	}

	public void setResultData(int[][] resultData) {
		this.resultData = resultData;
	}
	
	
}