Problem:
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character’.’.
You may assume that there will be only one unique solution.
A sudoku puzzle…
…and its solution numbers marked in red.
Solution:
采用笨拙的DFS的办法，判断填入的数字是否合法，可以通过三个规则事先过滤掉不合法的数字，然后试试剩余的是否有合法的数字
题目大意：
填数独游戏。。。。。。
Java源代码（300ms）：
public class Solution {public void solveSudoku(char[][] board) {SudoKu(board,0,0);}private boolean SudoKu(char[][] board,int i,int j){if(i==8 && j==9)return true;if(j==9){i++;j=0;}if(board[i][j]!='.'){if(SudoKu(board,i,j+1))return true;}else{int[] map=getValidNum(board,i,j);for(int k=1;k<10;k++){if(map[k]==0){board[i][j]=(char)(k+'0');if(SudoKu(board,i,j+1))return true;board[i][j]='.';}}}return false;}private int[] getValidNum(char[][] board,int i,int j){int[] map=new int[10];for(int k=0;k<9;k++){if(board[i][k]!='.')map[board[i][k]-'0']=1;if(board[k][j]!='.')map[board[k][j]-'0']=1;}for(int k=3*(i/3);k<3*(i/3)+3;k++){for(int l=3*(j/3);l<3*(j/3)+3;l++){if(board[k][l]!='.')map[board[k][l]-'0']=1;}}return map;}}C语言源代码（12ms）：
int* getValidNum(char** board,int i,int j){int k,l;int* map = (int*)malloc(sizeof(int)*10);memset(map,0,sizeof(int)*10);for(k=0;k<9;k++){if(board[i][k]!='.') map[board[i][k]-'0']=1;}for(k=0;k<9;k++){if(board[k][j]!='.') map[board[k][j]-'0']=1;}for(k=3*(i/3);k<3*(i/3)+3;k++){for(l=3*(j/3);l<3*(j/3)+3;l++){if(board[k][l]!='.') map[board[k][l]-'0']=1;}}return map;}bool SudoKu(char** board,int i,int j){int k;if(i==8 && j==9)return true;if(j==9){i++;j=0;}if(board[i][j]!='.'){if(SudoKu(board,i,j+1))return true;}else{int* map=getValidNum(board,i,j);for(k=1;k<10;k++){if(map[k]==0){board[i][j]=k+'0';if(SudoKu(board,i,j+1))return true;board[i][j]='.';}}free(map);}return false;} void solveSudoku(char** board, int boardRowSize, int boardColSize) {SudoKu(board,0,0);}C++源代码（24ms）：
class Solution {public:void solveSudoku(vector<vector<char>>& board) {SudoKu(board,0,0);}private:bool SudoKu(vector<vector<char>>& board,int i,int j){if(i==8 && j==9)return true;if(j==9){i++;j=0;}if(board[i][j]!='.'){if(SudoKu(board,i,j+1))return true;}else{int* map=getValidNum(board,i,j);for(int k=1;k<10;k++){if(map[k]==0){board[i][j]=k+'0';if(SudoKu(board,i,j+1))return true;board[i][j]='.';}}}return false;}int* getValidNum(vector<vector<char>>& board,int i,int j){int* map=(int*)malloc(sizeof(int)*10);memset(map,0,sizeof(int)*10);for(int k=0;k<9;k++){if(board[i][k]!='.')map[board[i][k]-'0']=1;if(board[k][j]!='.')map[board[k][j]-'0']=1;}for(int k=3*(i/3);k<3*(i/3)+3;k++){for(int l=3*(j/3);l<3*(j/3)+3;l++){if(board[k][l]!='.')map[board[k][l]-'0']=1;}}return map;}};Python源代码（636ms）：
class Solution:# @param {character[][]} board# @return {void} Do not return anything, modify board in-place instead.def solveSudoku(self, board):self.SudoKu(board,0,0)def SudoKu(self,board,i,j):if i==8 and j==9:return Trueif j==9:i+=1;j=0if board[i][j]!='.':if self.SudoKu(board,i,j+1):return Trueelse:map=self.getValidNum(board,i,j)for k in range(1,10):if map[k]==0:board[i][j]=chr(k+ord('0'))if self.SudoKu(board,i,j+1):return Trueboard[i][j]='.'return Falsedef getValidNum(self,board,i,j):map=[0 for k in range(10)]for k in range(9):if board[i][k]!='.':map[ord(board[i][k])-ord('0')]=1if board[k][j]!='.':map[ord(board[k][j])-ord('0')]=1for k in range(3*(i/3),3*(i/3)+3):for l in range(3*(j/3),3*(j/3)+3):if board[k][l]!='.':map[ord(board[k][l])-ord('0')]=1return map
，青春在我的心中是苦涩的又是甘甜的，是精致的又是粗糙的，
