LoginSignup
1
2
@nabe_boy

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

Last updated at Posted at 2024-04-13

数独ソルバーのコード解説

はじめてQiitaで記事を書きました。
構成や説明が下手っぴかもしれませんが、最後まで読んでもらえると嬉しいです。

概要

『問題解決のPythonプログラミング　数学パズルで鍛えるアルゴリズム的思考』
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初心者（基本的な文法がわかる人）
  • 私

この記事について

本に記載されているソースコードは、こちらからダウンロードできます。
私は、本を読みつつ、IDEでコードを動かしてデバッグモードで1行ずつ動きを追ったら、正確な理解ができました。
その記録を残しておき、忘れた頃に追体験できるように記事を書いています。
（このソースコードと本を読めば、Pyhonに慣れている人なら動作原理はすぐにわかると思いますが。）

ソースコードの簡単な説明

ソースコードに、分かりやすいようにコメントをつけました。（しつこいほど）

定義されている関数の一覧

  • solveSudoku()
  • findNextCellToFill()
  • isValid()
  • printSudoku()
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()で答えを表示します。
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が順に帰っていく様子を示しています。

参考記事

執筆にあたり参考にした記事を紹介します。非常に助かりました😊

終わりに

何とか、solveSudoku()の解説をすることができました。
Python初心者向けに細かく書いたので、冗長すぎたかもしれません。
意欲が続けば、最適化されたバージョンのsolveSudokuOpt()の解説もしたいと思います。
誤字・脱字・明らかな間違いがありましたら、ぜひ教えてください。

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

1
2
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
2