# LeetCode Hard 37. Sudoku Solver

tags: leetcode

問題

• Explore
• Problems

空のセルを埋めることで数独パズルを解くプログラムを書け,

数独の解答は次の規則を全て満たす必要がある.

1. 各行で1-9の数字がそれぞれ1回だけ出てくる.

2. 各列で1-9の数字がそれぞれ1回だけ出てくる,

3. 9x9の格子の中にある9つの3x3の格子に1-9の数字がそれぞれ1回だけ出てくる,

空のセルは'.'によって示される,

注意:

与えられた盤は1-9の数字と.だけを持つ.

与えられた数独パズルは一意な解を持つと仮定しても良い.

与えられる盤は常に9x9である.

解法

まずは数独の再帰的な構造を注目します

最初のセルから見ていき, 次のセルまで数字を置きます. それ以前にセルに置いた数字によってその決まるという再帰的な構造があります

この場合, 基底は81セルが埋まったときです

また, この問題は数字を埋めることと数字が埋められること, 2つのことを考える必要があるので関数を分けると良いでしょう. 1つの関数が複数の動作をするとデバッグが大変ですし, そもそも書く際にコードが複雑になります

再帰的に考えると

1行目から9行目のセルまでを左から右に埋めていくと考えます

このとき, 今セルに置く数をposとして, row = pos / 9, col = pos % 9と定義すると再帰を書くのが簡潔になります

• 現在のセルに数字が書かれていたら, 次のマスに進みます
• 現在のセルに数字が書かれていなかったら, その数に数字を書きます
  • このときの数字の候補をcandidateとします
  • この数字が置けるならば, 次のセルに進みます
    • この際に次のセルに進んだ結果によってこれからもこの選択肢の探索をするか決めます
    • これはBacktrakingという言われる手法で途中で正解が出ないと分かったらそれ以上は計算をやめます
  • 探索の後に数字をセルを空にしておきます
  • これによって次の探索でこの探索に失敗したときの影響がなくなるようにします
• 全てが正しい答えのときにその際の盤の状態が出力されます

文字が置けるかどうか

isValidという関数で下では書いています

まずは同じ行, 列に置けるかを調べます. これは多分良いと思います

次に格子の中の格子に置けるかどうかの調べ方です

まずはその格子(sub格子)の中で最も左のセルについて考えます

これはrowとcolをそれぞれ3で割った際の商です(0-indexed)

ここで0-8を3で割った商と余りがそれぞれsub格子に行と列に対応することを考えるとこれらの値をrowとcolに足してそれらの数字と被っていないかを調べれば良いです

計算量

ヒューリスティック探索なので計算量はよくわからない...(ヒューリスティック探索の計算量って最悪計算量でいいんですかね)

Python

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.helper(board, 0)
        
    def helper(self, board, pos):
      if pos == 81:
        return True
      
      row, col = pos//9, pos%9
      if board[row][col] != '.':
        return self.helper(board, pos+1)
      
      nums = "123456789"
      for num in nums:
        if self.isValid(board, pos, num):
          board[row][col] = num
          if self.helper(board, pos+1):
            return True
          board[row][col] = '.'
          
      return False
    
    def isValid(self, board, pos, candidate):
      row, col = pos//9, pos%9
      for y in range(9):
        if board[y][col] == candidate:
          return False
        
      for x in range(9):
        if board[row][x] == candidate:
          return False
        
      upper_row, upper_col = 3 * (row//3), 3 * (col//3)
      for i in range(9):
        if board[upper_row + i//3][upper_col + i%3] == candidate:
          return False
      
      return True

C++

class Solution {
public:
  void solveSudoku(vector<vector<char>>& board) {
    helper(board, 0);
  }
private:
  bool helper(vector<vector<char>>& board, int pos) {
    if (pos == 81) {
      return true;
    }
    int row = pos / 9, col = pos % 9;
    if (board[row][col] != '.') {
      return helper(board, pos + 1);
    }
    for (int i = 0; i < 9; i++) {
      char candidate = '1' + i;
      if (isValid(board, pos, candidate)) {
        board[row][col] = candidate;
        if (helper(board, pos + 1)) {
          return true;
        }
        board[row][col] = '.';
      }
    }
    return false;
  }
  bool isValid(vector<vector<char>>& board, int pos, char candidate) {
    int row = pos / 9, col = pos % 9;
    for (int y = 0; y < 9; y++) {
      if (board[y][col] == candidate) {
        return false;
      }
    }
    for (int x = 0; x < 9; x++) {
      if (board[row][x] == candidate) {
        return false;
      }
    }
    int upper_row = 3 * (row/3), upper_col = 3 * (col/3);
    for (int i = 0; i < 9; i++) {
      if (board[upper_row + i/3][upper_col + i%3] == candidate) {
        return false;
      }
    }
    return true;
  }
};