數獨Sudoku

數獨（すうどく，Sūdoku），是源自18世紀瑞士發明，流傳到美國，再由日本發揚光大的一種數學游戲。是一種運用紙、筆進行演算的邏輯游戲。玩家需要根據9×9盤面上的已知數字，推理出所有剩余空格的數字，并滿足每一行、每一列、每一個粗線宮內的數字均含1-9，不重復。

下面我們寫一個小程序來求解數獨問題。

對于計算機來說，他無法根據自己的判斷聰明的給出解答，只能從首個空位置逐一嘗試，如果發現到目前為止走不動了，則需要會退到上一個填數的位置，嘗試下一個數字，以此類推。

使用棧的非遞歸方式。

• 我們設置一個結構，包含元素的行號、列號以及放置的數字，每次講放置的信息記錄到棧里；
• 如果走到某個位置發現從1-9沒有任何元素可以在這里放置，則需要回溯，回到上一個位置，為下一個位置留出一個元素。

CODE：

import java.util.Stack;class Help {int row;int col;int val;
}
public class Sudoku {/*** Use stack store the roads.* @param chess* @return*/public static int[][] getSudoku(int[][] chess) {Stack<Help> stack = new Stack<Help>();int val = -1;for(int i=0; i<9; i++) {for(int j=0; j<9; j++) {if(chess[i][j] != 0)continue;boolean flag = false;int k;if(val == -1)k = 0;else k = val+1;for(; k<10; k++) {if(isValid(k, i, j, chess)) {Help h = new Help();h.row = i;h.col = j;h.val = k;stack.add(h);chess[i][j] = k;val = -1;flag = true;}if(flag == true)k = 10;}if(flag == false && !stack.isEmpty()) { //There is no road, backtrackingHelp h = stack.pop();i = h.row;j = h.col-1;val = h.val;chess[i][j+1] = 0;}}}return chess;}/*** Judge if it is valid when chess[row][col] = k.* @param k* @param row* @param col* @param chess* @return*/private static boolean isValid(int k, int row, int col, int[][] chess) {for(int i=0; i<9; i++)if(chess[row][i] == k)return false;for(int i=0; i<9; i++) if(chess[i][col] == k)return false;int r = row/3, c = col/3;for(int i=r*3; i<r*3+3; i++) {for(int j=c*3; j<c*3+3; j++) {if(chess[i][j] == k)return false;}}return true;}public static void main(String[] args) {// TODO Auto-generated method stubint[][] a = {{0,4,2,0,6,3,0,0,9},{6,0,0,0,1,0,0,0,5},{3,0,0,0,2,0,4,8,0},{1,0,0,5,0,2,6,0,8},{4,0,0,0,0,7,0,0,1},{9,0,5,6,0,0,0,0,7},{0,3,6,0,5,0,0,0,2},{2,0,0,0,7,0,0,0,4},{7,0,0,2,9,0,8,5,0}};int[][] res = getSudoku(a);for(int i=0; i<9; i++) {for(int j=0; j<9; j++)System.out.print(res[i][j] + " ");System.out.println();}}}