반응형
4퀸 문제 및 8퀸 문제 (4-Queen problem & 8-Queen problem)
4퀸 문제(4-Queen problem) 및 8퀸 문제(8-Queen problem)는 재귀 알고리즘을 설명할 때 자주 나오는 예제로 흔히 n-Queen으로 알려진 문제이다.
간단하게 살펴보면, n개의 퀸이 서로 공격하여 잡을 수 없도록 n x n 체스판에 배치하는 것이다.
이때, 퀸은 자신과 같은 열, 행, 대각선에 위치한 다른 퀸을 공격할 수 있다.
예를 들어 4퀸 문제를 해결하고자 할 때, 체스판은 총 16칸(4*4)이 된다. 이때 첫 번째 퀸의 경우 아무 곳이나 배치할 수 있으므로 16가지, 그 다음 퀸을 배치하는 것은 15가지, ... 이런식으로 총 16*15*14*13 = 43680가지의 수가 만들어지는데, 이 조합을 모두 나열한 후 각각이 조건에 부합하는지 체크하는 것은 비현실적이다. 따라서 필자는 이 문제를 규칙을 3가지로 분할하여 정복하는 분할 정복법(divide and conquer)을 통해 해결하였다.
먼저 규칙 1은 "각 열에 퀸을 1개만 배치하여야 한다."이다.
그리고 규칙 2는 "각 행에 퀸을 1개만 배치하여야 한다."이다.
이런식의 규칙을 활용하면 규칙 1에 의해서 4*4*4*4 = 256개의 조합의 수로 줄어들고 규칙 2에 의해 같은 행에 퀸을 배치하는 조합의 수만큼 생략할 수 있다. 이제 마지막으로 아래와 같이 서로 같은 대각선에 위치한 조합을 제외하면 쉽게 해결할 수 있다.
자세한 코드는 깃허브에 남겨놓았고 코드 line별로 상세한 해설을 주석으로 남겨두었다.
4퀸 문제 풀이 깃허브: https://github.com/PSLeon24/DataStructure-Algorithms/blob/main/4-queen.ipynb
GitHub - PSLeon24/DataStructure-Algorithms: Do it! 자료구조와 함께 배우는 알고리즘 입문(Python)
Do it! 자료구조와 함께 배우는 알고리즘 입문(Python). Contribute to PSLeon24/DataStructure-Algorithms development by creating an account on GitHub.
github.com
8퀸 문제 풀이 깃허브: https://github.com/PSLeon24/DataStructure-Algorithms/blob/main/8-queen.ipynb
GitHub - PSLeon24/DataStructure-Algorithms: Do it! 자료구조와 함께 배우는 알고리즘 입문(Python)
Do it! 자료구조와 함께 배우는 알고리즘 입문(Python). Contribute to PSLeon24/DataStructure-Algorithms development by creating an account on GitHub.
github.com
N퀸 문제 풀이 깃허브: https://github.com/PSLeon24/Baekjoon/blob/main/9663.py
- 포스팅: https://psleon.tistory.com/63
4퀸 문제(4 Queen Problem)
# 8-Queen을 해결하기 위한 4-Queen
# (j, i)의 2 dimensional-matrix라 생각
pos = [0] * 4 # 각 열에 배치한 퀸의 위치
flag_a = [False] * 4 # 각 행에 퀸을 배치했는지 체크 (False: 배치 X, True: 배치 O)
flag_b = [False] * 7 # 대각선 방향(↙↗)으로 퀸을 배치했는지 체크 (False: 배치 X, True: 배치 O)
# 4x4 table을 그리면, 좌측 상단부터 대각선 번호 0 ~ 6로 나타낼 수 있음
flag_c = [False] * 7 # 대각선 방향(↖↘)으로 퀸을 배치했는지 체크 (False: 배치 X, True: 배치 O)
# 4x4 table을 그리면, 좌측 하단부터 대각선 번호 0 ~ 6로 나타낼 수 있음
cnt = 0 # n개의 퀸을 조건에 맞게 모두 배치시키는 경우의 수
def put():
global cnt # n개의 퀸을 조건에 맞게 모두 배치시키는 경우의 수를 전역변수로 생성
cnt += 1 # put()함수가 호출될 때마다 경우의 수는 1씩 증가
print(f"Queen's position in Chess Game - {cnt}")
for i in range(4): # 0~3(총 4개)의 열
print(f'index:{i, pos[i]}', end=' ') # i행 pos[i](=j)에 배치한 퀸의 위치를 출력
print()
def show(): # 4 x 4의 matrix 형태로 퀸의 위치를 표시
for j in range(4): # j행
for i in range(4): # i열
print('■' if pos[i] == j else '□', end='') # j행 i열에 퀸이 위치하면 ■, 없으면 □을 출력
print()
print()
def set(i):
for j in range(4): # 4개의 행을 검색
if(not flag_a[j] # j행에 퀸이 배치되지 않았다면
and not flag_b[i + j] # 대각선 방향(↙↗)으로 퀸이 배치되지 않았다면 - j행 i열의 값은 i+j로 구할 수 있음
and not flag_c[i - j + 3]): # 대각선 방향(↖↘)으로 퀸이 배치되지 않았다면 - j행 i열의 값은 i-j+3으로 구할 수 있음
pos[i] = j # 퀸을 j행에 배치
if i == 3: # 모든 열에 퀸을 배치 완료 (0열 ~ 3열까지 총 4개의 열)
put()
show()
else:
flag_a[j] = flag_b[i + j] = flag_c[i - j + 3] = True
# 위 코드는 (j, i) 위치에 퀸을 배치할 때, 해당 행, 대각선 (↙↗), 대각선 (↖↘)에 퀸이 배치되었다는 표시
set(i + 1) # 다음 열(i + 1)에 대해 재귀적으로 퀸을 배치하기 위한 함수를 호출
# 위 코드는 열이 한 칸씩 증가하며 가능한 모든 퀸의 배치를 찾는 과정
flag_a[j] = flag_b[i + j] = flag_c[i - j + 3] = False # 퀸이 배치되었던 행, 대각선 (↙↗), 대각선 (↖↘)의 표시를 다시 False로 변경
# 위 코드는 해당 위치에서 다른 가능한 퀸의 배치를 찾기 위해 다시 되돌리는 역할
set(0)
print(f'퀸을 배치할 수 있는 모든 경우의 수 = {cnt}')
Queen's position in Chess Game - 1
index:(0, 1)
index:(1, 3)
index:(2, 0)
index:(3, 2)
□□■□
■□□□
□□□■
□■□□
Queen's position in Chess Game - 2
index:(0, 2)
index:(1, 0)
index:(2, 3)
index:(3, 1)
□■□□
□□□■
■□□□
□□■□
퀸을 배치할 수 있는 모든 경우의 수 = 2
8퀸 문제(8 Queen Problem)
# 4-Queen을 응용해 해결하는 8-Queen
# (j, i)의 2 dimensional-matrix라 생각
pos = [0] * 8 # 각 열에 배치한 퀸의 위치
flag_a = [False] * 8 # 각 행에 퀸을 배치했는지 체크 (False: 배치 X, True: 배치 O)
flag_b = [False] * 15 # 대각선 방향(↙↗)으로 퀸을 배치했는지 체크 (False: 배치 X, True: 배치 O)
# 8x8 table을 그리면, 좌측 상단부터 대각선 번호 0 ~ 15로 나타낼 수 있음
flag_c = [False] * 15 # 대각선 방향(↖↘)으로 퀸을 배치했는지 체크 (False: 배치 X, True: 배치 O)
# 8x8 table을 그리면, 좌측 하단부터 대각선 번호 0 ~ 15로 나타낼 수 있음
cnt = 0 # n개의 퀸을 조건에 맞게 모두 배치시키는 경우의 수
def put():
global cnt # n개의 퀸을 조건에 맞게 모두 배치시키는 경우의 수를 전역변수로 생성
cnt += 1 # put()함수가 호출될 때마다 경우의 수는 1씩 증가
print(f"Queen's position in Chess Game - {cnt}")
for i in range(8): # 0~7(총 8개)의 열
print(f'index:{i, pos[i]}', end=' ') # i행 pos[i](=j)에 배치한 퀸의 위치를 출력
print()
def show(): # 8 x 8의 matrix 형태로 퀸의 위치를 표시
for j in range(8): # j행
for i in range(8): # i열
print('■' if pos[i] == j else '□', end='') # j행 i열에 퀸이 위치하면 ■, 없으면 □을 출력
print()
print()
def set(i):
for j in range(8): # 8개의 행을 검색
if(not flag_a[j] # j행에 퀸이 배치되지 않았다면
and not flag_b[i + j] # 대각선 방향(↙↗)으로 퀸이 배치되지 않았다면 - j행 i열의 값은 i+j로 구할 수 있음
and not flag_c[i - j + 7]): # 대각선 방향(↖↘)으로 퀸이 배치되지 않았다면 - j행 i열의 값은 i-j+7으로 구할 수 있음
pos[i] = j # 퀸을 j행에 배치
if i == 7: # 모든 열에 퀸을 배치 완료 (0열 ~ 7열까지 총 8개의 열)
put()
show()
else:
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = True
# 위 코드는 (j, i) 위치에 퀸을 배치할 때, 해당 행, 대각선 (↙↗), 대각선 (↖↘)에 퀸이 배치되었다는 표시
set(i + 1) # 다음 열(i + 1)에 대해 재귀적으로 퀸을 배치하기 위한 함수를 호출
# 위 코드는 열이 한 칸씩 증가하며 가능한 모든 퀸의 배치를 찾는 과정
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = False # 퀸이 배치되었던 행, 대각선 (↙↗), 대각선 (↖↘)의 표시를 다시 False로 변경
# 위 코드는 해당 위치에서 다른 가능한 퀸의 배치를 찾기 위해 다시 되돌리는 역할
set(0)
print(f'퀸을 배치할 수 있는 모든 경우의 수 = {cnt}')
Queen's position in Chess Game - 1
index:(0, 0)
index:(1, 4)
index:(2, 7)
index:(3, 5)
index:(4, 2)
index:(5, 6)
index:(6, 1)
index:(7, 3)
■□□□□□□□
□□□□□□■□
□□□□■□□□
□□□□□□□■
□■□□□□□□
□□□■□□□□
□□□□□■□□
□□■□□□□□
Queen's position in Chess Game - 2
index:(0, 0)
index:(1, 5)
index:(2, 7)
index:(3, 2)
index:(4, 6)
index:(5, 3)
index:(6, 1)
index:(7, 4)
■□□□□□□□
□□□□□□■□
□□□■□□□□
□□□□□■□□
□□□□□□□■
□■□□□□□□
□□□□■□□□
□□■□□□□□
Queen's position in Chess Game - 3
index:(0, 0)
index:(1, 6)
index:(2, 3)
index:(3, 5)
index:(4, 7)
index:(5, 1)
index:(6, 4)
index:(7, 2)
■□□□□□□□
□□□□□■□□
□□□□□□□■
□□■□□□□□
□□□□□□■□
□□□■□□□□
□■□□□□□□
□□□□■□□□
Queen's position in Chess Game - 4
index:(0, 0)
index:(1, 6)
index:(2, 4)
index:(3, 7)
index:(4, 1)
index:(5, 3)
index:(6, 5)
index:(7, 2)
■□□□□□□□
□□□□■□□□
□□□□□□□■
□□□□□■□□
□□■□□□□□
□□□□□□■□
□■□□□□□□
□□□■□□□□
Queen's position in Chess Game - 5
index:(0, 1)
index:(1, 3)
index:(2, 5)
index:(3, 7)
index:(4, 2)
index:(5, 0)
index:(6, 6)
index:(7, 4)
□□□□□■□□
■□□□□□□□
□□□□■□□□
□■□□□□□□
□□□□□□□■
□□■□□□□□
□□□□□□■□
□□□■□□□□
Queen's position in Chess Game - 6
index:(0, 1)
index:(1, 4)
index:(2, 6)
index:(3, 0)
index:(4, 2)
index:(5, 7)
index:(6, 5)
index:(7, 3)
□□□■□□□□
■□□□□□□□
□□□□■□□□
□□□□□□□■
□■□□□□□□
□□□□□□■□
□□■□□□□□
□□□□□■□□
Queen's position in Chess Game - 7
index:(0, 1)
index:(1, 4)
index:(2, 6)
index:(3, 3)
index:(4, 0)
index:(5, 7)
index:(6, 5)
index:(7, 2)
□□□□■□□□
■□□□□□□□
□□□□□□□■
□□□■□□□□
□■□□□□□□
□□□□□□■□
□□■□□□□□
□□□□□■□□
Queen's position in Chess Game - 8
index:(0, 1)
index:(1, 5)
index:(2, 0)
index:(3, 6)
index:(4, 3)
index:(5, 7)
index:(6, 2)
index:(7, 4)
□□■□□□□□
■□□□□□□□
□□□□□□■□
□□□□■□□□
□□□□□□□■
□■□□□□□□
□□□■□□□□
□□□□□■□□
Queen's position in Chess Game - 9
index:(0, 1)
index:(1, 5)
index:(2, 7)
index:(3, 2)
index:(4, 0)
index:(5, 3)
index:(6, 6)
index:(7, 4)
□□□□■□□□
■□□□□□□□
□□□■□□□□
□□□□□■□□
□□□□□□□■
□■□□□□□□
□□□□□□■□
□□■□□□□□
Queen's position in Chess Game - 10
index:(0, 1)
index:(1, 6)
index:(2, 2)
index:(3, 5)
index:(4, 7)
index:(5, 4)
index:(6, 0)
index:(7, 3)
□□□□□□■□
■□□□□□□□
□□■□□□□□
□□□□□□□■
□□□□□■□□
□□□■□□□□
□■□□□□□□
□□□□■□□□
Queen's position in Chess Game - 11
index:(0, 1)
index:(1, 6)
index:(2, 4)
index:(3, 7)
index:(4, 0)
index:(5, 3)
index:(6, 5)
index:(7, 2)
□□□□■□□□
■□□□□□□□
□□□□□□□■
□□□□□■□□
□□■□□□□□
□□□□□□■□
□■□□□□□□
□□□■□□□□
Queen's position in Chess Game - 12
index:(0, 1)
index:(1, 7)
index:(2, 5)
index:(3, 0)
index:(4, 2)
index:(5, 4)
index:(6, 6)
index:(7, 3)
□□□■□□□□
■□□□□□□□
□□□□■□□□
□□□□□□□■
□□□□□■□□
□□■□□□□□
□□□□□□■□
□■□□□□□□
Queen's position in Chess Game - 13
index:(0, 2)
index:(1, 0)
index:(2, 6)
index:(3, 4)
index:(4, 7)
index:(5, 1)
index:(6, 3)
index:(7, 5)
□■□□□□□□
□□□□□■□□
■□□□□□□□
□□□□□□■□
□□□■□□□□
□□□□□□□■
□□■□□□□□
□□□□■□□□
Queen's position in Chess Game - 14
index:(0, 2)
index:(1, 4)
index:(2, 1)
index:(3, 7)
index:(4, 0)
index:(5, 6)
index:(6, 3)
index:(7, 5)
□□□□■□□□
□□■□□□□□
■□□□□□□□
□□□□□□■□
□■□□□□□□
□□□□□□□■
□□□□□■□□
□□□■□□□□
Queen's position in Chess Game - 15
index:(0, 2)
index:(1, 4)
index:(2, 1)
index:(3, 7)
index:(4, 5)
index:(5, 3)
index:(6, 6)
index:(7, 0)
□□□□□□□■
□□■□□□□□
■□□□□□□□
□□□□□■□□
□■□□□□□□
□□□□■□□□
□□□□□□■□
□□□■□□□□
Queen's position in Chess Game - 16
index:(0, 2)
index:(1, 4)
index:(2, 6)
index:(3, 0)
index:(4, 3)
index:(5, 1)
index:(6, 7)
index:(7, 5)
□□□■□□□□
□□□□□■□□
■□□□□□□□
□□□□■□□□
□■□□□□□□
□□□□□□□■
□□■□□□□□
□□□□□□■□
Queen's position in Chess Game - 17
index:(0, 2)
index:(1, 4)
index:(2, 7)
index:(3, 3)
index:(4, 0)
index:(5, 6)
index:(6, 1)
index:(7, 5)
□□□□■□□□
□□□□□□■□
■□□□□□□□
□□□■□□□□
□■□□□□□□
□□□□□□□■
□□□□□■□□
□□■□□□□□
Queen's position in Chess Game - 18
index:(0, 2)
index:(1, 5)
index:(2, 1)
index:(3, 4)
index:(4, 7)
index:(5, 0)
index:(6, 6)
index:(7, 3)
□□□□□■□□
□□■□□□□□
■□□□□□□□
□□□□□□□■
□□□■□□□□
□■□□□□□□
□□□□□□■□
□□□□■□□□
Queen's position in Chess Game - 19
index:(0, 2)
index:(1, 5)
index:(2, 1)
index:(3, 6)
index:(4, 0)
index:(5, 3)
index:(6, 7)
index:(7, 4)
□□□□■□□□
□□■□□□□□
■□□□□□□□
□□□□□■□□
□□□□□□□■
□■□□□□□□
□□□■□□□□
□□□□□□■□
Queen's position in Chess Game - 20
index:(0, 2)
index:(1, 5)
index:(2, 1)
index:(3, 6)
index:(4, 4)
index:(5, 0)
index:(6, 7)
index:(7, 3)
□□□□□■□□
□□■□□□□□
■□□□□□□□
□□□□□□□■
□□□□■□□□
□■□□□□□□
□□□■□□□□
□□□□□□■□
Queen's position in Chess Game - 21
index:(0, 2)
index:(1, 5)
index:(2, 3)
index:(3, 0)
index:(4, 7)
index:(5, 4)
index:(6, 6)
index:(7, 1)
□□□■□□□□
□□□□□□□■
■□□□□□□□
□□■□□□□□
□□□□□■□□
□■□□□□□□
□□□□□□■□
□□□□■□□□
Queen's position in Chess Game - 22
index:(0, 2)
index:(1, 5)
index:(2, 3)
index:(3, 1)
index:(4, 7)
index:(5, 4)
index:(6, 6)
index:(7, 0)
□□□□□□□■
□□□■□□□□
■□□□□□□□
□□■□□□□□
□□□□□■□□
□■□□□□□□
□□□□□□■□
□□□□■□□□
Queen's position in Chess Game - 23
index:(0, 2)
index:(1, 5)
index:(2, 7)
index:(3, 0)
index:(4, 3)
index:(5, 6)
index:(6, 4)
index:(7, 1)
□□□■□□□□
□□□□□□□■
■□□□□□□□
□□□□■□□□
□□□□□□■□
□■□□□□□□
□□□□□■□□
□□■□□□□□
Queen's position in Chess Game - 24
index:(0, 2)
index:(1, 5)
index:(2, 7)
index:(3, 0)
index:(4, 4)
index:(5, 6)
index:(6, 1)
index:(7, 3)
□□□■□□□□
□□□□□□■□
■□□□□□□□
□□□□□□□■
□□□□■□□□
□■□□□□□□
□□□□□■□□
□□■□□□□□
Queen's position in Chess Game - 25
index:(0, 2)
index:(1, 5)
index:(2, 7)
index:(3, 1)
index:(4, 3)
index:(5, 0)
index:(6, 6)
index:(7, 4)
□□□□□■□□
□□□■□□□□
■□□□□□□□
□□□□■□□□
□□□□□□□■
□■□□□□□□
□□□□□□■□
□□■□□□□□
Queen's position in Chess Game - 26
index:(0, 2)
index:(1, 6)
index:(2, 1)
index:(3, 7)
index:(4, 4)
index:(5, 0)
index:(6, 3)
index:(7, 5)
□□□□□■□□
□□■□□□□□
■□□□□□□□
□□□□□□■□
□□□□■□□□
□□□□□□□■
□■□□□□□□
□□□■□□□□
Queen's position in Chess Game - 27
index:(0, 2)
index:(1, 6)
index:(2, 1)
index:(3, 7)
index:(4, 5)
index:(5, 3)
index:(6, 0)
index:(7, 4)
□□□□□□■□
□□■□□□□□
■□□□□□□□
□□□□□■□□
□□□□□□□■
□□□□■□□□
□■□□□□□□
□□□■□□□□
Queen's position in Chess Game - 28
index:(0, 2)
index:(1, 7)
index:(2, 3)
index:(3, 6)
index:(4, 0)
index:(5, 5)
index:(6, 1)
index:(7, 4)
□□□□■□□□
□□□□□□■□
■□□□□□□□
□□■□□□□□
□□□□□□□■
□□□□□■□□
□□□■□□□□
□■□□□□□□
Queen's position in Chess Game - 29
index:(0, 3)
index:(1, 0)
index:(2, 4)
index:(3, 7)
index:(4, 1)
index:(5, 6)
index:(6, 2)
index:(7, 5)
□■□□□□□□
□□□□■□□□
□□□□□□■□
■□□□□□□□
□□■□□□□□
□□□□□□□■
□□□□□■□□
□□□■□□□□
Queen's position in Chess Game - 30
index:(0, 3)
index:(1, 0)
index:(2, 4)
index:(3, 7)
index:(4, 5)
index:(5, 2)
index:(6, 6)
index:(7, 1)
□■□□□□□□
□□□□□□□■
□□□□□■□□
■□□□□□□□
□□■□□□□□
□□□□■□□□
□□□□□□■□
□□□■□□□□
Queen's position in Chess Game - 31
index:(0, 3)
index:(1, 1)
index:(2, 4)
index:(3, 7)
index:(4, 5)
index:(5, 0)
index:(6, 2)
index:(7, 6)
□□□□□■□□
□■□□□□□□
□□□□□□■□
■□□□□□□□
□□■□□□□□
□□□□■□□□
□□□□□□□■
□□□■□□□□
Queen's position in Chess Game - 32
index:(0, 3)
index:(1, 1)
index:(2, 6)
index:(3, 2)
index:(4, 5)
index:(5, 7)
index:(6, 0)
index:(7, 4)
□□□□□□■□
□■□□□□□□
□□□■□□□□
■□□□□□□□
□□□□□□□■
□□□□■□□□
□□■□□□□□
□□□□□■□□
Queen's position in Chess Game - 33
index:(0, 3)
index:(1, 1)
index:(2, 6)
index:(3, 2)
index:(4, 5)
index:(5, 7)
index:(6, 4)
index:(7, 0)
□□□□□□□■
□■□□□□□□
□□□■□□□□
■□□□□□□□
□□□□□□■□
□□□□■□□□
□□■□□□□□
□□□□□■□□
Queen's position in Chess Game - 34
index:(0, 3)
index:(1, 1)
index:(2, 6)
index:(3, 4)
index:(4, 0)
index:(5, 7)
index:(6, 5)
index:(7, 2)
□□□□■□□□
□■□□□□□□
□□□□□□□■
■□□□□□□□
□□□■□□□□
□□□□□□■□
□□■□□□□□
□□□□□■□□
Queen's position in Chess Game - 35
index:(0, 3)
index:(1, 1)
index:(2, 7)
index:(3, 4)
index:(4, 6)
index:(5, 0)
index:(6, 2)
index:(7, 5)
□□□□□■□□
□■□□□□□□
□□□□□□■□
■□□□□□□□
□□□■□□□□
□□□□□□□■
□□□□■□□□
□□■□□□□□
Queen's position in Chess Game - 36
index:(0, 3)
index:(1, 1)
index:(2, 7)
index:(3, 5)
index:(4, 0)
index:(5, 2)
index:(6, 4)
index:(7, 6)
□□□□■□□□
□■□□□□□□
□□□□□■□□
■□□□□□□□
□□□□□□■□
□□□■□□□□
□□□□□□□■
□□■□□□□□
Queen's position in Chess Game - 37
index:(0, 3)
index:(1, 5)
index:(2, 0)
index:(3, 4)
index:(4, 1)
index:(5, 7)
index:(6, 2)
index:(7, 6)
□□■□□□□□
□□□□■□□□
□□□□□□■□
■□□□□□□□
□□□■□□□□
□■□□□□□□
□□□□□□□■
□□□□□■□□
Queen's position in Chess Game - 38
index:(0, 3)
index:(1, 5)
index:(2, 7)
index:(3, 1)
index:(4, 6)
index:(5, 0)
index:(6, 2)
index:(7, 4)
□□□□□■□□
□□□■□□□□
□□□□□□■□
■□□□□□□□
□□□□□□□■
□■□□□□□□
□□□□■□□□
□□■□□□□□
Queen's position in Chess Game - 39
index:(0, 3)
index:(1, 5)
index:(2, 7)
index:(3, 2)
index:(4, 0)
index:(5, 6)
index:(6, 4)
index:(7, 1)
□□□□■□□□
□□□□□□□■
□□□■□□□□
■□□□□□□□
□□□□□□■□
□■□□□□□□
□□□□□■□□
□□■□□□□□
Queen's position in Chess Game - 40
index:(0, 3)
index:(1, 6)
index:(2, 0)
index:(3, 7)
index:(4, 4)
index:(5, 1)
index:(6, 5)
index:(7, 2)
□□■□□□□□
□□□□□■□□
□□□□□□□■
■□□□□□□□
□□□□■□□□
□□□□□□■□
□■□□□□□□
□□□■□□□□
Queen's position in Chess Game - 41
index:(0, 3)
index:(1, 6)
index:(2, 2)
index:(3, 7)
index:(4, 1)
index:(5, 4)
index:(6, 0)
index:(7, 5)
□□□□□□■□
□□□□■□□□
□□■□□□□□
■□□□□□□□
□□□□□■□□
□□□□□□□■
□■□□□□□□
□□□■□□□□
Queen's position in Chess Game - 42
index:(0, 3)
index:(1, 6)
index:(2, 4)
index:(3, 1)
index:(4, 5)
index:(5, 0)
index:(6, 2)
index:(7, 7)
□□□□□■□□
□□□■□□□□
□□□□□□■□
■□□□□□□□
□□■□□□□□
□□□□■□□□
□■□□□□□□
□□□□□□□■
Queen's position in Chess Game - 43
index:(0, 3)
index:(1, 6)
index:(2, 4)
index:(3, 2)
index:(4, 0)
index:(5, 5)
index:(6, 7)
index:(7, 1)
□□□□■□□□
□□□□□□□■
□□□■□□□□
■□□□□□□□
□□■□□□□□
□□□□□■□□
□■□□□□□□
□□□□□□■□
Queen's position in Chess Game - 44
index:(0, 3)
index:(1, 7)
index:(2, 0)
index:(3, 2)
index:(4, 5)
index:(5, 1)
index:(6, 6)
index:(7, 4)
□□■□□□□□
□□□□□■□□
□□□■□□□□
■□□□□□□□
□□□□□□□■
□□□□■□□□
□□□□□□■□
□■□□□□□□
Queen's position in Chess Game - 45
index:(0, 3)
index:(1, 7)
index:(2, 0)
index:(3, 4)
index:(4, 6)
index:(5, 1)
index:(6, 5)
index:(7, 2)
□□■□□□□□
□□□□□■□□
□□□□□□□■
■□□□□□□□
□□□■□□□□
□□□□□□■□
□□□□■□□□
□■□□□□□□
Queen's position in Chess Game - 46
index:(0, 3)
index:(1, 7)
index:(2, 4)
index:(3, 2)
index:(4, 0)
index:(5, 6)
index:(6, 1)
index:(7, 5)
□□□□■□□□
□□□□□□■□
□□□■□□□□
■□□□□□□□
□□■□□□□□
□□□□□□□■
□□□□□■□□
□■□□□□□□
Queen's position in Chess Game - 47
index:(0, 4)
index:(1, 0)
index:(2, 3)
index:(3, 5)
index:(4, 7)
index:(5, 1)
index:(6, 6)
index:(7, 2)
□■□□□□□□
□□□□□■□□
□□□□□□□■
□□■□□□□□
■□□□□□□□
□□□■□□□□
□□□□□□■□
□□□□■□□□
Queen's position in Chess Game - 48
index:(0, 4)
index:(1, 0)
index:(2, 7)
index:(3, 3)
index:(4, 1)
index:(5, 6)
index:(6, 2)
index:(7, 5)
□■□□□□□□
□□□□■□□□
□□□□□□■□
□□□■□□□□
■□□□□□□□
□□□□□□□■
□□□□□■□□
□□■□□□□□
Queen's position in Chess Game - 49
index:(0, 4)
index:(1, 0)
index:(2, 7)
index:(3, 5)
index:(4, 2)
index:(5, 6)
index:(6, 1)
index:(7, 3)
□■□□□□□□
□□□□□□■□
□□□□■□□□
□□□□□□□■
■□□□□□□□
□□□■□□□□
□□□□□■□□
□□■□□□□□
Queen's position in Chess Game - 50
index:(0, 4)
index:(1, 1)
index:(2, 3)
index:(3, 5)
index:(4, 7)
index:(5, 2)
index:(6, 0)
index:(7, 6)
□□□□□□■□
□■□□□□□□
□□□□□■□□
□□■□□□□□
■□□□□□□□
□□□■□□□□
□□□□□□□■
□□□□■□□□
Queen's position in Chess Game - 51
index:(0, 4)
index:(1, 1)
index:(2, 3)
index:(3, 6)
index:(4, 2)
index:(5, 7)
index:(6, 5)
index:(7, 0)
□□□□□□□■
□■□□□□□□
□□□□■□□□
□□■□□□□□
■□□□□□□□
□□□□□□■□
□□□■□□□□
□□□□□■□□
Queen's position in Chess Game - 52
index:(0, 4)
index:(1, 1)
index:(2, 5)
index:(3, 0)
index:(4, 6)
index:(5, 3)
index:(6, 7)
index:(7, 2)
□□□■□□□□
□■□□□□□□
□□□□□□□■
□□□□□■□□
■□□□□□□□
□□■□□□□□
□□□□■□□□
□□□□□□■□
Queen's position in Chess Game - 53
index:(0, 4)
index:(1, 1)
index:(2, 7)
index:(3, 0)
index:(4, 3)
index:(5, 6)
index:(6, 2)
index:(7, 5)
□□□■□□□□
□■□□□□□□
□□□□□□■□
□□□□■□□□
■□□□□□□□
□□□□□□□■
□□□□□■□□
□□■□□□□□
Queen's position in Chess Game - 54
index:(0, 4)
index:(1, 2)
index:(2, 0)
index:(3, 5)
index:(4, 7)
index:(5, 1)
index:(6, 3)
index:(7, 6)
□□■□□□□□
□□□□□■□□
□■□□□□□□
□□□□□□■□
■□□□□□□□
□□□■□□□□
□□□□□□□■
□□□□■□□□
Queen's position in Chess Game - 55
index:(0, 4)
index:(1, 2)
index:(2, 0)
index:(3, 6)
index:(4, 1)
index:(5, 7)
index:(6, 5)
index:(7, 3)
□□■□□□□□
□□□□■□□□
□■□□□□□□
□□□□□□□■
■□□□□□□□
□□□□□□■□
□□□■□□□□
□□□□□■□□
Queen's position in Chess Game - 56
index:(0, 4)
index:(1, 2)
index:(2, 7)
index:(3, 3)
index:(4, 6)
index:(5, 0)
index:(6, 5)
index:(7, 1)
□□□□□■□□
□□□□□□□■
□■□□□□□□
□□□■□□□□
■□□□□□□□
□□□□□□■□
□□□□■□□□
□□■□□□□□
Queen's position in Chess Game - 57
index:(0, 4)
index:(1, 6)
index:(2, 0)
index:(3, 2)
index:(4, 7)
index:(5, 5)
index:(6, 3)
index:(7, 1)
□□■□□□□□
□□□□□□□■
□□□■□□□□
□□□□□□■□
■□□□□□□□
□□□□□■□□
□■□□□□□□
□□□□■□□□
Queen's position in Chess Game - 58
index:(0, 4)
index:(1, 6)
index:(2, 0)
index:(3, 3)
index:(4, 1)
index:(5, 7)
index:(6, 5)
index:(7, 2)
□□■□□□□□
□□□□■□□□
□□□□□□□■
□□□■□□□□
■□□□□□□□
□□□□□□■□
□■□□□□□□
□□□□□■□□
Queen's position in Chess Game - 59
index:(0, 4)
index:(1, 6)
index:(2, 1)
index:(3, 3)
index:(4, 7)
index:(5, 0)
index:(6, 2)
index:(7, 5)
□□□□□■□□
□□■□□□□□
□□□□□□■□
□□□■□□□□
■□□□□□□□
□□□□□□□■
□■□□□□□□
□□□□■□□□
Queen's position in Chess Game - 60
index:(0, 4)
index:(1, 6)
index:(2, 1)
index:(3, 5)
index:(4, 2)
index:(5, 0)
index:(6, 3)
index:(7, 7)
□□□□□■□□
□□■□□□□□
□□□□■□□□
□□□□□□■□
■□□□□□□□
□□□■□□□□
□■□□□□□□
□□□□□□□■
Queen's position in Chess Game - 61
index:(0, 4)
index:(1, 6)
index:(2, 1)
index:(3, 5)
index:(4, 2)
index:(5, 0)
index:(6, 7)
index:(7, 3)
□□□□□■□□
□□■□□□□□
□□□□■□□□
□□□□□□□■
■□□□□□□□
□□□■□□□□
□■□□□□□□
□□□□□□■□
Queen's position in Chess Game - 62
index:(0, 4)
index:(1, 6)
index:(2, 3)
index:(3, 0)
index:(4, 2)
index:(5, 7)
index:(6, 5)
index:(7, 1)
□□□■□□□□
□□□□□□□■
□□□□■□□□
□□■□□□□□
■□□□□□□□
□□□□□□■□
□■□□□□□□
□□□□□■□□
Queen's position in Chess Game - 63
index:(0, 4)
index:(1, 7)
index:(2, 3)
index:(3, 0)
index:(4, 2)
index:(5, 5)
index:(6, 1)
index:(7, 6)
□□□■□□□□
□□□□□□■□
□□□□■□□□
□□■□□□□□
■□□□□□□□
□□□□□■□□
□□□□□□□■
□■□□□□□□
Queen's position in Chess Game - 64
index:(0, 4)
index:(1, 7)
index:(2, 3)
index:(3, 0)
index:(4, 6)
index:(5, 1)
index:(6, 5)
index:(7, 2)
□□□■□□□□
□□□□□■□□
□□□□□□□■
□□■□□□□□
■□□□□□□□
□□□□□□■□
□□□□■□□□
□■□□□□□□
Queen's position in Chess Game - 65
index:(0, 5)
index:(1, 0)
index:(2, 4)
index:(3, 1)
index:(4, 7)
index:(5, 2)
index:(6, 6)
index:(7, 3)
□■□□□□□□
□□□■□□□□
□□□□□■□□
□□□□□□□■
□□■□□□□□
■□□□□□□□
□□□□□□■□
□□□□■□□□
Queen's position in Chess Game - 66
index:(0, 5)
index:(1, 1)
index:(2, 6)
index:(3, 0)
index:(4, 2)
index:(5, 4)
index:(6, 7)
index:(7, 3)
□□□■□□□□
□■□□□□□□
□□□□■□□□
□□□□□□□■
□□□□□■□□
■□□□□□□□
□□■□□□□□
□□□□□□■□
Queen's position in Chess Game - 67
index:(0, 5)
index:(1, 1)
index:(2, 6)
index:(3, 0)
index:(4, 3)
index:(5, 7)
index:(6, 4)
index:(7, 2)
□□□■□□□□
□■□□□□□□
□□□□□□□■
□□□□■□□□
□□□□□□■□
■□□□□□□□
□□■□□□□□
□□□□□■□□
Queen's position in Chess Game - 68
index:(0, 5)
index:(1, 2)
index:(2, 0)
index:(3, 6)
index:(4, 4)
index:(5, 7)
index:(6, 1)
index:(7, 3)
□□■□□□□□
□□□□□□■□
□■□□□□□□
□□□□□□□■
□□□□■□□□
■□□□□□□□
□□□■□□□□
□□□□□■□□
Queen's position in Chess Game - 69
index:(0, 5)
index:(1, 2)
index:(2, 0)
index:(3, 7)
index:(4, 3)
index:(5, 1)
index:(6, 6)
index:(7, 4)
□□■□□□□□
□□□□□■□□
□■□□□□□□
□□□□■□□□
□□□□□□□■
■□□□□□□□
□□□□□□■□
□□□■□□□□
Queen's position in Chess Game - 70
index:(0, 5)
index:(1, 2)
index:(2, 0)
index:(3, 7)
index:(4, 4)
index:(5, 1)
index:(6, 3)
index:(7, 6)
□□■□□□□□
□□□□□■□□
□■□□□□□□
□□□□□□■□
□□□□■□□□
■□□□□□□□
□□□□□□□■
□□□■□□□□
Queen's position in Chess Game - 71
index:(0, 5)
index:(1, 2)
index:(2, 4)
index:(3, 6)
index:(4, 0)
index:(5, 3)
index:(6, 1)
index:(7, 7)
□□□□■□□□
□□□□□□■□
□■□□□□□□
□□□□□■□□
□□■□□□□□
■□□□□□□□
□□□■□□□□
□□□□□□□■
Queen's position in Chess Game - 72
index:(0, 5)
index:(1, 2)
index:(2, 4)
index:(3, 7)
index:(4, 0)
index:(5, 3)
index:(6, 1)
index:(7, 6)
□□□□■□□□
□□□□□□■□
□■□□□□□□
□□□□□■□□
□□■□□□□□
■□□□□□□□
□□□□□□□■
□□□■□□□□
Queen's position in Chess Game - 73
index:(0, 5)
index:(1, 2)
index:(2, 6)
index:(3, 1)
index:(4, 3)
index:(5, 7)
index:(6, 0)
index:(7, 4)
□□□□□□■□
□□□■□□□□
□■□□□□□□
□□□□■□□□
□□□□□□□■
■□□□□□□□
□□■□□□□□
□□□□□■□□
Queen's position in Chess Game - 74
index:(0, 5)
index:(1, 2)
index:(2, 6)
index:(3, 1)
index:(4, 7)
index:(5, 4)
index:(6, 0)
index:(7, 3)
□□□□□□■□
□□□■□□□□
□■□□□□□□
□□□□□□□■
□□□□□■□□
■□□□□□□□
□□■□□□□□
□□□□■□□□
Queen's position in Chess Game - 75
index:(0, 5)
index:(1, 2)
index:(2, 6)
index:(3, 3)
index:(4, 0)
index:(5, 7)
index:(6, 1)
index:(7, 4)
□□□□■□□□
□□□□□□■□
□■□□□□□□
□□□■□□□□
□□□□□□□■
■□□□□□□□
□□■□□□□□
□□□□□■□□
Queen's position in Chess Game - 76
index:(0, 5)
index:(1, 3)
index:(2, 0)
index:(3, 4)
index:(4, 7)
index:(5, 1)
index:(6, 6)
index:(7, 2)
□□■□□□□□
□□□□□■□□
□□□□□□□■
□■□□□□□□
□□□■□□□□
■□□□□□□□
□□□□□□■□
□□□□■□□□
Queen's position in Chess Game - 77
index:(0, 5)
index:(1, 3)
index:(2, 1)
index:(3, 7)
index:(4, 4)
index:(5, 6)
index:(6, 0)
index:(7, 2)
□□□□□□■□
□□■□□□□□
□□□□□□□■
□■□□□□□□
□□□□■□□□
■□□□□□□□
□□□□□■□□
□□□■□□□□
Queen's position in Chess Game - 78
index:(0, 5)
index:(1, 3)
index:(2, 6)
index:(3, 0)
index:(4, 2)
index:(5, 4)
index:(6, 1)
index:(7, 7)
□□□■□□□□
□□□□□□■□
□□□□■□□□
□■□□□□□□
□□□□□■□□
■□□□□□□□
□□■□□□□□
□□□□□□□■
Queen's position in Chess Game - 79
index:(0, 5)
index:(1, 3)
index:(2, 6)
index:(3, 0)
index:(4, 7)
index:(5, 1)
index:(6, 4)
index:(7, 2)
□□□■□□□□
□□□□□■□□
□□□□□□□■
□■□□□□□□
□□□□□□■□
■□□□□□□□
□□■□□□□□
□□□□■□□□
Queen's position in Chess Game - 80
index:(0, 5)
index:(1, 7)
index:(2, 1)
index:(3, 3)
index:(4, 0)
index:(5, 6)
index:(6, 4)
index:(7, 2)
□□□□■□□□
□□■□□□□□
□□□□□□□■
□□□■□□□□
□□□□□□■□
■□□□□□□□
□□□□□■□□
□■□□□□□□
Queen's position in Chess Game - 81
index:(0, 6)
index:(1, 0)
index:(2, 2)
index:(3, 7)
index:(4, 5)
index:(5, 3)
index:(6, 1)
index:(7, 4)
□■□□□□□□
□□□□□□■□
□□■□□□□□
□□□□□■□□
□□□□□□□■
□□□□■□□□
■□□□□□□□
□□□■□□□□
Queen's position in Chess Game - 82
index:(0, 6)
index:(1, 1)
index:(2, 3)
index:(3, 0)
index:(4, 7)
index:(5, 4)
index:(6, 2)
index:(7, 5)
□□□■□□□□
□■□□□□□□
□□□□□□■□
□□■□□□□□
□□□□□■□□
□□□□□□□■
■□□□□□□□
□□□□■□□□
Queen's position in Chess Game - 83
index:(0, 6)
index:(1, 1)
index:(2, 5)
index:(3, 2)
index:(4, 0)
index:(5, 3)
index:(6, 7)
index:(7, 4)
□□□□■□□□
□■□□□□□□
□□□■□□□□
□□□□□■□□
□□□□□□□■
□□■□□□□□
■□□□□□□□
□□□□□□■□
Queen's position in Chess Game - 84
index:(0, 6)
index:(1, 2)
index:(2, 0)
index:(3, 5)
index:(4, 7)
index:(5, 4)
index:(6, 1)
index:(7, 3)
□□■□□□□□
□□□□□□■□
□■□□□□□□
□□□□□□□■
□□□□□■□□
□□□■□□□□
■□□□□□□□
□□□□■□□□
Queen's position in Chess Game - 85
index:(0, 6)
index:(1, 2)
index:(2, 7)
index:(3, 1)
index:(4, 4)
index:(5, 0)
index:(6, 5)
index:(7, 3)
□□□□□■□□
□□□■□□□□
□■□□□□□□
□□□□□□□■
□□□□■□□□
□□□□□□■□
■□□□□□□□
□□■□□□□□
Queen's position in Chess Game - 86
index:(0, 6)
index:(1, 3)
index:(2, 1)
index:(3, 4)
index:(4, 7)
index:(5, 0)
index:(6, 2)
index:(7, 5)
□□□□□■□□
□□■□□□□□
□□□□□□■□
□■□□□□□□
□□□■□□□□
□□□□□□□■
■□□□□□□□
□□□□■□□□
Queen's position in Chess Game - 87
index:(0, 6)
index:(1, 3)
index:(2, 1)
index:(3, 7)
index:(4, 5)
index:(5, 0)
index:(6, 2)
index:(7, 4)
□□□□□■□□
□□■□□□□□
□□□□□□■□
□■□□□□□□
□□□□□□□■
□□□□■□□□
■□□□□□□□
□□□■□□□□
Queen's position in Chess Game - 88
index:(0, 6)
index:(1, 4)
index:(2, 2)
index:(3, 0)
index:(4, 5)
index:(5, 7)
index:(6, 1)
index:(7, 3)
□□□■□□□□
□□□□□□■□
□□■□□□□□
□□□□□□□■
□■□□□□□□
□□□□■□□□
■□□□□□□□
□□□□□■□□
Queen's position in Chess Game - 89
index:(0, 7)
index:(1, 1)
index:(2, 3)
index:(3, 0)
index:(4, 6)
index:(5, 4)
index:(6, 2)
index:(7, 5)
□□□■□□□□
□■□□□□□□
□□□□□□■□
□□■□□□□□
□□□□□■□□
□□□□□□□■
□□□□■□□□
■□□□□□□□
Queen's position in Chess Game - 90
index:(0, 7)
index:(1, 1)
index:(2, 4)
index:(3, 2)
index:(4, 0)
index:(5, 6)
index:(6, 3)
index:(7, 5)
□□□□■□□□
□■□□□□□□
□□□■□□□□
□□□□□□■□
□□■□□□□□
□□□□□□□■
□□□□□■□□
■□□□□□□□
Queen's position in Chess Game - 91
index:(0, 7)
index:(1, 2)
index:(2, 0)
index:(3, 5)
index:(4, 1)
index:(5, 4)
index:(6, 6)
index:(7, 3)
□□■□□□□□
□□□□■□□□
□■□□□□□□
□□□□□□□■
□□□□□■□□
□□□■□□□□
□□□□□□■□
■□□□□□□□
Queen's position in Chess Game - 92
index:(0, 7)
index:(1, 3)
index:(2, 0)
index:(3, 2)
index:(4, 5)
index:(5, 1)
index:(6, 6)
index:(7, 4)
□□■□□□□□
□□□□□■□□
□□□■□□□□
□■□□□□□□
□□□□□□□■
□□□□■□□□
□□□□□□■□
■□□□□□□□
퀸을 배치할 수 있는 모든 경우의 수 = 92'Algorithms & Data Structure' 카테고리의 다른 글
| [Algorithms] 셰이커 정렬(Shaker Sort) (0) | 2023.05.30 |
|---|---|
| [Data Structure] 원형 이중 연결 리스트(Circular Doubly Linked List) (0) | 2023.05.30 |
| [Algorithms] KMP 문자열 검색 알고리즘(Knuth-Morris-Pratt Algorithm) (0) | 2023.05.22 |
| [Algorithms] 하노이의 탑(Tower of Hanoi) (0) | 2023.05.19 |
| [Algorithms] 브루트 포스법(Brute Force Method) (2) | 2023.05.17 |