백준(baekjoon) 2580번: 스도쿠(골드 4, 파이썬 PYTHON) - 백트래킹

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

 

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

 

import sys

sudoku=[]

for _ in range(9):
  sudoku_line=list(map(int,sys.stdin.readline().split()))
  sudoku.append(sudoku_line)

def promising(num,row,col):
  global sudoku
  for x in range(9):
    if(num==sudoku[row][x] or num==sudoku[x][col]):  
      return False 
  for x in range(row-row%3,row-row%3+3):  
    for y in range(col-col%3,col-col%3+3):
      if(num==sudoku[x][y]):  
        return False 
  return True  
    
def backtracking_sudoku(row,col):  
  global sudoku
  if(row==9):  
    for x in sudoku:
      print(*x) 
    exit(0) 
  else:  
    if(sudoku[row][col]==0):  
      for num in range(1,10): 
        if(promising(num,row,col)==True): 
          sudoku[row][col]=num  
          if(col+1==9): 
            backtracking_sudoku(row+1,0)  
          else: 
            backtracking_sudoku(row,col+1) 
          sudoku[row][col]=0 
    else: 
      if(col+1==9): 
        backtracking_sudoku(row+1,0)  
      else: 
        backtracking_sudoku(row,col+1) 
        
backtracking_sudoku(0,0)

 

※ 백트래킹

 

 

● 먼저 sudoku 배열에 입력되는 스도쿠를 저장해준다.( 입력받는 각 줄은 sudoku_line 이라는 배열에 입력받고, 각 sudoku_line을 sudoku에 append 시키므로 sudoku 배열은 2차원 배열이 된다. ) 그 후 스도쿠의 각 칸을 탐색해준다.

 

먼저 backtracking_sudoku 함수를 정의해주자.

 

● backtracking_sudoku 함수는 매개변수로 row와 col을 받고, 각 값은 현재 탐색을 진행할 스도쿠 칸의 행과 열의 인덱스를 나타낸다.

 

● 만약 row 값이 9 라면 즉, 행 인덱스가 9라는 것이고 스도쿠 행의 인덱스는 8까지 있으므로 탐색이 끝났음을 의미하므로 현재 만들어진 스도쿠를 출력한 뒤 exit(0)을 통해 프로그램을 종료시킨다.

 

● 아직 탐색해야 할 칸이 남아있고 현재 탐색하는 스도쿠 칸의 값이 0일 시, 고려할 수 있는 숫자 1부터 9까지를 돌며 각 숫자와 현재 row, col 값을 promising 함수에 넘겨 True를 return 받으면 이 칸에 그 수를 넣어주고 만약 현재 칸의 열이 마지막 열이라면 backtracking(row+1,0) 을 호출해주고 만약 마지막 열이 아니라면 backtracking(row,col+1)을 호출해준다.

 

● 다 끝나면 원래대로 이 칸의 값을 0으로 다시 되돌려준다.

 

● 만약 현재 탐색하는 스도쿠 칸의 값이 0이 아니고 열이 마지막 열이라면 backtracking(row+1, 0) 을 호출해준 뒤 끝내고, 열이 마지막 열이 아니라면 backtracking(row,col+1) 을 호출해준 뒤 끝낸다.

 

이제 promising 함수를 살펴보자.

 

● promising 함수는 매개변수로 num, row, col 을 받고 각각 현재 칸에 넣으려고 하는 수, 그 칸의 행 인덱스, 그 칸의 열 인덱스를 나타낸다.

 

● 먼저, 현재 넣으려고 하는 수가 현재 칸과 같은 행과 열에 이미 있으면 False를 return 해준다.

 

●그 후, 만약 3x3 사각형에서 현재 넣으려고 하는 수가 이미 있으면 False를 return 해준다.

 

● 끝까지 False를 return하지 않을 시 True를 return 해준다.

 

● 처음에는 행과 열의 인덱스가 모두 0인 칸부터 탐색해야 하므로 backtracking(0,0)을 호출해주면 답이 나온다!

 

 

결과