找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2191|回复: 1
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Sudoku Solver】-【刷题第一弹2014】

[复制链接]

22

主题

6

精华

612

积分

超级会员

Rank: 4

积分
612
发表于 10-11-2014 11:13 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 timeforce 于 10-11-2014 11:15 PM 编辑

leetcode通道:https://oj.leetcode.com/problems/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.

思路:
首先这道题的思路的比较直观,我们先把空着的格子统计出来放到一个ArrayList 里面, 然后开始运用dfs
首先每当填入一个数字的时候我们需要用isValid来验证,只有不冲突的情况下才能添加进格子里
dfs 函数返回值定义为boolean
if(dfs(empty,board,cur+1,len)) 运行成功往上一层返回true,如果不成功, 把刚填入的数字抹去再去试下一个数字,如果这一层的数字都不成功,返回false, 跳回上一层进行修改,最后如果cur==len 的时候所有格子都填完返回true,一路返回true上去完成任务
代码:[code]public class Solution {
    public void solveSudoku(char[][] board) {
        ArrayList empty = new ArrayList();
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
                if(board[j]=='.'){
                    empty.add(i*9+j);
                }
        int len = empty.size();
        dfs(empty,board,0,len);
    }
   
    public boolean dfs(ArrayList empty, char[][] board, int cur, int len){
        if(cur==len) return true;
        int index = empty.get(cur);
        int row = index/9;
        int col = index%9;
        for(int v=1;v<=9;v++){
            if(isValid(v,row,col,board)){
                board[row][col] = (char)(v+'0');
                if(dfs(empty,board,cur+1,len))
                    return true;
                board[row][col] = '.';
            }
        }
        return false;
    }
   
    public boolean isValid(int v, int row, int col, char[][] board){
        for(int i=0;i<9;i++){
            if(board[row] - '0'==v) return false;
            if(board[col] - '0'==v) return false;
            int row_s = 3*(row/3) + i/3;
            int col_s = 3*(col/3) + i%3;
            if(board[row_s][col_s] - '0'==v) return false;
        }
        return true;
    }
}[/code]

几点注意的地方:
1. 验证小九宫格的时候,坐标为{3*(row/3)+i/3 , 3*(col/3)+i%3}
2. char到int的转换 - '0'
[size=14.4444446563721px]时间复杂度是 O((n^2)!), 平均情况下不会到这个程度,空间复杂度是 O(n^2).


本帖被以下淘专辑推荐:

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 12-10-2014 04:16 AM | 显示全部楼层
c++版本,思路一致,dfs+backtracking
  1.     void solveSudoku(vector<vector<char> > &board){
  2.         solveSudoku(0, 0, board);
  3.     }
  4.    
  5.     bool solveSudoku(int row, int col, vector<vector<char> > &board) {
  6.         if(row == 9) return true;
  7.         
  8.         int next_row = col == 8 ? row + 1 : row;
  9.         int next_col = col == 8 ? 0 : col + 1;        
  10.         if(board[row][col] != '.'){
  11.             if(solveSudoku(next_row, next_col, board))
  12.                 return true;
  13.         }
  14.         else{
  15.             char tmp = board[row][col];
  16.             for(char c = '1'; c <= '9'; c++){
  17.                 if(isValid(row, col, c, board)){
  18.                     board[row][col] = c;
  19.                     if(solveSudoku(next_row, next_col, board))
  20.                         return true;
  21.                 }
  22.             }
  23.             board[row][col] = tmp;
  24.         }
  25.         return false;
  26.     }
  27.    
  28.     bool isValid(int row, int col, char c, vector<vector<char> > &board){
  29.         for(int i = 0; i < 9; i++)
  30.             if(board【i】[col] == c) return false;
  31.         
  32.         for(int j = 0; j < 9; j++)
  33.             if(board[row][j] == c) return false;
  34.         
  35.         int sr = (row / 3) * 3;
  36.         int sc = (col / 3) * 3;
  37.         for(int i = 0; i < 3; i++)
  38.             for(int j = 0; j < 3; j++)
  39.                 if(board[sr + i][sc + j] == c) return false;

  40.         return true;
  41.     }
复制代码

易错点,board的值在进入下一次循环前一定要复原

补充内容 (1-19-2015 08:45 AM):
刷第二次的时候,又忘了把board值复原了。
另外一个提高效率的地方,在isValid函数中,不需要借助hashmap,虽然leetcode把这道题归到hashtable里了
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表