릿코드 37- Sudoku Solver, nQueen 다시풀기

def dfs(board, empty, count):
    global isEnd
    if count == len(empty):
        for i in board:
            print(i)
        isEnd = True
        return
    y,x = empty[count]
    nums = possible(board, y, x)
    for num in nums:
        if not isEnd:
            board[y][x] = num
            dfs(board, empty, count+1)
            board[y][x] = 0

def possible(board, y, x):
    nums = [True for i in range(10)]
    for i in range(9):
        nums[board[y][i]] = False
        nums[board[i][x]] = False
    y = (y//3) * 3
    x = (x//3) * 3
    for i in range(y, y + 3):
        for j in range(x, x + 3):
            nums[board[i][j]] = False
    return [idx for idx, i in enumerate(nums) if i and idx != 0]

def solution(board):
    empty = [(i,j) for i in range(9) for j in range(9) if board[i][j] == '.']
    for i in range(9):
        for j in range(9):
            if board[i][j].isdigit():
                board[i][j] = int(board[i][j])
            else :
                board[i][j] = 0
    return dfs(board, empty, 0)
isEnd = False
solution([["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"]])

nQueen 문제 복습하면서 백트래킹 문제를 좀더 풀어봐야겠다 싶어 풀어본 문제. 백트래킹 문제는 dfs의 틀과 비슷한 것 같다.

1. dfs 함수 가장 처음에 종료조건 체크

2. 현재 시점에서 넣을 수 있는 값 후보들 순회하며 다음 dfs 호출

3. 다음 dfs 호출 이후에는 원상복구 해둬야함

 

위의 나만의 틀대로 nQueen 문제를 다시 풀어봤다.

def dfs(positions, row) :
    n = len(positions)
    if n == row:
        return 1
    count = 0
    possibleCol = possible(positions, row)
    for col in possibleCol :
        positions[row] = col
        count += dfs(positions, row + 1)
    return count


def possible(pos, row) :
    ret = [True for i in range(len(pos))]
    for i in range(len(pos)) :
        for j in range(row):
            if pos[j] == i or (row-j == abs(pos[j] - i)):
                ret[i] = False
    return [idx for idx, i in enumerate(ret) if i]


def solution(n):
    ans = [0] * n
    return dfs(ans, 0)

print(solution(10))

 

 

백트래킹 하나만 더해보자...