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

# 基本仕様

## 入力形式

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

'''
```

# 終わりに

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