This code implements a recursive algorithm for solving Sudoku. And I want the result of the doctest to succeed.
The code implementation of the Sudoku algorithm is shown below.
import copy
from doctest import testmod
def solveSudoku2by2(a):
'''
This function returns the depth and tree
for each depth if there is a correct answer.
If it doesn't exist, it returns 'Impossible'.
Example
-------
>>> solveSudoku2by2(a)
[[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 1], [2, 1, 3, 4]]
tree depth, a
1, [[0, 3, 1, 2], [0, 0, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
2, [[4, 3, 1, 2], [0, 0, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
3, [[4, 3, 1, 2], [1, 0, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
4, [[4, 3, 1, 2], [1, 2, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
5, [[4, 3, 1, 2], [1, 2, 4, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
6, [[4, 3, 1, 2], [1, 2, 4, 3], [0, 0, 0, 0], [2, 1, 3, 0]]
7, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 0, 0, 0], [2, 1, 3, 0]]
8, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 0, 0], [2, 1, 3, 0]]
9, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 0], [2, 1, 3, 0]]
10, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 1], [2, 1, 3, 0]]
11, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 1], [2, 1, 3, 4]]
'''
solve(a, 0)
if any(0 in k for k in a):
print('Impossible')
else:
print(a)
print('tree depth, a')
result.sort(key=lambda x:x[0])
for x, y in result:
print(f'{x+1}, {y}')
def solve(a, k):
'''
This function resolves the sudoku received as a parameter and then exits.
'''
if k == 0:
result.append((k, copy.deepcopy(a)))
if k == len(empty_list):
return
else:
x = empty_list[k][0]
y = empty_list[k][1]
for i in range(1, 5):
if columns(x, a, i) and rows(y, a, i) and twoBy2(x, y, a, i):
a[x][y] = i
result.append((k + 1, copy.deepcopy(a)))
solve(a, k+1)
if a[empty_list[-1][0]][empty_list[-1][1]] == 0: # 정답 루트가 아닌 경우
a[x][y] = 0
def columns(x, a, num):
'''
This function receives the current x-coordinate and Sudoku a,
the number of 1 to 4 as parameters, and returns true
if there is a number to put in the column, false if it does not exist.
'''
for i in range(4):
if num == a[x][i]:
return False
return True
def rows(y, a, num):
'''
This function receives the current y-coordinate and Sudoku a,
the number of 1 to 4 as parameters, and returns true
if there is a number to put in the row,
false if it does not exist.
'''
for i in range(4):
if num == a[i][y]:
return False
return True
def twoBy2(x, y, a, num):
'''
This function receives the current x and y coordinates and Sudoku a,
the number of 1 to 4 as parameters, and returns true
if there is a number to put in the coordinate base 2x2,
false if it does not exist.
'''
dx = x // 2 * 2
dy = y // 2 * 2
for i in range(2):
for j in range(2):
if num == a[dx + i][dy + j]:
return False
return True
def make_empty_list(a):
'''
This function creates a list
with the coordinates of the empty cells of Sudoku as tuple elements and returns it.
'''
empty_list = []
for i in range(4):
for j in range(4):
if a[i][j] == 0:
empty_list.append((i, j))
return empty_list
if __name__ == '__main__':
a = [[0, 3, 1, 2], [0, 0, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
# a = [[0,2,1,3], [0,0,0,0], [0,0,0,0],[2,1,3,0]]
result = []
empty_list = make_empty_list(a)
solveSudoku2by2(a)
testmod()
The output result of the code excluding the testmod module is as follows.
[[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 1], [2, 1, 3, 4]]
tree depth, a
1, [[0, 3, 1, 2], [0, 0, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
2, [[4, 3, 1, 2], [0, 0, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
3, [[4, 3, 1, 2], [1, 0, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
4, [[4, 3, 1, 2], [1, 2, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
5, [[4, 3, 1, 2], [1, 2, 4, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
6, [[4, 3, 1, 2], [1, 2, 4, 3], [0, 0, 0, 0], [2, 1, 3, 0]]
7, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 0, 0, 0], [2, 1, 3, 0]]
8, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 0, 0], [2, 1, 3, 0]]
9, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 0], [2, 1, 3, 0]]
10, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 1], [2, 1, 3, 0]]
11, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 1], [2, 1, 3, 4]]
And the result of the doctest is below.
Failed example:
solveSudoku2by2(a)
Expected:
[[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 1], [2, 1, 3, 4]]
tree depth, a
1, [[0, 3, 1, 2], [0, 0, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
2, [[4, 3, 1, 2], [0, 0, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
3, [[4, 3, 1, 2], [1, 0, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
4, [[4, 3, 1, 2], [1, 2, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
5, [[4, 3, 1, 2], [1, 2, 4, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
6, [[4, 3, 1, 2], [1, 2, 4, 3], [0, 0, 0, 0], [2, 1, 3, 0]]
7, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 0, 0, 0], [2, 1, 3, 0]]
8, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 0, 0], [2, 1, 3, 0]]
9, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 0], [2, 1, 3, 0]]
10, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 1], [2, 1, 3, 0]]
11, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 1], [2, 1, 3, 4]]
Got:
[[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 1], [2, 1, 3, 4]]
tree depth, a
1, [[0, 3, 1, 2], [0, 0, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
1, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 1], [2, 1, 3, 4]]
2, [[4, 3, 1, 2], [0, 0, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
3, [[4, 3, 1, 2], [1, 0, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
4, [[4, 3, 1, 2], [1, 2, 0, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
5, [[4, 3, 1, 2], [1, 2, 4, 0], [0, 0, 0, 0], [2, 1, 3, 0]]
6, [[4, 3, 1, 2], [1, 2, 4, 3], [0, 0, 0, 0], [2, 1, 3, 0]]
7, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 0, 0, 0], [2, 1, 3, 0]]
8, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 0, 0], [2, 1, 3, 0]]
9, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 0], [2, 1, 3, 0]]
10, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 1], [2, 1, 3, 0]]
11, [[4, 3, 1, 2], [1, 2, 4, 3], [3, 4, 2, 1], [2, 1, 3, 4]]
**********************************************************************
1 items had failures:
1 of 1 in __main__.solveSudoku2by2
***Test Failed*** 1 failures.
I wonder why the expected value and got value in doctest are different. What part is wrong?
