8퀸 문제(8-Queen problem) 알아보기

가우스가 오답을 발표했다고 유명하다고 한다.
유명한 사람을 슬프다.
오답한 게 널리 후손까지 알려졌다.

그치만 그것도 인기가 아닐까.

이 문제는 다음과 같다.

8개의 퀸이 서로 공격하여 잡을 수 없도록 8x8 체스판에 배치하세요.

가로줄을 행,
세로줄을 열, 이라고 하고

배열 인덱스에 맞춰서

행과 열에 0~7까지 번호를 부여한다.

퀸 배치하기

퀸을 배치하는 조합이 모두 몇 가지인지 알아보자.

첫번째 퀸은 64칸 중 아무 곳이나 선택하면 되지만,
두번째 퀸부터는 63칸 중 아무곳을 선택해서...

...
64x63x...x57 = 178,462,987,637,730

이걸 모두 보는 건 비현실적이다.

퀸은 자신과 같은 열에 있는 다른 퀸을 공격할 수 있으므로,
다음과 같은 규칙을 세울 수 있다.

규칙1. 각 열에 퀸을 1개만 배치한다.

그러면 이제 조합수는

8x...8 = ...
로 아무튼 8을 여덟번 곱한 값이 나오는데,
여전히 큰 수다.

그런데!
사실 같은 행에 있으면 공격할 수 있지 않는가?
규칙을 하나 더 추가하자.

규칙2. 각 행에 퀸을 1개만 배치한다.

...

그렇지만 규칙을 두 가지나 하는 알고리즘은 쉽게 만들 수 없다.

그러므로 첫번째 규칙에 따라
조합을 나열하는 알고리즘부터 생각해보자.

각 열에 퀸을 배치한다고 생각해보자.

0열에서 퀸을 배치하는 방법은 8가지다.

그러면 각 방법마다 문제를 8개로 나눌 수 있다.

• 1열에 배치한 경우 나머지 7열을..
• 1열에 배치한 경우 나머지 7열을..
  ...

그 다음에 1열에 배치한 경우 나머지 7열에서
2열을 배치하는 걸 생각해보자.

• 1행 1열에 배치한 상태에서, 2열 1행에...
• 1행 1열에 배치한 상태에서, 2열 2행에...

해서 또 8개의 문제로 나누어진다.

이 작업 등을 반복하면,
7열까지 퀸을 배치한 조합은
아까 계산한것처럼 8x8x8...을 여덟번 곱한 값이다.

그렇지만
이 때 두번째 시도에서 1행 1열에 배치했는데, 2열 1행에 배치한 조합들은 제외해도 된다...
....

....

분기 작업으로 문제 해결하기

이처럼 가지를 나누는 식으로,
모든 조합을 나열하는 프로그램을 만든다...고 한다.

8퀸 문제를 해결하는 것은 아니다.

? 나누는 작업을 프로그래밍 용어로 '분기'라고 한다.

배열 pos에,
i열에 j행이라고 할때,
pos[i] = j 로 넣어둔다.

set() 이라는 재귀 함수를 만들거고,
pos[i]에 0~7까지 대입한다.

가장 먼저 호출에는 set(0)으로 시작하여,
set(i+1)로 나아간다..

내가 만든 함수

def set(열:int)-> None:

	for i in range(8):
    	pos[i] = i
        

...네 안 만들었습니다.
그래서 순차적으로 알아봤습니다.

pos[0] = 0 으로 넣었을떄,

이건 pos[1]= 0, pos[1] = 1... 로 넣어지다가

pos[1] =0에서 pos[2] =0 ...

...

그래서 정답 코드를 봤다.

def set(i:int) -> None:
	for j in range(8):
    	pos[i] = j
        set(i+1)
        
set(0)

...하아아

인자를 받아서 진짜로
0부터 7까지 넣은다음에

그렇구나..
대충 알거같은데..

만약 1차에서, 다음으로 넘어가야한다면,
(그러니까 다른 값을 출력하기 전에 그 1번째 경우에서
또 반복해야한다면)
그 반복문 안에 그냥 그 함수를 넣어버린다는 거잖아.

오오오

이렇게 차례대로 가지가 뻗어나가듯이
배치 조합을 열거하는 방법을 분기(branching) 작업 이라고 한다.

이처럼 하노이의 탑이나 8퀸 문제처럼
큰 문제를 작은 문제로 분할하고,
작은 문제 풀이법을 결합하여

전체 풀이법을얻는 방법을

분할 정복법(divide and conquer, 분할 해결법) 이라고 한다.

여기서 주의할 점은...

문제를 분할할 때,
작은 문제 풀이법에서 원래의 문제 풀이법을 쉽게 도출할 수 있도록 설계해야한다.

한정 작업과 분기 한정법

분기 조합으로는 퀸을 배치하는 조합을 나열할 수는 있지만,
8퀸 문제의 최종 답을 얻을 수는 없다.

다음은 앞에 분기를 한정할 때 정했던 규칙이다.

규칙2. 각 행에 퀸을 1개만 배치한다.

음.

그냥 바로 프로그램 만들어버리네
저 울어요

def set(i:int) -> None:
	for j in range(8):
    	
    	pos[i] = j
        if pos[i-1] = pos[i]:
        	break
        set(i+1)
        
set(0)

해봤습니다

정답 코드

flag = [False] * 8

def set(i:int) -> None:
	for j in range(8):
        if not flag[j]:
        	pos[i] = j
        flag[j] = True
        set(i+1)
        frag[j] = False
        
set(0)

True와 False를 flag로 만들어서

올렸는지 아닌지를 True로 반환하고

...
하...
천재네...

내가 한건 거기서 break 해버리기때문에..
..아니 챗 지피티는
위엣것도 괜찮대
쩝...

그래서...

이처럼 필요하지 않는 분기를 없애서,
불필요한 조합을 열거하지 않는 방법을 한정(bounding) 작업 이라고 한다.

분기 작업과 한정 작업을 조합하여 문제를 풀이하는 방법을,
분기 한정법(branching and bounding method)이라고 합니다.

8퀸 문제 해결 프로그램 만들기

퀸이 행과 열 방향으로 겹치지 않는 조합을 나열하는 프로그램.

하지만 체스에서 퀸은 대각선 방향으로 이동할 수 있으므로,
어떤 대각선에서 보더라도 퀸을 1개만 배치하는 한정 작업을 추가로 적용해야한다.

하...
말은 쉽지...

대각선 조건이 뭐야?

일단 1열에서
1에 배치될때

열 행
(1,1)-> (2,2)

2에 배치될때
(1,2) -> (2,1) (2,3)

3에 배치될때
(1,3)-> (2,2),(2,4)

즉
다음에 들어갈때는 값이
j-1, j+1은 안된다! 라는 거잖아.
j-1이 음수면 없고.
j+1이 8을 넘으면 없고.

두번째 플래그 만드나??

flag = [False] * 8
twoFlag = [False] * 8

def set(i:int) -> None:
	for j in range(8):
        if not flag[j] and not twoFlag[j]:
        	pos[i] = j
        twoFlag[j] = True
        flag[j] = True
        set(i+1)
        twoFlag[j] = False
        frag[j] = False
        
set(0)

아니...
그... 저번 프로그램은 flag로 저번 함수의 값을 가져왔잖아?
그래서 내가 체크하는 것도 저번 함수의 값을..
pos[i]같은게 아니라, 총합하는 식으로 가져와야할 거같거든.

근데 인접한 값일때만 flag를 True를 반환..
받으려면 어떻게하지?
값을 저장해두고..그래...

flag = [False] * 8
k = 0

def set(i:int) -> None:
	for j in range(8):
        if not flag[j] and j != k+1 and j != k-1:
        	pos[i] = j
            k = j
        flag[j] = True
        set(i+1)
        frag[j] = False
        
set(0)

정답을 보겠사옵니다

헉!!
아이디어는 맞았어
구현은 약간 틀렸어
많이 틀렸을 수도 있어

pos = [0] * 8
flag_a = [False] * 8
flag_b = [False] * 15
flag_c = [False] * 15

def set(i:int) -> None:
	for j in range(8):
        if 
        not flag[j] and 
        not flag_b[i+j] and 
        not flag_c[i-j+7]:
        	pos[i] = j
        flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = True
        set(i+1)
        flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = False
        
set(0)

많이 틀렸군
나는 인접한 것만 고려해서 뒷부분에...
거리가 멀지만 대각선인게 존재할 수 있어.

그래서 아예 n행 n열을 전부 고려하는 flag_b, flag c를 만들었다.

대각선을 전부 그어서 그 대각선의 갯수가
15개라서 15개 할당해주고,

놓았다면...

행과 열의 합이 0행 0열부터 7행 7열까지니까
더하면 총합이 0부터 14, 즉 대각선 인덱스와 같은 걸 이용해서

왼쪽 대각선과 오른쪽 대각선을 한번에 올려줌...

b는 그런 식이고
c는..
그 대각선에 속하는 인덱스를
전부 더하면 i-j +7로 나오다니

아니...
왜 이렇게 딱 떨어지게 나와주는거지?

내가 모르는 뭔가 이유가 있겠지

넘어가자

아무튼 8퀸 끝!
재밌었다!