백트래킹 - 몸풀기 문제

### 문제 47 1부터 N까지 숫자 중 합이 10이 되는 조합 구하기

N을 입력 받아 1부터 N까지의 숫자 중에서 합이 10이 되는 조합을 리스트로 반환하는 함수 작성

같은 숫자는 한 번만 선택 가능, 오름차순으로 정렬, N은 1이상 10 이하

# 조합한 숫자의 합이 10이 되면 해당 조합을 결과 리스트에 추가
# 조합한 숫자의 합이 10보다 크면 백트래킹
def solution():
	results=[]
    
	def backtrack(sum,selected_nums,start)
    	if sum == 10:
        	results.append(selected_nums)
        return
        
        for i in range(start,N+1):
        	if sum+i<=10:
            	backtrack(
                	sum+i,selected_nums+[i],i+1
                ) # 유망한 경우에만 백트랙 함수를 재귀적으로 호출
 backtrack(0,[],1)
 return results

### 문제 48 스도쿠 퍼즐

9x9 스토쿠 보드를 다 채워 완성된 스도쿠 보드를 반환하는 함수 작성
1. 가로줄, 세로줄에는 1부터 9까지의 숫자가 한 번씩 나타나야
2. 9x9 보드를 채울 9개의 작은 박스 (3x3 크기)에도 1부터 9까지의 숫자가 한 번씩 나타나야

# 아래 조건에 해당된다면 백트래킹
# 1. 해당 행에 넣으려는 숫자 num이 있는지 확인
# 2. 해당 열에 넣으려는 숫자 num이 있는지 확인
# 3. 3x3 박스에 num이 있는지 확인

def solution():
	def is_valid(num,row,col):
    	return not (in_row(num,row) or in_column(num,row) or in_box(num,row,col))
        
    def in_row(num,row):
    	return num in board[row]
    
    def in_column(num,column):
    	return num in board[column]
    
    def in_box(num,column,row):
    	box_row=(row//3)*3
        box_column=(column//3)*3
        for i in range(box_row,box_row+3):
        	for j in range(box_column,box_column+3):
            	if board[i][j]==num:
                	return True
        return False
    def find_empty_position():
    	for i in range(9):
        	for j in range(9):
            	if board[i][j]==0:
                	return i,j
    return None
    
    def find_solution():
    empty_pos=find_empty_position()
    
    if not empty_pos:
    	return True
    row,col=empty_pos
    for num in range(1,10):
    	if is_valid(num,row,col):
        	board[row][col]=num
            if find_solution():
            	return True
            board[row][col]=0
    return False
 find_solution()
 return board