[LeetCode][JavaScript]Sudoku Solver

浏览数：44 / 时间：2015年06月08日

Sudoku Solver

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.

又是一道DFS。

test case比较弱，只有6个，并且说好了都是可解的。

每到一格先看看是不是结束了或者不需要填，否则调用findCandidate方法找出在当前这一步所有可填的数字，然后开始递归。

每一轮递归回来都要把默认的‘.‘写回去，否则会影响下一轮的结果。

开了个flag记录是不是结束，如果已经遍历完就return掉，不用再找了。

 1 /**
 2  * @param {character[][]} board
 3  * @return {void} Do not return anything, modify board in-place instead.
 4  */
 5 var solveSudoku = function(board) {
 6     var isComplete = false;
 7     dfs(0, 0);
 8 
 9     function dfs(x, y){
10         if(isComplete){
11             return;
12         }
13         var candidates = findCandidate(x, y);
14         if(x === 8 && y == 8){
15             if(board[8][8] === ‘.‘){
16                  board[8][8] = candidates[0];
17             }
18             isComplete = true;
19             return;
20         }
21 
22         if(board[x][y] !== ‘.‘){
23             if(y === 8){
24                 dfs(x + 1, 0);
25                 return;
26             }else{
27                 dfs(x, y + 1);
28                 return;
29             }
30         }
31         for(var i = 0; i < candidates.length; i++){
32             board[x][y] = candidates[i];
33             if(y === 8){
34                 dfs(x + 1, 0);
35             }else{
36                 dfs(x, y + 1);
37             }
38             if(!isComplete){
39                board[x][y] = ‘.‘; 
40             }else{
41                 return;
42             }
43         }
44     }
45 
46     function findCandidate(x, y){
47         var set = new Set();
48         var candidate = [];
49         var cell = -1;
50         //row
51         for(i = 0; i < 9; i++){
52             cell = board[x][i];
53             if(!set.has(cell)){
54                 set.add(cell);
55             }   
56         }
57         //column
58         for(i = 0; i < 9; i++){
59             cell = board[i][y];
60             if(!set.has(cell)){
61                 set.add(cell);
62             }  
63         }
64         //square
65         var offsetX = parseInt(x / 3) * 3;
66         var offsetY = parseInt(y / 3) * 3;
67         for(i = 0; i <= 2; i++){
68             for(j = 0; j <= 2; j++){
69                 cell = board[i + offsetX][j + offsetY];
70                 if(!set.has(cell)){
71                     set.add(cell);
72                 }
73             }
74         }
75         //find candidate
76         for(i = 1; i <= 9; i++){
77             if(!set.has(i + "")){
78                 candidate.push(i + "");
79             }
80         }
81         return candidate;
82     } 
83 };

附赠一个UT

 1 function test(){
 2     var map = [
 3         [‘5‘,‘3‘,‘.‘,‘.‘,‘7‘,‘.‘,‘.‘,‘.‘,‘.‘],
 4         [‘6‘,‘.‘,‘.‘,‘1‘,‘9‘,‘5‘,‘.‘,‘.‘,‘.‘],
 5         [‘.‘,‘9‘,‘8‘,‘.‘,‘.‘,‘.‘,‘.‘,‘6‘,‘.‘],
 6         [‘8‘,‘.‘,‘.‘,‘.‘,‘6‘,‘.‘,‘.‘,‘.‘,‘3‘],
 7         [‘4‘,‘.‘,‘.‘,‘8‘,‘.‘,‘3‘,‘.‘,‘.‘,‘1‘],
 8         [‘7‘,‘.‘,‘.‘,‘.‘,‘2‘,‘.‘,‘.‘,‘.‘,‘6‘],
 9         [‘.‘,‘6‘,‘.‘,‘.‘,‘.‘,‘.‘,‘2‘,‘8‘,‘.‘],
10         [‘.‘,‘.‘,‘.‘,‘4‘,‘1‘,‘9‘,‘.‘,‘.‘,‘5‘],
11         [‘.‘,‘.‘,‘.‘,‘.‘,‘8‘,‘.‘,‘.‘,‘7‘,‘9‘]
12     ]
13 
14     solveSudoku(map);
15 
16     for(var m = 0; m < map.length; m++){
17         var line = "";
18         for(var n = 0; n < map[m].length; n++){
19             line += (map[m][n] + ",");
20         }
21         console.log(line);
22     }
23 }