[Algorithm] - 알고리즘 : 스도쿠

16 Dec 2020 in Algorithm on Algorithm

Joma class python에서 마지막 문제가 스도쿠 backtracking 문제였다.

단순히 재귀함수를 이용해 스도쿠 판을 채우는 문제였는데 오랜만에 풀어서 조금 시간이 걸렸다.

재귀에는 항상 탈출 조건이 있어야 한다. (해결이던 실패던)

스도쿠 조건

해결 조건

모든 보드가 다 채워져야 한다
- 총 합이 405이어야 한다. (아니면 실패)
3가지 조건을 모두 만족하여야 한다.
- 열에 숫자가 1~9까지 다 들어가 있어야 한다
- 행에 숫자가 1~9까지 다 들어가 있어야 한다
- 3X3칸에 숫자가 1~9까지 다 들어가 있어야 한다

재귀로 이걸 해결해보자.

def solve_helper(board, pos_y, pos_x):
	...

조건 체크

보드가 채워졌는지?

total = 0
isFill = True # True면 판이 다 채워진것

for col in range(len(board)):
	for row in range(len(board[0])):
		if board[col][row] == 0 : # 비어 있으면
			isFill = False
		total += board[col][row]

# 조건 완료 (다 채워짐)
if isFill:
	if total == 405:
		return board
	else:
		return None

보드 범위 벗어남

# 2. 보드 범위 벗어남 9*9
# 0 <= pos_x <= 8
if pos_x > len(board[0]):
  return None
# 0 <= pos_y <= 8
if pos_y > len(board):
  return None

재귀 반복부

해당 칸의 가능한 숫자 찾기

행과 열, 그리고 3x3칸에 중복된 숫자를 제거하는 방식으로 해보자

# 반복부
# 3. 해당칸 숫자 범위 찾기
nums = [1,2,3,4,5,6,7,8,9]
# 3-1. 행에서 있는 숫자 빼기
for col in range(len(board)):
  if board[col][pos_x] != 0 and board[col][pos_x] in nums:
    nums.remove(board[col][pos_x])

# 3-2. 열에서 있는 숫자 빼기
for row in range(len(board[0])):
  if board[pos_y][row] != 0 and board[pos_y][row] in nums:
    nums.remove(board[pos_y][row])

# 3-3. 3x3에 있는 숫자 빼기
# 현재 내가 있는 칸의 위치
# 0,1,2 => 0
# 3,4,5 => 1
# 6,7,8 => 2
section_x = int(pos_x / 3)
section_y = int(pos_y / 3)

for row in range(3):
  for col in range(3):
    if board[section_y*3 + col][section_x*3 + row] != 0 and board[section_y*3 + col][section_x*3 + row] in nums:
      nums.remove(board[section_y*3 + col][section_x*3 + row])

# 4. 가능한 숫자가 없으면 None
if len(nums) < 1:
  return None

다음 칸 찾기

채울 숫자를 찾았으니 다음 숫자를 채울 칸을 찾아보자

next_y = pos_y
next_x = pos_x

row_count = pos_x + 1

# 5. 다음 칸 찾기
for col in range(pos_y, 9):
  for row in range(row_count, 9):
    print(f'finding... {col} {row}')
    if board[col][row] == 0:
      print(f'찾았다! 다음 숫자!!')
      next_y = col
      next_x = row
      break
  else:
    row_count = 0
    continue
  break

재귀 반복 부

가능한 숫자를 넣고 재귀를 진행

# 5. 가능한 숫자가 있으면 숫자들 넣으며 재귀
for num in nums:
  # 숫자 넣기
  board[pos_y][pos_x] = num
  # 다음 칸 찾기
  new_board = solve_helper(board, next_y, next_x)
  if new_board is not None:
    return new_board

  board[pos_y][pos_x] = 0

return None

진행 이미지

열심히 반복하더니 정답을 찾아냈다.