LeetCode: 37. Sudoku Solver

LeetCode: 37. Sudoku Solver

Problem: 37. Sudoku Solver

Link: https://leetcode.com/problems/sudoku-solver/

Difficulty: Hard

Description:

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

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3×3 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 9×9.

Solution:

Language: Swift

Runtime: 472ms
Memory: 19.2MB

Copy to Clipboard

class Solution {
    func solveSudoku(_ board: inout [[Character]]) {
        isSolve(&board)
    }
    
    func isSolve (_ board: inout [[Character]]) -> Bool {
        for i in 0 ..< 9 {
            for j in 0 ..< 9 {
                if board[i][j] == "." {
                    for num in 1 ... 9 {
                        if isValid(board, i, j ,num) {
                            board[i][j] = Character(String(num))
                        
                            if isSolve(&board) {
                                return true
                            } else {
                                board[i][j] = "."
                            }
                        }
                    }
                    return false
                }
            }
        }
        return true
    }
    
    func isValid(_ board: [[Character]], _ row: Int, _ col: Int, _ char: Int) -> Bool {
        let num = Character(String(char))
        
        for index in 0 ..< 9 {
            // check row
            if board[index][col] != "." && board[index][col] == num {
                return false
            }
            //check colomn
            if board[row][index] != "." && board[row][index] == num {
                return false
            }
            //check box
            if board[row / 3 * 3 + index / 3][col / 3 * 3 + index % 3] != "." && board[row / 3 * 3 + index / 3][col / 3 * 3 + index % 3] == num {
                return false
            }
        }
        return true
    }
}

Related Posts

Leave A Comment Cancel reply