알고리즘 - Backtracking

Backtracking

대표 예 = 미로 찾기

• nxn의 미로 시작점(0,0) 도착점 (n-1,n-1)
  

find_way(x,y):
	if x==n-1 and y==n-1:
    	return True
    if M[x][y] == safe:
    	try_down = find_way(x+1,y)
        if try_down == True:
        	return True
        try_east = find_way(x,y+1)
        return try_east
    else:
    	return False

대표 예2 = N-queens 문제 (8-queens problem)

• 4x4 보드에 퀸을 규칙에 따라 위치 시키는 경우.((0,0)~(3,3))
  

pseudo-code

Nqueens(k):  # x[k]를 결정 (열의 번호)
	if k >= N:
    	return
    for c in range(N):
    	if queen can place at (k,c):
        	x[k] = c
            Nqueens(k+1)

공부 중...