数独（すうどく，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, backtracking
Help 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 stub
int[][] 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();
}
}
}