N-Queen 파이썬

0. 문제설명
   N-Queen 문제는 크기가 NxN인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제
   8x8 체스판에서 퀸은 상하좌우+대각선 방향에서 다른 퀸이 있으면 안된다. (동일 행,열,대각선으로는 다른 퀸을 놓을 수 없다)
   12개의 기본형태, 여덟퀸의 경우 총 92개의 해가 존재한다.

back-tracking

1. 백트래킹으로 n-Queen 문제해결
   백트래킹? 모든 경우의 수를 전부 고려하는 알고리즘
   (= DFS를 사용하여 조건에 맞지 않으면 중단하고 이전으로 돌아가 다시 확인하기를 반복하면서 원하는 조건을 찾는 알고리즘)
   (vs DFS: dfs는 가능한 모든 경로를 탐색하므로 불필요할 것 같은 경로를 사전에 차단하는 등의 로직이 존재하지 않는다. 반면 백트래킹은 해를 찾아가면서 지금의 경로가 해가 될 것 같지 ㅇ낳으면 그 경로를 더 이상 가지 않고 되돌아간다)

def n_queens (col, i):
    n = len(col) -1
    //n=(열의 개수-1) 예) 5열이면 n=4
    
    if (promising(i, col)):
        if (i == n):
        //i가 끝까지 다 나왔음
            print(col[1: n+1])
        //i=n이면 1열부터 (n+1)열까지 출력 예) 
        else:
            for j in range(1, n+1):
            // 아직 j가 끝까지 못간 경우에 대해 n+1까지 증가할때
                col[i+1] = j
                n_queens(i+1, col)
                //(i+1)에 j를 할당 -> 새로운 수 i+1에 대해 다시 반복
        
def promising (i, col):
    k = 1
    flag = True
    while (k < i and flag):
        if (col[i] == col[k] or abs(col[i] - col[k]) == (i - k)):
        //1) 동일한 열에 있는가 or 2) 동일한 대각선에 위치
            flag = False
            //flag를 거짓으로 설정
        k += 1
	return flag;

2. Math.abs(n)
   정수 인수 n의 절대값을 반환한다.
   col[i] : i번째 행에서 퀸이 놓여져 있는 열의 위치

3. 알고리즘 계산식 분석
   1) 같은 열에 있는지 체크한다.
   col[i] == col[k] i행에 있는 퀸의 열과 k행에 있는 퀸의 열이 동일
   2) 대각선 체크한다.
   col[i]-col[k] == i-k(i행에 있는 퀸의 열)-(k행에 있는 퀸의 열)=(i-k)

4. 시험하기

n=4
col=[0] * (n+1)
n_queens(col, 0)

[2, 4, 1, 3] => col[1]=2, col[2]=4, col[3]=1, col[4]=3
[3, 1, 4, 2] => col[1]=3, col[2]=1, col[3]=4, col[4]=2
얘네를 그려서 보면 y축 대칭임

n=8
col=[0] * (n+1)
n_queens(col, 0)

brute-force 기반

1. 브루트포스로 n-queens 문제해결
   brute-force? 완전 탐색알고리즘 (가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족하는 결과만 가져온다)
   구조에 따라 i) 선형구조: 순차 탐색 ii) 비선형구조: BFS, DFS
2. 소개
   퀸위치의 가능한 모든 순열을 찾은 다음 > 각각을 평가하여 유효한 솔루션인지 여부를 결정함
3. 한계점
   항상 솔루션이 존재하는 경우 해결책을 찾을 수 있으나 계산 비용이 후보 수에 비례하므로 효율적이지 않다. 검색공간이 증가함에 따라 솔루션을 찾는 계산이 증가하므로 이 알고리즘의 사용이 제한된다.
4. 계산- 시간복잡도
   NxN 표에서 모든 위치에서 해결책을 찾기 때문에 O(N^N) 시간 복잡도를 갖는다.
5. 시간복잡도를 줄이려면?
   계산을 줄이면 시간 복잡도를 낮출수 있다. 검색공간을 줄이고 차원을 줄임으로써 검색공간을 줄인다.

#### IMPORTS
import itertools

#### FUNCTIONS ####
def create_empty_board(N):
    "Create an NxN board of zeros"
    return [[0]*N for _ in range(N)] 

def perm_to_board(perm):
    "Makes a full board board from a given permutation"
    board = create_empty_board(len(perm))
    for ndx in range(len(perm)):
        board[perm[ndx]][ndx] = 1
    return board

def print_perm(perm):
    "Pretty print utility function"
    print()
    print(perm," =" )
    print_board(perm_to_board(perm))
    
def is_solution(perm):
    "Check if input array contains queens on the same diagonal"
    for (i,j) in itertools.combinations(range(len(perm)), 2):
        if ( abs(i-j) == abs(perm[i]-perm[j]) ): return False
    return True

def find_permutations(N):
    "Find all possible permuations of 0-(N-1)"
    return list(itertools.permutations(range(0,N)))

def find_first_solutions(all_permutations):
    "Utility function that checks validity of each solution"
    for perm in all_permutations:
        if is_solution(perm): return perm
        
if __name__ == '__main__':
    # input size of board = number of queens
    print("How many queens to place?")
    # convert input string to a number
    N = int(input()) 

    # find all permutations of N queens
    all_permuations = find_permutations(N)

    # go through all perms, return first valid one
    perm = find_first_solutions(all_permuations)

    # pretty print the perm and board
    print_perm(perm)

5. 동작 알고리즘
   (1) NxN 보드에 얼마나 많은 퀸을 놓을 것인지 물어본다.
   (2) 0~N 순열에서 가능한 모든 후보를 찾는다.

brute-force 알고리즘 (모든 해결방안)

brute-force의 확장버전
: 해결방안이 발견되면 후보평가를 중단했음. => 더 많은 계싼이 필요하나 모든 솔루션을 제공하기 위해 후보를 계속해서 평가함

파이썬 코드 실행시간 측정 방법

1. time 모듈을 이용한 시간 측정
2. datetime 모듈을 이용하여 조금 이쁘게 시간 측정 출력