Now Loading ...
-
37. Sudoku Solver
출처 : 37. Sudoku Solver
Solution
Python
class Solution(object):
flag = False
# return 값 없이 board 배열 값 자체를 변환해야하는게 목표
def solveSudoku(self, board):
self.back(board, 0, -1)
# 백트래킹으로 탐색해보자
def back(self, board, y, x):
# 마지막 칸을 채운거라면 flag=True
if (x==8) and (y==8):
self.flag = True
return False
# True=뒤에서 제대로 채우지 못해서 탈출 중인 함수라는 뜻
chk2 = False
# 탐색마저 안 끝난 행부터 확인
for nx in range(x+1, 9):
if board[y][nx]==".":
# 빈칸 채웠는지 체크 변수
chk1 = True
for c in range(1, 10):
if self.checkRow(board, y, str(c)) and self.checkCol(board, nx, str(c)) and self.checkBox(board, y, nx, str(c)):
board[y][nx] = str(c)
chk2 = self.back(board, y, nx)
chk1 = False
# 재귀 탈출 시 flag가 True면 "." 으로 안 바꿈
if self.flag: return False
board[y][nx] = "."
if chk1 or chk2: return True
# 끝까지 다 탐색했다면 flag=True
if (y==8) and (nx==8):
self.flag = True
return
# 다음 탐색이 필요한 열 확인 시작
for ny in range(y+1, 9):
for nx in range(9):
if board[ny][nx]==".":
# 빈칸 채웠는지 체크 변수
chk1 = True
for c in range(1, 10):
if self.checkRow(board, ny, str(c)) and self.checkCol(board, nx, str(c)) and self.checkBox(board, ny, nx, str(c)):
board[ny][nx] = str(c)
chk2 = self.back(board, ny, nx)
chk1 = False
# 재귀 탈출 시 flag가 True면 "." 으로 안 바꿈
if self.flag: return False
board[ny][nx] = "."
if chk1 or chk2: return True
# 끝까지 다 탐색했다면 flag=True
if (ny==8) and (nx==8):
self.flag = True
return
# y행에 n이 있는지
def checkRow(self, board, y, n):
if n in board[y]: return False
return True
# x열에 n이 있는지
def checkCol(self, board, x, n):
for i in range(9):
if n == board[i][x]: return False
return True
# (y, x)가 위치한 박스에 n이 있는지
def checkBox(self, board, y, x, n):
yk, xk = y//3, x//3
for ny in range(yk*3, (yk+1)*3):
for nx in range(xk*3, (xk+1)*3):
if n == board[ny][nx]: return False
return True
if __name__ == '__main__':
board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
temp = Solution()
temp.solveSudoku(board)
for row in board: print(*row)
output = [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
The '.' character indicates empty cells.
Example 1:
Input:
board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output:
[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation:
The input board is shown above and the only valid solution is shown below:
Constraints:
board.length == 9
board[i].length == 9
board[i][j] is a digit or '.'.
It is guaranteed that the input board has only one solution.
Touch background to close
kangspa.com
