首页 > 其他 > 详细

(Hard) Sudoku Solver - LeetCode

时间:2019-08-22 13:35:45      阅读:101      评论:0      收藏:0      [点我收藏+]

Description:

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character ‘.‘.

技术分享图片
A sudoku puzzle...

技术分享图片
...and its solution numbers marked in red.

Note:

  • The given board contain only digits 1-9 and the character ‘.‘.
  • You may assume that the given Sudoku puzzle will have a single unique solution.
  • The given board size is always 9x9.
Accepted
140.8K
Submissions
367.2K

 

Solution:

class Solution {
    public void solveSudoku(char[][] board) {
        
        Solve_Helper(board);
        
        
    }
    
    //Helper function SolveSudoku
    /*  Find row, col of an unassigned cell
  If there is none, return true
  For digits from 1 to 9
    a) If there is no conflict for digit at row, col
        assign digit to row, col and recursively try fill in rest of grid
    b) If recursion successful, return true
    c) Else, remove digit and try another
  If all digits have been tried and nothing worked, return false
  */
    
    public boolean Solve_Helper(char[][] board){
        
        int row = -1; 
        
        int col = -1; 
        
        boolean isEmpty = true; 
        
    
        for (int i = 0; i < 9; i++) 
        { 
            for (int j = 0; j < 9; j++)  
            { 
                if (board[i][j] == ‘.‘)  
                { 
                    
                    row = i; 
                    col = j; 

                    // we still have some remaining 
                    // missing values in Sudoku 
                    isEmpty = false;  
                    break; 
                } 
            } 
            
            if (!isEmpty) 
            { 
                break; 
            } 
        } 

        // no empty space left 
        if (isEmpty)  
        { 
            return true; 
        } 
        
         // else for each-row backtrack 
        for (char num = ‘1‘; num <= ‘9‘; num++) 
                { 
                    if (IsSafe(board, row, col, num)) 
                    { 
                        board[row][col] = num; 
                        if (Solve_Helper(board))  
                        { 
                            // print(board, n); 
                            return true; 
                        }  
                        else
                        { 
                            board[row][col] = ‘.‘; // replace it 
                        } 
                    } 
                } 
                return false; 

    }
      
    //Helper function to check collison
    public boolean IsSafe(char[][] board,  int row, int col,  char num)
    {
        //Check Column Collision
        
        for(int i = 0; i<board.length; i++){
            
            
            if(i!= row && board[i][col]==num){
                
                return false;
            }
        }
        
        // Check Row Collison
        
        for(int j= 0; j< board[0].length; j++){
            
            if(j!= col && board[row][j] ==num){
            
                return false;
            }
        }
        
        //Check 3*3 on based on the row and col position
        
        for(int i = row/3*3; i< row/3*3+3; i++){
            
            for(int j = col/3*3; j<col/3*3+3; j++){
                
                if(i!=row &&j!=col && board[i][j]==num){
                    return false;
                }
            }   
        }    
        
        return true;
    
    }
}

 

(Hard) Sudoku Solver - LeetCode

原文:https://www.cnblogs.com/codingyangmao/p/11393553.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!