最近暇つぶしに数独をするようになっていたのですが、自分で解くのが面倒くさくなってきたのでプログラムに解かせるようにしました。

基本仕様

入力形式

9×9の二次元配列を入力として受け取る。埋まっていないマス目は-1とした。

入力例

board = [
    [-1,  4,  5, -1, -1,  6, -1,  3, -1],
    [-1, -1, -1, -1,  4,  9,  1,  2,  6],
    [-1, -1, -1, -1, -1, -1, -1, -1, -1],
    [-1,  1,  2, -1, -1, -1, -1, -1,  4],
    [ 9, -1, -1, -1,  6,  2, -1, -1, -1],
    [-1,  8,  7, -1, -1, -1, -1, -1,  9],
    [-1, -1, -1, -1, -1, -1, -1, -1, -1],
    [-1, -1, -1, -1,  9,  5,  6,  8,  7],
    [-1,  7,  6, -1, -1,  3, -1,  9, -1]
]
"""
   4 5 |     6 |   3   
       |   4 9 | 1 2 6 
       |       |       
-------+-------+-------
   1 2 |       |     4 
 9     |   6 2 |       
   8 7 |       |     9 
-------+-------+-------
       |       |       
       |   9 5 | 6 8 7 
   7 6 |     3 |   9   
"""

プログラム本体

書きやすさ重視で特にこれといった探索の工夫は行っていないです。ただ、数字を片っ端から入れて、成立するか検討する方式だと組み合わせ数が膨大なので、考慮する候補を少し減らしました。

以下、プログラム本体になります。
solve()の基本動作として、マス目を左上から順番に右下まで見ていき、埋まっていなかったら、入れることが可能な数字の候補を探し、候補の数だけ分岐する深さ優先探索方式にしました。

def solve(board, row, col):
    # find unfilled square
    while col < 9 and board[row][col] != -1:
        if row == 8:
            row = 0
            col += 1
        else:
            row += 1

    # filled
    if col == 9:
        return board
    
    else:
        num_list = check(board, row, col)
        for num in num_list:
            board_copy = copy.deepcopy(board)
            board_copy[row][col] = num
            ans = solve(board_copy, row, col)
            if ans != None:
                return ans
        return None

check()は行、列、箱内でまだ出てきていない数字を探して、それらの数字の配列を返す関数です。

def check(board, row, col):
    flag = [True for i in range(9)]
    num_list = []
    
    if board[row][col] != -1:
        return num_list
    
    for i in range(9):
        # check row 
        if board[row][i] != -1:
            flag[board[row][i]-1] = False
            
        # check col
        if board[i][col] != -1:
            flag[board[i][col]-1] = False
    
    # check box
    for i in range(3):
        for j in range(3):
            col_num = col//3*3+i
            row_num = row//3*3+j
            if board[row_num][col_num] != -1:
                flag[board[row_num][col_num]-1] = False
    
    # convert flag to number list
    for i in range(9):
        if flag[i]:
            num_list.append(i+1)
            
    return num_list

出力結果

上の入力例をそのまま入れた結果、以下のようになりました。

出力例

board_ans = [
    [1, 4, 5, 2, 7, 6, 9, 3, 8],
    [7, 3, 8, 5, 4, 9, 1, 2, 6],
    [2, 6, 9, 8, 3, 1, 4, 7, 5],
    [3, 1, 2, 9, 5, 8, 7, 6, 4],
    [9, 5, 4, 7, 6, 2, 8, 1, 3],
    [6, 8, 7, 3, 1, 4, 2, 5, 9],
    [5, 9, 1, 6, 8, 7, 3, 4, 2],
    [4, 2, 3, 1, 9, 5, 6, 8, 7],
    [8, 7, 6, 4, 2, 3, 5, 9, 1]
]
'''
 1 4 5 | 2 7 6 | 9 3 8 
 7 3 8 | 5 4 9 | 1 2 6 
 2 6 9 | 8 3 1 | 4 7 5 
-------+-------+-------
 3 1 2 | 9 5 8 | 7 6 4 
 9 5 4 | 7 6 2 | 8 1 3 
 6 8 7 | 3 1 4 | 2 5 9 
-------+-------+-------
 5 9 1 | 6 8 7 | 3 4 2 
 4 2 3 | 1 9 5 | 6 8 7 
 8 7 6 | 4 2 3 | 5 9 1 

'''

見た感じ大丈夫そうですね。

終わりに

今回の実装は割と思いつきの突貫工事で行ったので、もしかしたら危ない挙動をするかもしれません。（手元で3例ほどやって解けてたのでまあいいかなあと）もちろん今回の実装は解く上で最適な手法ではないです。例えば、マス目に入れる数字の候補数が少ないものから埋めていったほうが速くなると思います。ですが、実装が長くなりそうだったのでやめました。現在の実装でも日常生活で使う分には、十分な処理時間で終わります。そのあたりの高速化は読者への課題とします。
世の中には数独をグレブナー基底を使って解く猛者もいるようですが、筆者にはまだそれだけの能力はないです。きっと百年後にはできるようになってるでしょう。