基礎的な数独ソルバーの解説

# 数独ソルバーのコード解説
はじめてQiitaで記事を書きました。  
構成や説明が下手っぴかもしれませんが、最後まで読んでもらえると嬉しいです。
## 概要
[『問題解決のPythonプログラミング　数学パズルで鍛えるアルゴリズム的思考』](https://www.oreilly.co.jp/books/9784873118512/)  
14章　数独は二度とごめんだ  
この本の日本語訳が少し分かりにくかったので、自分なりに解説してみようと思います。
## 前置き
### この本について
この本は、『Programming for the Puzzled: 
Learn to Program While Solving Puzzles』の翻訳書です。  
その本は、著者がMITで行なっていた、プログラミング基礎の授業を元にして書かれているそうです。  
その授業の動画やPDF、ソースコードは、無料で閲覧できます。やったね👍  
https://ocw.mit.edu/courses/6-s095-programming-for-the-puzzled-january-iap-2018/  

### 想定する読者
- この本の14章のプログラムについて理解を深めたい人
- 基本的な数独ソルバーに興味がある人
- Python初心者（基本的な文法がわかる人）
- 私

### この記事について
本に記載されているソースコードは、[こちら](https://ocw.mit.edu/courses/6-s095-programming-for-the-puzzled-january-iap-2018/pages/puzzle-8-you-wont-want-to-play-sudoku-again/)からダウンロードできます。  
私は、本を読みつつ、IDEでコードを動かしてデバッグモードで1行ずつ動きを追ったら、正確な理解ができました。  
その記録を残しておき、忘れた頃に追体験できるように記事を書いています。  
（このソースコードと本を読めば、Pyhonに慣れている人なら動作原理はすぐにわかると思いますが。）
## ソースコードの簡単な説明
ソースコードに、分かりやすいようにコメントをつけました。（しつこいほど）
### 定義されている関数の一覧
  - solveSudoku()
  - findNextCellToFill()
  - isValid()
  - printSudoku()
```python:
def solveSudoku(grid, i=0, j=0):    # 最上位ルーチン
    global backtracks   # 再帰呼び出しを超えて変数の状態を保持する
    i, j = findNextCellToFill(grid)  # 次の空白マスを見つける
    if i == -1:         # 空白マスがなければ、
        return True     # 数独が解けた合図！（呼び出し元にTrueが返る）
    for e in range(1, 10):  # 空白マスに数字を入れていく
        if isValid(grid, i, j, e):  # 入れる数字がルールに違反していないか
            grid[i][j] = e  # 実際に数字を入れる
            if solveSudoku(grid, i, j):     # 再帰呼び出し
                return True  # 呼び出し元にTrueが返る
            backtracks += 1  # solveSudoku()がFalseを返したら実行
            grid[i][j] = 0  # 入れた数字を消して空白マスに戻す
    return False    # 空白マスに入る数字がなかった！(呼び出し元にFalseが返る)

def findNextCellToFill(grid):   # 次の空白マスを見つける
    for x in range(0, 9):
        for y in range(0, 9):
            if grid[x][y] == 0:  # 空白マスを見つけたら、
                return x, y     # そのマスの位置を返す
    return -1, -1   # 次の空白マスはなかった！

def isValid(grid, i, j, e):     # 数独のルールに違反していないかチェックする
    rowOk = all([e != grid[i][x] for x in range(9)])    # 入れた数字eがその行にないか調べる
    if rowOk:
        columnOk = all([e != grid[x][j] for x in range(9)])  # 入れた数字eがその列にないか調べる
        if columnOk:
            secTopX, secTopY = 3 * (i // 3), 3 * (j // 3)   # そのブロックの初めの行番号、列番号を取得
            for x in range(secTopX, secTopX + 3):
                for y in range(secTopY, secTopY + 3):
                    if grid[x][y] == e:     # そのブロックに、入れた数字eがあったら、
                        return False        # ルールに違反！
            return True
    return False    # 行と列に、入れた数字eがあった。ルールに違反！

def printSudoku(grid):      # 数独の答えを見やすいように出力する
    numrow = 0
    for row in grid:
        if numrow % 3 == 0 and numrow != 0:
            print(" ")  # 上・中・下のブロックの間に改行を入れる
        print(row[0:3], " ", row[3:6], " ", row[6:9])
        numrow += 1
```
### 入力と実行
- 入力であるinputは、2次元配列で構成されています。空白は、0で表します。
- inputは、本に記載のものは使わずに、簡単な数独パズルを使います。（説明を簡潔にするため）
- solveSudoku()で数独パズルを解き、printSudoku()で答えを表示します。
```python:
input = [[0, 0, 0, 5, 3, 1, 6, 0, 9],
         [9, 0, 6, 4, 8, 0, 0, 0, 0],
         [3, 0, 4, 0, 0, 2, 0, 5, 8],
         [7, 6, 5, 0, 1, 0, 3, 8, 4],
         [1, 3, 9, 7, 4, 8, 0, 0, 6],
         [0, 0, 8, 0, 0, 0, 0, 1, 0],
         [0, 8, 3, 0, 0, 0, 1, 6, 5],
         [0, 4, 7, 1, 6, 0, 0, 9, 2],
         [0, 9, 0, 0, 2, 0, 4, 0, 0]]

solveSudoku(input)
printSudoku(input)
```
### 出力
- 数独パズルの答えが出力されました！
- これで数独パズルを自動で解くことができました😃

```
[8, 7, 2]   [5, 3, 1]   [6, 4, 9]
[9, 5, 6]   [4, 8, 7]   [2, 3, 1]
[3, 1, 4]   [6, 9, 2]   [7, 5, 8]
 
[7, 6, 5]   [2, 1, 9]   [3, 8, 4]
[1, 3, 9]   [7, 4, 8]   [5, 2, 6]
[4, 2, 8]   [3, 5, 6]   [9, 1, 7]
 
[2, 8, 3]   [9, 7, 4]   [1, 6, 5]
[5, 4, 7]   [1, 6, 3]   [8, 9, 2]
[6, 9, 1]   [8, 2, 5]   [4, 7, 3]
```
## 詳しい説明
### プログラムの流れ
メインルーチン
- 空白マスを探す
- （見つけたら）1-9の数字を当てはめる
- （空白マスがなかったら）Trueを返す
  - 数独のルールに違反していないかチェックする
    - （違反していたら）次の数字へ
    - （違反してなかったら）空白マスに数字を入れる
    - メインルーチンを呼び出す（再帰）
    - （呼び出し先からTrueが返ってきたら）Trueを返す
    - （呼び出し先からFalseが返ってきたら、以下を実行）
    - やり直し回数+1
    - 入れた数字を消して、空白マスに戻す
- （空白マスに入る数字がなかったら）Falseを返す
### プログラムの実行過程を見る
この入力だと、やり直し回数（変数backtracks）が8回になります。  
backtracksが8回になるまでの過程をこれから説明します。  
各数独パズルの図は、backtracksが+1された瞬間を表示しています。
#### backtracks == 0
入力であるinputです。
```
   0  1  2     3  4  5     6  7  8

0 [0, 0, 0]   [5, 3, 1]   [6, 0, 9]
1 [9, 0, 6]   [4, 8, 0]   [0, 0, 0]
2 [3, 0, 4]   [0, 0, 2]   [0, 5, 8]
 
3 [7, 6, 5]   [0, 1, 0]   [3, 8, 4]
4 [1, 3, 9]   [7, 4, 8]   [0, 0, 6]
5 [0, 0, 8]   [0, 0, 0]   [0, 1, 0]
 
6 [0, 8, 3]   [0, 0, 0]   [1, 6, 5]
7 [0, 4, 7]   [1, 6, 0]   [0, 9, 2]
8 [0, 9, 0]   [0, 2, 0]   [4, 0, 0]
```
#### backtracks == 1
```
   0  1  2     3  4  5     6  7  8

0 [2, 7, 0]   [5, 3, 1]   [6, 0, 9]
1 [9, 0, 6]   [4, 8, 0]   [0, 0, 0]
2 [3, 0, 4]   [0, 0, 2]   [0, 5, 8]
 
3 [7, 6, 5]   [0, 1, 0]   [3, 8, 4]
4 [1, 3, 9]   [7, 4, 8]   [0, 0, 6]
5 [0, 0, 8]   [0, 0, 0]   [0, 1, 0]
 
6 [0, 8, 3]   [0, 0, 0]   [1, 6, 5]
7 [0, 4, 7]   [1, 6, 0]   [0, 9, 2]
8 [0, 9, 0]   [0, 2, 0]   [4, 0, 0]
```
[0, 0]に2、[0, 1]に7を入れました。  
その後、[0, 2]に数字が入らないことを確認したため、やり直しが必要です。
```
solveSudoku(grid, 0, 0)
    solveSudoku(grid, 0, 1)
        solveSudoku(grid, 0, 2) -> False
```
#### backtracks == 2
```
   0  1  2     3  4  5     6  7  8

0 [2, 0, 0]   [5, 3, 1]   [6, 0, 9]
1 [9, 0, 6]   [4, 8, 0]   [0, 0, 0]
2 [3, 0, 4]   [0, 0, 2]   [0, 5, 8]
 
3 [7, 6, 5]   [0, 1, 0]   [3, 8, 4]
4 [1, 3, 9]   [7, 4, 8]   [0, 0, 6]
5 [0, 0, 8]   [0, 0, 0]   [0, 1, 0]
 
6 [0, 8, 3]   [0, 0, 0]   [1, 6, 5]
7 [0, 4, 7]   [1, 6, 0]   [0, 9, 2]
8 [0, 9, 0]   [0, 2, 0]   [4, 0, 0]
```
前回、solveSudoku(grid, 0, 2)の返り値がFalseだったため、solveSudoku(grid, 0, 1)の途中からコードを実行しました。  
[0, 1]に8以降の数字を当てはめましたが、入る数字はなかったようです。やり直しが必要です。

```
solveSudoku(grid, 0, 0)
    solveSudoku(grid, 0, 1) -> False
```
#### backtracks == 3
```
   0  1  2     3  4  5     6  7  8

0 [8, 2, 0]   [5, 3, 1]   [6, 0, 9]
1 [9, 0, 6]   [4, 8, 0]   [0, 0, 0]
2 [3, 0, 4]   [0, 0, 2]   [0, 5, 8]
 
3 [7, 6, 5]   [0, 1, 0]   [3, 8, 4]
4 [1, 3, 9]   [7, 4, 8]   [0, 0, 6]
5 [0, 0, 8]   [0, 0, 0]   [0, 1, 0]
 
6 [0, 8, 3]   [0, 0, 0]   [1, 6, 5]
7 [0, 4, 7]   [1, 6, 0]   [0, 9, 2]
8 [0, 9, 0]   [0, 2, 0]   [4, 0, 0]
```
前回、solveSudoku(grid, 0, 1)の返り値がFalseだったため、solveSudoku(grid, 0, 0)の途中からコードを実行しました。  
[0, 0]に8、[0, 1]に2を入れました。  
その後、[0, 2]に数字が入らないことを確認したため、やり直しが必要です。
```
solveSudoku(grid, 0, 0)
    solveSudoku(grid, 0, 1)
        solveSudoku(grid, 0, 2) -> False
```
#### backtracks == 4
```
   0  1  2     3  4  5     6  7  8

0 [8, 7, 2]   [5, 3, 1]   [6, 4, 9]
1 [9, 1, 6]   [4, 8, 7]   [2, 3, 0]
2 [3, 0, 4]   [0, 0, 2]   [0, 5, 8]
 
3 [7, 6, 5]   [0, 1, 0]   [3, 8, 4]
4 [1, 3, 9]   [7, 4, 8]   [0, 0, 6]
5 [0, 0, 8]   [0, 0, 0]   [0, 1, 0]
 
6 [0, 8, 3]   [0, 0, 0]   [1, 6, 5]
7 [0, 4, 7]   [1, 6, 0]   [0, 9, 2]
8 [0, 9, 0]   [0, 2, 0]   [4, 0, 0]
```
前回、solveSudoku(grid, 0, 2)の返り値がFalseだったため、solveSudoku(grid, 0, 1)の途中からコードを実行しました。  
[0, 1]-> 7、[0, 1]->2、・・・（中略）[1, 6]-> 2、[1, 7]-> 3　という感じで数字を入れました。  
その後、[1, 8]に数字が入らないことを確認したため、やり直しが必要です。
```
solveSudoku(grid, 0, 0)
    solveSudoku(grid, 0, 1)
        solveSudoku(grid, 0, 2)
            ・・・
                solveSudoku(grid, 1, 8) -> False
```
#### backtracks == 5
```
   0  1  2     3  4  5     6  7  8

0 [8, 7, 2]   [5, 3, 1]   [6, 4, 9]
1 [9, 1, 6]   [4, 8, 7]   [2, 0, 0]
2 [3, 0, 4]   [0, 0, 2]   [0, 5, 8]
 
3 [7, 6, 5]   [0, 1, 0]   [3, 8, 4]
4 [1, 3, 9]   [7, 4, 8]   [0, 0, 6]
5 [0, 0, 8]   [0, 0, 0]   [0, 1, 0]
 
6 [0, 8, 3]   [0, 0, 0]   [1, 6, 5]
7 [0, 4, 7]   [1, 6, 0]   [0, 9, 2]
8 [0, 9, 0]   [0, 2, 0]   [4, 0, 0]
```
前回、solveSudoku(grid, 1, 8)の返り値がFalseだったため、solveSudoku(grid, 1, 7)の途中からコードを実行しました。  
[1, 7]に4以降の数字を当てはめましたが、入る数字はなかったようです。やり直しが必要です。
```
solveSudoku(grid, 0, 0)
    solveSudoku(grid, 0, 1)
        solveSudoku(grid, 0, 2)
            ・・・
                solveSudoku(grid, 1, 7) -> False
```
#### backtracks == 6
```
   0  1  2     3  4  5     6  7  8
   
0 [8, 7, 2]   [5, 3, 1]   [6, 4, 9]
1 [9, 1, 6]   [4, 8, 7]   [0, 0, 0]
2 [3, 0, 4]   [0, 0, 2]   [0, 5, 8]
 
3 [7, 6, 5]   [0, 1, 0]   [3, 8, 4]
4 [1, 3, 9]   [7, 4, 8]   [0, 0, 6]
5 [0, 0, 8]   [0, 0, 0]   [0, 1, 0]
 
6 [0, 8, 3]   [0, 0, 0]   [1, 6, 5]
7 [0, 4, 7]   [1, 6, 0]   [0, 9, 2]
8 [0, 9, 0]   [0, 2, 0]   [4, 0, 0]
```
前回、solveSudoku(grid, 1, 7)の返り値がFalseだったため、solveSudoku(grid, 1, 6)の途中からコードを実行しました。  
[1, 6]に3以降の数字を当てはめましたが、入る数字はなかったようです。やり直しが必要です。
```
solveSudoku(grid, 0, 0)
    solveSudoku(grid, 0, 1)
        solveSudoku(grid, 0, 2)
            ・・・
                solveSudoku(grid, 1, 6) -> False
```
#### backtracks == 7
```
   0  1  2     3  4  5     6  7  8

0 [8, 7, 2]   [5, 3, 1]   [6, 4, 9]
1 [9, 1, 6]   [4, 8, 0]   [0, 0, 0]
2 [3, 0, 4]   [0, 0, 2]   [0, 5, 8]
 
3 [7, 6, 5]   [0, 1, 0]   [3, 8, 4]
4 [1, 3, 9]   [7, 4, 8]   [0, 0, 6]
5 [0, 0, 8]   [0, 0, 0]   [0, 1, 0]
 
6 [0, 8, 3]   [0, 0, 0]   [1, 6, 5]
7 [0, 4, 7]   [1, 6, 0]   [0, 9, 2]
8 [0, 9, 0]   [0, 2, 0]   [4, 0, 0]
```
前回、solveSudoku(grid, 1, 6)の返り値がFalseだったため、solveSudoku(grid, 1, 5)の途中からコードを実行しました。  
[1, 5]に8以降の数字を当てはめましたが、入る数字はなかったようです。やり直しが必要です。
```
solveSudoku(grid, 0, 0)
    solveSudoku(grid, 0, 1)
        solveSudoku(grid, 0, 2)
            ・・・
                solveSudoku(grid, 1, 5) -> False
```
#### backtracks == 8
```
   0  1  2     3  4  5     6  7  8

0 [8, 7, 2]   [5, 3, 1]   [6, 4, 9]
1 [9, 5, 6]   [4, 8, 7]   [2, 3, 1]
2 [3, 1, 4]   [6, 9, 2]   [7, 5, 8]
 
3 [7, 6, 5]   [2, 1, 9]   [3, 8, 4]
4 [1, 3, 9]   [7, 4, 8]   [5, 2, 6]
5 [2, 0, 8]   [0, 0, 0]   [0, 1, 0]
 
6 [0, 8, 3]   [0, 0, 0]   [1, 6, 5]
7 [0, 4, 7]   [1, 6, 0]   [0, 9, 2]
8 [0, 9, 0]   [0, 2, 0]   [4, 0, 0]
```
前回、solveSudoku(grid, 1, 5)の返り値がFalseだったため、solveSudoku(grid, 1, 1)の途中からコードを実行しました。  
[1, 1]-> 5、[1, 5]-> 7、・・・（中略）[5, 0]-> 2　という感じで数字を入れました。  
その後、[5, 1]に数字が入らないことを確認したため、やり直しが必要です。
```
solveSudoku(grid, 0, 0)
    solveSudoku(grid, 0, 1)
        solveSudoku(grid, 0, 2)
            ・・・
                solveSudoku(grid, 5, 0)
                    solveSudoku(grid, 5, 1) -> False
```
#### 数独パズルの完成
```
   0  1  2     3  4  5     6  7  8

0 [8, 7, 2]   [5, 3, 1]   [6, 4, 9]
1 [9, 5, 6]   [4, 8, 7]   [2, 3, 1]
2 [3, 1, 4]   [6, 9, 2]   [7, 5, 8]
 
3 [7, 6, 5]   [2, 1, 9]   [3, 8, 4]
4 [1, 3, 9]   [7, 4, 8]   [5, 2, 6]
5 [4, 2, 8]   [3, 5, 6]   [9, 1, 7]
 
6 [2, 8, 3]   [9, 7, 4]   [1, 6, 5]
7 [5, 4, 7]   [1, 6, 3]   [8, 9, 2]
8 [6, 9, 1]   [8, 2, 5]   [4, 7, 3]
```
前回、solveSudoku(grid, 5, 1)の返り値がFalseだったため、solveSudoku(grid, 5, 0)の途中からコードを実行しました。  
その後、やり直しは発生せず、答えを出力できました。
```
solveSudoku(grid, 0, 0) -> True
    solveSudoku(grid, 0, 1) -> True
        solveSudoku(grid, 0, 2) -> True
            ・・・
                solveSudoku(grid, 5, 0) -> True
                    ・・・
                        solveSudoku(grid, 8, 7) -> True
                            solveSudoku(grid, 8, 8) -> True
```
上の図は、呼び出し先から呼び出し元へ、Trueが順に帰っていく様子を示しています。
## 参考記事
執筆にあたり参考にした記事を紹介します。非常に助かりました😊
- [VSCodeで始めるMarkdown入門](https://qiita.com/ourinhu269/items/af1e2b4d7fb71a78aef3)
- [君はVS Codeのデバッグの知られざる機能について知っているか](https://qiita.com/_ken_/items/c5aa4841be74b06530b4)
## 終わりに
何とか、solveSudoku()の解説をすることができました。  
Python初心者向けに細かく書いたので、冗長すぎたかもしれません。  
意欲が続けば、最適化されたバージョンのsolveSudokuOpt()の解説もしたいと思います。
誤字・脱字・明らかな間違いがありましたら、ぜひ教えてください。  

**ここまで読んでいただきありがとうございました。**