Algorithm

Sudoku

Posted by Tong on March 11, 2020

36. Valid Sudoku

Difficulty: Medium

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.


A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Input:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true

Example 2:

Input:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8\. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.
  • The given board contain only digits 1-9 and the character '.'.
  • The given board size is always 9x9.

Solution

Language: C++

class Solution {
 public:
  bool isValidSudoku(vector<vector<char>>& board) {
    vector<vector<int>> rows(9, vector<int>(10, 0));
    vector<vector<int>> cols(9, vector<int>(10, 0));
    vector<vector<int>> boxes(9, vector<int>(10, 0));
    for (int r = 0; r < 9; ++r) {
      for (int c = 0; c < 9; ++c) {
        if (board[r][c] == '.') {
          continue;
        }
        const int num = board[r][c] - '0';
        if (!rows[r][num] && !cols[c][num] && !boxes[r / 3 * 3 + c / 3][num]) {
          rows[r][num] = 1;
          cols[c][num] = 1;
          boxes[r / 3 * 3 + c / 3][num] = 1;
        } else {
          return false;
        }
      }
    }
    return true;
  }
};

37. Sudoku Solver

Difficulty: Hard

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.

Solution

Language: C++

class Solution {
 public:
  void solveSudoku(vector<vector<char>>& board) {
    rows_ = vector<vector<int>>(9, vector<int>(10));
    cols_ = vector<vector<int>>(9, vector<int>(10));
    boxes_ = vector<vector<int>>(9, vector<int>(10));

    for (int i = 0; i < 9; ++i) {
      for (int j = 0; j < 9; ++j) {
        const char c = board[i][j];
        if (c != '.') {
          const int n = c - '0';
          const int bx = j / 3;
          const int by = i / 3;
          rows_[i][n] = 1;
          cols_[j][n] = 1;
          boxes_[by * 3 + bx][n] = 1;
        }
      }
    }

    fill(board, 0, 0);
  }

 private:
  bool fill(vector<vector<char>>& board, int x, int y) {
    if (y == 9) {
      return true;
    }

    const int nx = (x + 1) % 9;
    const int ny = (nx == 0) ? y + 1 : y;

    if (board[y][x] != '.') {
      return fill(board, nx, ny);
    }

    for (int i = 1; i <= 9; ++i) {
      const int bx = x / 3;
      const int by = y / 3;
      const int box_key = by * 3 + bx;
      if (!rows_[y][i] && !cols_[x][i] && !boxes_[box_key][i]) {
        rows_[y][i] = 1;
        cols_[x][i] = 1;
        boxes_[box_key][i] = 1;
        board[y][x] = i + '0';
        if (fill(board, nx, ny)) {
          return true;
        }
        board[y][x] = '.';
        boxes_[box_key][i] = 0;
        cols_[x][i] = 0;
        rows_[y][i] = 0;
      }
    }
    return false;
  }

 private:
  vector<vector<int>> rows_, cols_, boxes_;
};

980. Unique Paths III

Difficulty: Hard

On a 2-dimensional grid, there are 4 types of squares:

  • 1 represents the starting square.  There is exactly one starting square.
  • 2 represents the ending square.  There is exactly one ending square.
  • 0 represents empty squares we can walk over.
  • -1 represents obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Example 1:

Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1\. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2\. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

Example 2:

Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths: 
1\. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2\. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3\. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4\. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

Example 3:

Input: [[0,1],[2,0]]
Output: 0
Explanation: 
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.

Note:

  1. 1 <= grid.length * grid[0].length <= 20

Solution

Language: C++

class Solution {
 public:
  int uniquePathsIII(vector<vector<int>>& grid) {
    rows_ = static_cast<int>(grid.size());
    if (rows_ == 0) {
      return 0;
    }
    cols_ = static_cast<int>(grid[0].size());
    if (cols_ == 0) {
      return 0;
    }
    num_of_non_obstacle_ = 0;
    // find start pos
    for (int r = 0; r < rows_; ++r) {
      for (int c = 0; c < cols_; ++c) {
        if (grid[r][c] != -1) {
          ++num_of_non_obstacle_;
        }
        if (grid[r][c] == 1) {
          start_r = r;
          start_c = c;
        }
      }
    }

    // depth-first search
    sum_ = 0;
    dfs(grid, start_r, start_c, 1);
    return sum_;
  }

 private:
  void dfs(vector<vector<int>>& grid, const int r, const int c, const int cnt) {
    if (r < 0 || r >= rows_ || c < 0 || c >= cols_ || grid[r][c] == -1) {
      // if out of bounds, or already there
      return;
    }
    if (grid[r][c] == 2) {
      if (cnt == num_of_non_obstacle_) {
        ++sum_;
      }
      return;
    }

    const int backup = grid[r][c];
    grid[r][c] = -1;
    dfs(grid, r - 1, c, cnt + 1);
    dfs(grid, r + 1, c, cnt + 1);
    dfs(grid, r, c - 1, cnt + 1);
    dfs(grid, r, c + 1, cnt + 1);
    grid[r][c] = backup;
  }

 private:
  int rows_;
  int cols_;
  int start_r, start_c;
  size_t num_of_non_obstacle_;
  int sum_;
};
CATALOG
    FEATURED TAGS
    Installation SLAM C++ Language Algorithm Technique Reconstruction DSO VIO