스도쿠 솔버 파이썬
스도쿠는 논리와 추리를 사랑하는 사람들에게 가장 인기 있는 논리 기반의 숫자 배치 퍼즐 게임입니다. 스도쿠 퍼즐을 푸는 것은 두뇌가 집중력과 논리적 사고를 향상시키는 데 도움이 됩니다.
이 기사에서는 Python을 사용하여 스도쿠를 해결하는 방법을 설명합니다.
Python에서 역추적 알고리즘을 사용하여 스도쿠 해결
계산 문제에 대한 솔루션을 찾을 때 역추적 알고리즘은 우리가 자주 사용하는 기술입니다. 스도쿠를 푸는 동안 채워진 상자의 숫자가 유효한지 여부를 확인합니다.
유효하지 않으면 1에서 9까지의 다른 숫자를 확인합니다. 유효한 숫자를 찾지 못하면 이전 옵션으로 되돌아갑니다.
우리가 막다른 길에 도달하고 이전 선택으로 돌아갈 때, 우리는 선택을 했고, 선택을 변경하여 다른 가능한 해결책을 얻게 됩니다.
역추적 알고리즘과 함께 스도쿠 솔버를 구현하는 방법을 살펴보겠습니다.
먼저 퍼즐을 형성하여 보드를 설정해야 합니다.
def setBoardFunc(puz):
global grid
print("\n---------------Sudoku Solver---------------\n")
print("Here is the Sudoku Problem :")
for i in range(0, len(puz), 9):
row = puz[i : i + 9]
temp = []
for block in row:
temp.append(int(block))
grid.append(temp)
printGridFunc()
여기에서는 퍼즐을 형성하기 위해 setBoardFunc()라는 함수를 정의했습니다. 반복하는 동안 9x9 퍼즐을 설정하고 빈 셀을 0으로 초기화합니다.
함수의 작업을 완료한 후 puz에 입력된 내용을 인쇄합니다. 그런 다음 그리드를 인쇄해야 합니다. 이 단계는 주어진 입력으로 9x9 그리드를 인쇄합니다.
def printGridFunc():
global grid
for row in grid:
print(row)
다음으로 현재 값이 현재 상자 내에 배치될 수 있는지 확인합니다.
def checkValidFunc(row, column, num):
global grid
for i in range(0, 9):
if grid[row][i] == num:
return False
for i in range(0, 9):
if grid[i][column] == num:
return False
square_row = (row // 3) * 3
square_col = (column // 3) * 3
for i in range(0, 3):
for j in range(0, 3):
if grid[square_row + i][square_col + j] == num:
return False
return True
이 단계는 주어진 번호가 특정 상자에 유효한지 확인합니다. 번호는 현재 위치에 배치할 동일한 행, 열 또는 블록 상자의 상자 중 어느 것도 아니어야 합니다.
숫자가 해당 요구 사항을 충족하고 true를 반환하면 다음 값으로 이동할 수 있습니다. 그렇지 않으면 번호가 거부됩니다. 그런 다음 역추적 알고리즘에 맞게 모든 블록을 통과해야 합니다.
def solveFunc():
global grid
for row in range(9):
for column in range(9):
if grid[row][column] == 0:
for num in range(1, 10):
if checkValidFunc(row, column, num):
grid[row][column] = num
solveFunc()
grid[row][column] = 0
return
print("\nSolution for the Sudoku Problem: ")
printGridFunc()
이 코드 청크의 후반부는 숫자가 유효한지 여부를 확인합니다. 여기에 함수 역추적 알고리즘을 도입했습니다.
처음에는 빈 셀을 검색합니다. 발견되면 해결된 스도쿠가 있고 주어진 스도쿠의 솔루션을 출력합니다. 빈 상자를 찾으면 반복을 통해 1에서 9까지의 숫자를 추측합니다.
유효한 숫자가 있으면 solveFunc()를 호출하고 다음 빈 셀로 이동하지만 추측이 유효하지 않으면 함수의 이전 호출은 셀의 값을 0으로 재설정하고 계속합니다. 다음 유효한 숫자를 찾기 위해 반복합니다.
알고리즘이 막다른 골목까지 유효한 숫자로 빈 상자를 채우면 프로세스를 역추적하고 전체 프로세스를 반복합니다. 마지막으로 그리드를 통과하고 함수를 호출하여 주어진 스도쿠를 풀어봅시다.
puz = (
"004300209005009001070060043006002087190007400050083000600000105003508690042910300"
)
grid = []
setBoardFunc(puz)
solveFunc()
완전한 소스 코드:
def setBoardFunc(puz):
global grid
print("\n---------------Sudoku Solver---------------\n")
print("Here is the Sudoku Problem :")
for i in range(0, len(puz), 9):
row = puz[i : i + 9]
temp = []
for block in row:
temp.append(int(block))
grid.append(temp)
printGridFunc()
def printGridFunc():
global grid
for row in grid:
print(row)
def checkValidFunc(row, column, num):
global grid
for i in range(0, 9):
if grid[row][i] == num:
return False
for i in range(0, 9):
if grid[i][column] == num:
return False
square_row = (row // 3) * 3
square_col = (column // 3) * 3
for i in range(0, 3):
for j in range(0, 3):
if grid[square_row + i][square_col + j] == num:
return False
return True
def solveFunc():
global grid
for row in range(9):
for column in range(9):
if grid[row][column] == 0:
for num in range(1, 10):
if checkValidFunc(row, column, num):
grid[row][column] = num
solveFunc()
grid[row][column] = 0
return
print("\nSolution for the Sudoku Problem: ")
printGridFunc()
puz = (
"004300209005009001070060043006002087190007400050083000600000105003508690042910300"
)
grid = []
setBoardFunc(puz)
solveFunc()
출력:
결론
더 많은 풀이 방법이 있지만 역추적 알고리즘을 사용하면 스도쿠의 최종 출력이 더 정확해지지만 많은 반복으로 구성되어 있기 때문에 시간이 더 걸립니다. 그러나 스도쿠 퍼즐을 푸는 것은 사람의 논리적 사고를 향상시키고 여가 시간을 보내는 흥미로운 방법입니다.
Nimesha is a Full-stack Software Engineer for more than five years, he loves technology, as technology has the power to solve our many problems within just a minute. He have been contributing to various projects over the last 5+ years and working with almost all the so-called 03 tiers(DB, M-Tier, and Client). Recently, he has started working with DevOps technologies such as Azure administration, Kubernetes, Terraform automation, and Bash scripting as well.