Help us understand the problem. What is going on with this article?

Python3を使って数独を解く

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

基本仕様

入力形式

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

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away