Eight Queens Problem
유명한 프로그래밍 퀴즈.
8-queens 문제는 Queen이 다른 Queen를 공격할 수 없는 8 X 8개의 체스 판에서 8개의 Queen을 체스판 위에 놓이게하는 문제이다. 체스 판에서 Queen은 똑같은 행렬(가로와 세로)/대각선방향에 대해서 공격이 가능하다. 그러므로 이 문제에 대한 solution은 자기 자신(Queen)을 보호하면서 새로운 위치에 Queen을 놓게 하는 것이다.
- 각 열에는 오직 하나의 퀸만 존재해야 한다.
- 각 행에는 오직 하나의 퀸만 존재해야 한다.
- 각각의 퀸의 대각선에 다른 퀸이 존재해서는 안 된다.
예를들어 다음과 같이 퀸을 위치할 수 있다.
8 x 8 체스판에 8개의 Queen을 놓을 수 있는 방법은 모두 몇 가지인가?
대각선도 행/열과 마찬가지로 한 퀸의 대각선 선상에서는 인접하지 않더라도 다른 퀸을 놓을 수 없다는거죠?
어휴 문제를 잘못 이해하고 풀었네요. 행,열과 달리 한 퀸과 바로 인접한 대각선방향에서만 퀸을 놓을 수 없는 걸로 이해하고 코드를 짰어요;ㅎㅎㅎ 나중에 시간나면 다시 풀어봐야겠네요
어릴 때 분명히 체스를 해 본 기억이 있는데.. 체스 룰이 기억이 잘 안나네요;;ㅎㅎ
-
Katherine,
2014/03/11 17:00
@Katherine님, 네 맞습니다. 대각선상으로 움직일때도 부딫히면 안됩니다.
-
pahkey,
2014/03/11 17:18
64개의 풀이가 있습니다.
Python 입니다.
import unittest
class Q:
def __init__(self, row, col):
self.row = row
self.col = col
def safe(self, other):
return self.row != other.row and self.col != other.col \
and abs(self.row-other.row) != abs(self.col-other.col)
def __str__(self):
return "(%s,%s)" % (self.row, self.col)
def eight_queen(s, result=[]):
string_queens = [int(i) for i in str(s)]
nextRow = len(string_queens)
if nextRow == 8:
result.append(s)
found_queens = []
for row, col in enumerate(string_queens):
found_queens.append(Q(row, col))
for col in range(8):
q = Q(nextRow, col)
isSafe = True
for found in found_queens:
if not q.safe(found):
isSafe = False
if isSafe:
eight_queen(s+str(col))
return result
class Test(unittest.TestCase):
def testSafe(self):
self.assertFalse(Q(0, 0).safe(Q(0, 0)))
self.assertFalse(Q(0, 0).safe(Q(0, 1)))
self.assertFalse(Q(0, 0).safe(Q(1, 0)))
self.assertFalse(Q(0, 0).safe(Q(1, 1)))
self.assertFalse(Q(0, 0).safe(Q(7, 7)))
self.assertFalse(Q(1, 1).safe(Q(2, 2)))
self.assertFalse(Q(1, 0).safe(Q(0, 1)))
self.assertFalse(Q(7, 7).safe(Q(6, 6)))
def testQueen(self):
print len(eight_queen(""))
#for x in eight_queen(""):print x
if __name__ == "__main__":
unittest.main()
이 문제를 풀기 위해 제일먼저 한 일은 퀸을 놓았을 때 안전한지를 판별해 주는 로직을 만드는 일이었습니다. 위 코드 Q 클래스의 safe method를 보시면 아마 쉽게 이해가 되실 겁니다.
그 다음은 머리속에서 한참을 고민한 결과 다음과 같은 알고리즘을 생각해 내었고 그것을 그대로 코드로 적었더니 문제가 풀리더군요.
- 최초 "" 이라는 문자열로 시작합니다.
- 첫번째 Row의 퀸이 올 수 있는 Column은 0~7 까지입니다. 이것을 "0", "1", "2", "3", "4", "5", "6", "7" 이라는 문자열로 표현합니다.
- 두번째 퀸을 놓는 것은 "02", "03",... 과 같이 표현합니다. 여기서 "02"의 의미는 첫번째 Row의 퀸의 Column 인덱스는 0, 두번째 row 퀸의 Column 인덱스는 2를 의미합니다. Row가 변경될 때 붙는 퀸들은 이전 Row들의 퀸들과 서로 안전한지 검사해야 합니다.
- 이전 Row들의 퀸들과 비교하여 그 다음 Row에 위치할 안전한 퀸들을 찾았다면 그 모두를 다시 재귀호출 시킵니다.
- 이렇게 계속해서 총 8개의 퀸들이 완성될 때까지 프로그램이 재귀적으로 수행됩니다.
수행시간은 0.1초 미만으로 나오네요.
문제풀이법 : bit flag를 이용한 문제 풀기
8칸인 경우 가로줄은 00000001, 00000010 ...... 10000000 중에 하나가 되며 1 bit만 True이기 때문에 가로로 겹치는 경우는 없기 때문에 가로 검사는 따로 하지 않아도 된다.대각선과 세로로 겹치는지 검사하기만 하면 되는데 OR연산을 이용하여 leftMask(왼쪽대각선), righMask(오른쪽대각선), accMask(세로마스크) 들을 하나의 mask로 합친다.
ex) mask = FULL_BIT_FLAG & (accMask | leftMask | rightMask)
여기 현재의 값(q)와 mask를 AND연산했을때 0 이 나오면 겹치치 않으므로 Safe이다. 그러므로 결과를 저장한다.
SIZE = 8
FULL_BIT_FLAG = (2**SIZE) - 1 # 8bit example => 11111111
def queens(accMask, leftMask, rightMask, acc_result, total_result):
# mask - check for safe
mask = FULL_BIT_FLAG & (accMask | leftMask | rightMask)
for i in range(SIZE):
# q is Queen
q = 1 << i
# safe case - not overlap case
if q & mask == 0:
nextAccMask = accMask | q
nextlLeftMask = (leftMask | q) << 1
nextrRightMask = (rightMask | q) >> 1
result = acc_result + [q]
# problem solved
if nextAccMask == FULL_BIT_FLAG:
# record result to total result
total_result.append(result)
return
else:
queens(nextAccMask, nextlLeftMask, nextrRightMask, result, total_result)
return total_result
# problem resolve
final_result = queens(0, 0, 0, [], [])
# show
for result in final_result:
# number to bit flag string
print("\n".join(["{0:b}".format(num).zfill(SIZE) for num in result]) + "\n")
print("Total answer count : %d" % len(final_result))
결과
00000001
00010000
10000000
00100000
00000100
01000000
00000010
00001000
.
.
.
10000000
00001000
00000001
00000100
00100000
00000010
01000000
00010000
Total answer count : 92
"""
board[row][col]
0 : empty
1 : queen
2 : forbidden
"""
from copy import deepcopy
def prettyprint(board):
print '\n'.join(str(r) for r in board),'\n'
return
def markposs(board, row, col):
board[row] = [2] * 8
for r in xrange(len(board)): board[r][col] = 2
if row > col: s = (row - col, 0)
else: s = (0, col - row)
while s[0] < len(board) and s[1] < len(board[0]):
board[s[0]][s[1]] = 2
s = (s[0] + 1, s[1] + 1)
if row + col > len(board) - 1: s = (row + col - (len(board) - 1), (len(board) - 1))
else: s = (0, row+ + col)
while s[0] < len(board) and s[1] > -1:
board[s[0]][s[1]] = 2
s = (s[0] + 1, s[1] - 1)
board[row][col] = 1
return
solve = []
def branchposs(board, rest = 8):
#prettyprint(board)
global solve
if rest == 0: solve.append(reduce(lambda x,y : ''.join(map(str,x))+''.join(map(str,y)), board).replace("2","0"))
for r in xrange(len(board)):
for c in xrange(len(board[0])):
if(board[r][c] == 0):
b = deepcopy(board)
markposs(b, r, c)
branchposs(b, rest - 1)
elif(board[r][c] == 1):
break
return
b = [[0]*8 for a in xrange(8)]
branchposs(b)
print set(solve)
무식하게 짰습니다. 퀸이 놓일 수 없는 위치를 표시하고 놓일 수 있는 위치에 다 넣어봅니다. 다 짜고 찾아보니 이런 방법이 제일 흔한 것 같더군요. 한 30분 돌려서 92개 나왔네요.
(use 'clojure.math.combinatorics)
(let [board (for [x (range 8), y (range 8)] [x y])
h-moves (for [i (range -7 8)] [i 0])
v-moves (for [i (range -7 8)] [0 i])
d-moves-1 (for [i (range -7 8)] [i i])
d-moves-2 (for [i (range -7 8)] [i (- 7 i)])
moves (concat h-moves v-moves d-moves-1 d-moves-2)
combos (combinations board 8)
attack (fn [pos] (set (map #(map + pos %) moves)))
put (fn [board pos] (remove (attack pos) board))
alive-8th? (fn [combo] (reduce put board (take 7 combo)))
alive (filter alive-8th? combos)]
(println "유효한 조합들= " alive)
(println "개수= " (count alive)))
Clojure 코드입니다.
문제의 정의 자체는 간단한데 계산량이 어마어마하게 많네요. 저도 효율적인 알고리즘을 생각하지 못해 Lee SunYeop님처럼 무식하게 했는데 (아마 제가 좀 더 무식할 듯) 먼저 모든 배치조합을 생성한 후 유효한 조합을 걸러내도록 했습니다. 아직 답은 못 구했습니다. 실행중인데 언제 끝날지 모르겠네요... ㄷㄷ
3시간동안 돌린 결과가 OutOfMemoryError Java heap space 네요. 다른 방법을 생각해 봐야겠네요.
-
박연오,
2014/02/28 00:35
+2
저도 처음엔 그렇게 했지만, 코딩을 중단하고 다른 일을 하던 다른 방법이 생각나서 저렇게 새로 코딩한 것인데요, 놓일 수 없는 자리를 표시하는 것이 훨씬 빠릅니다. 이렇게 하면 퀸을 놓을 수 있는 자리가 없는 경우 더이상 해당 가지를(?) 실행하지 않고 다음으로 넘어가버리니까요.
-
Lee SunYeop,
2014/02/28 05:44
그나저나 코드는 간결한게 참 이쁘네요
-
Lee SunYeop,
2014/02/28 05:45
time ruby nqueen.rb
92
real 0m0.034s
user 0m0.030s
sys 0m0.004s
$N = 8
$cnt = 0
def nqueen(candidates, row_y)
if row_y > $N
#found an answer
$cnt+=1
end
candidates_in_row_y = candidates.find_all{|y,x| row_y == y}
candidates_in_row_y.each do |y, x|
nqueen( candidates.reject { |cy,cx|
cy == y ||
cx == x ||
cy + cx == y + x ||
cy - cx == y - x
}, row_y + 1
)
end
end
rng = (1..$N).to_a
candidates = rng.product rng
nqueen(candidates, 1)
puts $cnt
#include <cstdio> #include <algorithm> #include <cstdlib> using namespace std; int cnt = 0; int pos[8]; bool chk(int queen,int rowpos){ for (int i = 0; i < queen; i++){ int rowpos2 = pos[i]; if (rowpos2 == rowpos || rowpos2 == rowpos-(queen-i) || rowpos2 == rowpos+(queen-i)) return false; } return true; } void recur(int x){ if (x == 8) ++cnt; else{ for (int i = 0; i < 8; i++){ if (chk(x,i)){ pos[x] = i; recur(x+1); } } } } int main(){ recur(0); printf("%d\n",cnt);return 0; }
고전적인 N-Queen 문제네요! 백트래킹으로 해결해줬어요. N = 8이라서 순식간에 92 (답)를 출력합니다. acmicpc.net 유저들은 이 문제도 한번 참고해보시길!: https://www.acmicpc.net/problem/9663
전형적인 백트래킹 문제. Edgar Dijkstra의 알고리즘을 그대로 C로 옮기면 아래와 같음.
#include <stdio.h>
int count = 0;
int cols[8] = {0};
int lr[15] = {0};
int rl[8] = {0};
void eq(int row) {
if (row == 8) {
count++;
return;
}
for (int col = 0; col < 8; col++) {
if (cols[col] || lr[7 + row - col] || rl[row + col])
continue;
// take step
cols[col] = 1;
lr[7 + row - col] = 1;
rl[row + col] = 1;
eq(row + 1);
// step back
lr[7 + row - col] = 0;
rl[row + col] = 0;
cols[col] = 0;
}
}
int main(int argc, const char * argv[]) {
eq(0);
printf("%d\n", count);
return 0;
}
차근차근 접근한다면.. 각 row에는 여왕 하나만 놓을 수 있으므로, 첫 줄부터 여왕을 놓아서 8번째 줄까지 문제없이 여왕을 놓을 수 있으면 솔루션 하나가 됨.
뼈대
void bt(int row) {
if (row == 8) { // 8줄 모두 놓았으니 끝.
count++;
return;
}
// 현재 row에 새로운 여왕을 놓아야 하는데
// 모든 col에 대해 놓을 수 있는지 검사하고, 놓을 수 있으면 다음 줄로 진행..
for (int col=0; col<8; col++) {
if (현재 row의 col위치에 여왕을 놓을 수 있으면) {
bt(row+1);
}
}
}
bt(0); // 0부터 시작
한 줄에 하나만 놓으므로 같은 row에서 여왕들이 충돌할 일은 없므르로, 0~row-1 까지 이미 놓아둔 여왕들과
- 같은 col에서 충돌이 있는지
- 좌상-우하 방향의 대각방향에 충돌이 있는지
- 우상-좌하 방향의 대각방향에 충돌이 있는지..
위 세가지 충돌이 없으면 현재 row의 col위치에 여왕을 놓을 수 있고, 다음 줄로 진행할 수 있음.
그러므로 여왕을 놓을 때마다 충돌검사를 위한 배열에 플래그를 지정함.
int cols[8] = {0, }; // col에 놓을 때 1로 설정
int lr[15] = {0, }; // 좌상-우하 방향의 대각방향.. (row, col)을 지나는 직선의 y절편.. (기울기 1)
int rl[15] = {0, }; // 우상-좌하 방향의 대각방향.. (row, col)을 지나는 직선의 y절편.. (기울기 -1)
그러면 for에선..
for (int col=0; col<8; col++) {
if (cols[col] || lr[7 + row - col] || rl[row + col]) // 이미 놓였으므로..
continue; // 더이상 진행할 필요없음
// 현재 col에 놓을 수 있음.
cols[col] = 1;
lr[7 + row - col] = 1;
rl[row + col] = 1;
bt(row+1); // 이제 다음 줄로 넘어감..
// 다음 col을 확인하기 전에 아까 설정한 값 reset!
cols[col] = 0;
lr[7 + row - col] = 0;
rl[row + col] = 0;
}
MATLAB으로 짰습니다. 가로 세로 확인은 MATLAB 내장함수인 perms (가능한 permutation 조합을 돌려주는 함수, 10개 이하에서 동작) 을 이용했고, 대각선 체크는 abs(perm_arr(q)-perm_arr(r)) == abs(q-r) 여부로 확인했습니다. worst case 1.123 million 만큼의 for-loop을 돌게 됩니다. (8! * 8C2 또는 factorial(8) * nchoosek(8,2))
답은 92 나왔고 걸린 시간은 0.08초입니다.
clear all
close all
clc
t_start=clock;
chess_size=8;
perm_arrays=perms(1:chess_size); % naturally screen out the row, column criterion
n=size(perm_arrays,1);
solution_cnt=0;
solution_set=[];
% 8! cases * 8C2 (28) times - screening
for p=1:n
perm_arr=perm_arrays(p,:);
exit_code=0;
for q=1:chess_size-1
if exit_code==1;continue;end;
for r=q+1:chess_size
if exit_code==1;continue;end;
if abs(perm_arr(q)-perm_arr(r))==abs(q-r) % queens in any diagonal position, should be screened out
exit_code=1;% escape condition
end
end
end
if exit_code==0 % survived
solution_cnt=solution_cnt+1;
solution_set(solution_cnt,:)=perm_arr;
end
end
disp(['가능한 경우의 수 : ' num2str(solution_cnt)]);
t_end=clock;
elapsed_time=etime(t_end,t_start);
if elapsed_time<60
disp([' elapsed time : ' num2str(elapsed_time) ' sec']);
elseif elapsed_time<3600
disp([' elapsed time : ' num2str(elapsed_time/60) ' mins']);
else
disp([' elapsed time : ' num2str(elapsed_time/3600) ' hours']);
end
disp(' ');
disp('---------------');
disp(' 예제 ');
Iden=eye(chess_size);
example_matrix=Iden(:,solution_set(3,:))
틀린풀이입니다^^; 제가 문제를 잘못 이해하고 풀었었네요;;ㅎㅎ 한 Q가 위치한 대각선상에서 그 Q와 바로 인접한 칸에만 다른 Q를 놓을 수 없는 것으로 착각하고 푼 문제입니당 Java입니다.
package h29_Queens;
public class Board { //체스판b[N][N] + b[i][N]:i행 퀸의 열주소, b[i][N+1]:i행 시도 횟수
int i,j;
void makeVoid(int[][] b){ //초기화함수(딱 한번만 쓰임)
for(i=0;i<b.length;i++){
for(j=0;j<b.length;j++) b[i][j]=0;
b[i][j]=b.length; b[i][j+1]=0;
}
}
int putQ(int[][] b, int a){ //입력받은 a번째 줄부터 퀸 놓기
int ii, N=b.length, m; //b[i][j]은 0:empty(.) 1:Queen(Q) 2:같은열 다른퀸-불가(+) 3:대각선 다른퀸-불가(x)
for(i=a; i<N; i++){
for(j=0,m=0; j<N; j++){
if(b[i][j]==0){
if(b[i][N+1]==m){
b[i][j]=1; b[i][N]=j;
for(ii=i+1;ii<b.length;ii++) b[ii][j]=2;
if(j>0 && i+1<N && b[i+1][j-1]!=2) b[i+1][j-1]=3;
if(j+1<N && i+1<N && b[i+1][j+1]!=2) b[i+1][j+1]=3;
break;
}
else m++;
}
}
if(j==N) break;
} return --i; //리턴값은 Queen을 마지막으로 놓은 행
}
void eraseQ(int[][] b, int n){ //n번째 줄에서 Queen 지우기
int N=b.length, m=b[n][N];
b[n][m]=0; b[n][N]=N; b[n][N+1]++;
for(i=n+1;i<N;i++){ b[i][m]=0; b[i][N]=N; b[i][N+1]=0; }
if(m>0 && n+1<N && b[n+1][m-1]==3) b[n+1][m-1]=0;
if(m+1<N && n+1<N && b[n+1][m+1]==3) b[n+1][m+1]=0;
}
void P(int[][] b, int r, int a){ //출력함수
char c='-'; int l=b.length;
for(i=0;i<b.length;i++){
for(j=0;j<b.length;j++){
switch(b[i][j]){
case 0: c='.'; break; //empty
case 1: c='Q'; break; //Queen Is
case 2: c='+'; break; //같은열에 다른 퀸 있음
case 3: c='x'; break; //대각선에 다른 퀸 있음
} System.out.print(" "+c);
} System.out.println(" "+((b[i][j]<l)?b[i][j]+1:0)+" "+b[i][j+1]);
} // N개 열 다음 칸(b[i][N]):Q의 열위치, 그다음칸(b[i][N+1]):이 행에서 시도한 횟수
System.out.println("result:"+r+" line:"+(a+1));
} //result:완성된 판의 갯수, line:Q을 마지막으로 놓은,혹은 이제 놓으려는 행
}
public class Queens {
public static void main(String[] args) {
Board B=new Board();
int N=8, r=0, a=0; //N:체스판(NXN), r:result(완성된 체스판의 갯수), a:퀸을 놓을 행
int[][] b=new int[N][N+2]; //체스판b[N][N] + b[i][N]:퀸의 주소, b[i][N+1]:i행에서 가능한 칸에 시도하는 횟수
//b[i][j]은 0:empty(.) 1:Queen(Q) 2:같은 열에 다른 퀸-불가(+) 3:대각선에 다른 퀸-불가(x)
B.makeVoid(b);
Total:
while(true){
a=B.putQ(b,a); //B.P(b,r,a);
while(a+1<N){ B.eraseQ(b,a); a=B.putQ(b,a); // B.P(b,r,a); //!모든 과정을 보고싶다면 이 B.P함수를 쓰세요
if(b[0][N+1]==N) break Total; //가능한 모든 시도를 하면 끝
} r++; B.P(b,r,a); //!!!완성된 판만 보려면 요기서 B.P함수를 (결과만 보려면 요 B.P(b,r,a);를 삭제)
B.eraseQ(b,a);
} System.out.println("Result:"+r);
}
}
* 출력예시(B.P(b,r,a))
empty→'.'(0), Queen→'Q'(1), 같은열다른행에 퀸(불가)→'+'(2), 대각선에 퀸(불가)→'x'(3)
b[i][N]:i행의 Q의 열주소(출력시 +1해서 출력, Q이 없을경우 원래값은 N → 0으로 출력)
b[i][N+1]:i행에서 가능한칸(빈칸)에 시도한 횟수
result(r):완성된 판 갯수, line(a):현재 Q을 놓으려는(혹은 놓은) 행→ +1해서 출력
<B.makeVoid(b)로 초기화 → 출력B.P(b,r,a)>
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
result:0 line:1
<첫번째 a=B.putQ(b,a); → B.P(b,r,a);>
Q . . . . . . . 1 0
+ x Q . . . . . 3 0
+ x + x Q . . . 5 0
+ Q + x + x . . 2 0
+ + + Q + . . . 4 0
+ + + + + Q . . 6 0
+ + + + + + x Q 8 0
+ + + + + + x + 0 0
result:0 line:7
<마지막 완성 판>
. . . . . . . Q 8 7
. . . . . Q x + 6 5
. . . Q x + x + 4 3
. . x + x + Q + 7 2
. . Q + . + + + 3 2
Q x + + . + + + 1 0
+ x + + Q + + + 5 0
+ Q + + + + + + 2 0
result:5242 line:8
Result:5242
<가능한 모든 시도를 하고나면(첫 행의 시도횟수가 8이 되면)
if(b[0][N+1]==N) break Total; 써서 프로그램종료>
. . . . . . . . 0 8
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
result:5242 line:0
Result:5242
8-여왕 문제의 답은 92개입니다. 5242개면 너무 많이 나오네요.
당장 마지막 완성 판이라고 된 것도 같은 대각선에 여왕이 둘 있네요
-
Kim Jaeju,
2014/03/11 16:33
아 제가 문제를 잘못 이해했나보네요..지적해주셔서 고마워요;;ㅎㅎ 행,열과 달리 대각선은 바로 다른 퀸과 인접한 대각선방향에서만 퀸을 놓을 수 없다고 잘못 이해하고 코드를 짰어요. 좀 있다가 다시풀어봐야겠어요;ㅋㅋ
-
Katherine,
2014/03/11 16:52
다시 풀었습니다. 그래픽 형식으로 출력해보는데 초점을 두고 코딩했습니다^^;; Java입니다. * 수정을 했습니다. 다른 열과 대각선 둘 다에 Q가 있어 불가표시 '+'와 'x' 표시가 겹칠경우 '#'으로 출력하게 해보았습니다.
* 체스판에 Q들을 두는 과정을 하나하나 그래픽형식으로 출력해보고 싶어서^^^^
그래픽형식으로 출력하는데 초점을 두고 코딩했습니다ㅎㅎ
# putQ 첫번째 시도 출력
Q . . . . . . . 1 1
+ x Q . . . . . 3 1
+ x # x Q . . . 5 1
# Q + x # x . . 2 1
# + # Q # x x . 4 1
+ # # # # x x x 0 0
# # + + # x x x 0 0
# + + + + x x x 0 0
result:0 line:5
#첫번째로 완성한 체스판 출력
Q . . . . . . . 1 1
+ x . . Q . . . 5 3
+ . x x + x . Q 8 3
+ . x x + Q x + 6 2
+ x Q . # # x # 3 1
# x + x # # Q # 7 1
# Q # x # # # # 2 1
# # # Q # # + # 4 1
result:1 line:8
#마지막으로 완성한 체스판 출력
. . . . . . . Q 8 8
. . . Q . . x + 4 4
Q . x + x x . + 1 1
+ x Q + x x . + 3 1
# x # # . Q x + 6 2
# Q # # x + x # 2 1
# # # # x # Q # 7 1
# + # # Q # # # 5 1
result:92 line:8
Result:92
#마지막 putQ 시도 출력
. . . . . . . Q 8 8
. . . . . Q x + 6 6
. . . Q x # x + 4 4
. . x # x + Q # 7 3
. x x # Q # + # 5 2
x x x # # # # + 0 0
x x x # + + # # 0 0
x x x + + + + # 0 0
result:92 line:5
Result:92
'+':다른열의 Q때문에 불가, 'x':대각선상 다른 Q때문에 불가, '#': '+'와 'x'가 겹침.
result:(r) → 지금까지 완성된 체스판의 갯수
line:(l) → (putQ직후) Q를 놓은, 혹은 (eraseQ직후) 이제 Q를 놓으려는 행
* 출력된 체스판 오른쪽 첫번째 숫자열은 J[i]+1 → i행에서 Q가 위치한 열주소값이구요 (초기값:N)
* 그 두번째 숫자열은 M[i] → (i-1행에서 Q 하나가 그 위치를 유지하고 있을 때) i행에서 빈 칸들 중 Q가 위치하기를 시도한 횟수입니다.
(출력시 Q가 놓인 행과 line(l)이 가리키는 행은 (M[i]+1)로 출력하지만, line(l)행 아래의 Q가 없는 행들은 M[i]을 원래 값 0 그대로 출력합니다)
※ 제가 올린 코드를 그대로 실행하면 완성된 체스판을 모두 출력하게 되어 있습니다ㅎㅎㅎ
최종값 Result만 출력하려면, (r++;는 절대 건드리지 마시고, 그 다음의)
→ B.P(board, J, M, r, l); /*!!!완성된 체스판만 출력*/ 요 부분을 /* */ 처리하시면 됩니다.
슬래쉬 두개를 풀어서 모든 putQ과정을 출력하거나, 모든 eraseQ과정까지 출력할 수도 있습니다;;;ㅋㅋㅋㅋ
* Q는 한 행, 한 열, 한 대각선에 하나씩만 둘 수 있습니다.
한 행당 하나의 Q만 둘 수 있으므로, N*N=8*8의 체스판에 한 행씩 빈칸에 Q를 두고,
Q를 둘 때마다 그 행의 아래행들에게 이 Q와 같은 열의 칸들(불가 '+'표시), 이 Q와 같은 대각선상의 칸들(불가 'x'표시)에 불가 표시를 합니다. ⇒ < putQ 함수 >
'+'표시와 'x'표시를 따로 하기 위해서 고민하다가,
* 그래픽파일 다룰 때 레이어 여러개 깔듯이 (ㅎㅎㅎ) 체스판을 두 장 깔았어요.
체스판 선언 board[행][열][2] →
board[][][0]에는 (초기값 0) 불가'+'표시(값 1)와 Q표시(값 -1),
board[][][1]에는 (초기값 0) 불가'x'표시(값 1,2) ~ (한 칸이 두개의 Q의 대각선상에 크로스식으로 모두 위치할 수 있으므로 값은 두 개 1,2가 될 수 있음)
※ 따라서 (board[i][j][0]==0 && board[i][j][1]==0)이어야만 진짜 empty → 빈칸 '.'표시
두 장의 체스판 레이어(board[][][0],board[][][1]) 모두에 불가표시가 있을경우 → 불가'#'표시
<putQ함수> 에서 (입력받은 line(l)값 행부터) 각 행(i)에 Q를 놓은 뒤에 (이 때 M[i]값에 따라서 놓음),
그다음행부터 이 Q로 인해 다른 Q가 올 수 없는 칸에 모두 불가표시('+','x')를 합니다
빈칸이 없어 Q를 놓을 수 없는 행이 나오기 전까지 계속 Q를 놓으며, 마지막으로 Q를 놓은 행의 값을 리턴합니다
putQ의 리턴값이 N-1일경우 (line:8) Q가 N개 모두 놓여졌다는 뜻이므로 하나의 완성된 체스판이 만들어진 거에요ㅎㅎ → r++;
<eraseQ함수> 입력받은 line(l)값의 Q를 지우고, 이 Q의 흔적들(그다음행부터 이 Q로 인한 불가표시들과 M[]값들)을 지웁니다. 지우고 있는 이 Q가 위치한 행 i의 M[i]값은 1 증가시킵니다.(새로운 시도를 해야 하므로)
만약 방금 지운 Q의 칸에서 그 다음 열 중 빈칸이 없을 경우, 한 행 위로 올라가서 Q를 지웁니다 → 즉 입력line값 l을 (i-1)로 주면서 eraseQ함수를 재귀시킵니다(반복)
지운 Q의 칸 다음 열들 중 빈칸이 있는 행에서 eraseQ함수를 재귀시키지 않고 그 행 값을 리턴합니다.
<프로그램 종료> : putQ와 eraseQ를 반복하다가, 첫번째 행에서 N번째열에 Q를 놓았다가 이를 지웠을 때 → 더 이상 또다른 시도를 할 수 없으므로 프로그램을 종료합니다
즉 (M[0]==N)이면 프로그램이 종료됩니다
#참고로 프로그램 종료시 출력 → M[0]==N이면 (eraseQ 함수에서 재귀 반복으로 모든 Q를 지움)
. . . . . . . . 0 9
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
. . . . . . . . 0 0
result:92 line:1
/* board[행][열][0] → 0:empty, -1:QueenIs, 1:다른열에 퀸-불가 (출력시 +표현 위한 것)
* board[행][열][1] → 0:empty, 1,2:대각선상 다른 퀸이 위치-불가 (출력시 x표현 위한 것)
* (board[i][j][0]==0 && board[i][j][1]==0)이어야만 진짜 empty
* */
package h_Chess_Queens;
public class Chess_Queens {
public static void main(String[] args) {
Board B=new Board();
int N=8; //N:체스판 크기 N*N=8*8
int i,j, r=0, l=0; //r:result, l:line
int[][][] board=new int[N][N][2];
int[] J=new int[N]; //Q의 주소: i행 j열에 Q이 위치 → J[i]=j (초기값:N=8)
int[] M=new int[N]; //각 행에서 빈칸에 putQ를 시도한 횟수
B.def(board, J, M); //체스판 초기화
do{
l=B.putQ(board, J, M, l);
if(l+1==N){ r++; //완성된 체스판이 나왔을 경우
B.P(board, J, M, r, l); /*!!!완성된 체스판만 출력*/
}
//else B.P(board, J, M, r, l); /*모든 putQ과정 출력*/
l=B.eraseQ(board, J, M, l);
//B.P(board, J, M, r, l); /*모든 eraseQ과정까지 출력*/ //굳이 요건 볼 필요 없습니다
}while(M[0]!=N);
System.out.println("Result:"+r);
}
}
package h_Chess_Queens;
public class Board {
int N=8; //N:체스판크기 N*N
int i,j,m,t;
/*출력함수*/
void P(int[][][] b, int[] J, int[] M, int r, int l){
char p;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
if(b[i][j][0]==0&&b[i][j][1]==0) p='.';
else if(b[i][j][0]==-1) p='Q';
else if(b[i][j][1]>0){
if(b[i][j][0]>0) p='#';
else p='x';
}
else if(b[i][j][0]>0) p='+';
else p='?';
System.out.print(p+" ");
}
if(J[i]<N) System.out.println((J[i]+1)+" "+(M[i]+1));
else if(M[i]>0) System.out.println(0+" "+(M[i]+1));
else System.out.println(0+" "+M[i]);
}
System.out.println("result:"+r+" line:"+(l+1));
}
/*초기화함수*/ //딱 한번만 쓰임
void def(int[][][] b, int[] J, int[] M){
for(i=0;i<N;i++){
for(j=0;j<N;j++){ b[i][j][0]=0; b[i][j][1]=0;} J[i]=N; M[i]=0;
}
}
/*Q놓는 함수 putQ*/ //a라인에서부터 Q을 놓기 시작함 → 마지막으로 Q놓은 행의 값 리턴
int putQ(int[][][] b, int[] J, int[] M, int a){
for(i=a;i<N;i++){
for(j=0,m=0; j<N;j++){
if(b[i][j][0]==0&&b[i][j][1]==0){
if(m==M[i]){
b[i][j][0]=-1; J[i]=j;
for(t=1; i+t<N;t++){
b[i+t][j][0]++;
if(j-t>=0) b[i+t][j-t][1]++;
if(j+t<N ) b[i+t][j+t][1]++;
}
break;
}//이제 Q 하나 놓음.
else m++;
}
}
if(j==N) break; //i행에서 Q를 놓을 자리가 없음 → 함수연산 중단하고 i-1값 리턴
}
return i-1;
}
/*Q지우는 함수 eraseQ*/ //지우는 Q의 흔적도 모두 지움
int eraseQ(int[][][] b, int[] J, int[] M, int l){
i=l; j=J[i];
b[i][j][0]=0; J[i]=N; M[i]++;
for(t=1;i+t<N;t++){
b[i+t][j][0]=0;
if(j-t>=0) b[i+t][j-t][1]--;
if(j+t<N ) b[i+t][j+t][1]--;
M[i+t]=0;
}
if(i>0){ //i행에서 방금 지운 Q자리 이후 빈 칸이 없을 경우 → 윗 칸으로 올라가서 윗칸 Q도 지움 (재귀)
for(t=1;j+t<N;t++) if(b[i][j+t][0]==0&&b[i][j+t][1]==0) break;
if(j+t==N) l=eraseQ(b,J,M,i-1);
}
return l; //재귀했을 경우에는, Q를 마지막으로 지운 행 값 리턴
}
}
Java 로 풀었습니다 :)
읽기쉬운, 객체지향에 부합하는 코드를 짜려고 노력하는데, 참 어렵네요ㅠㅠ 이름짓기, 클래스 설계는 항상 어렵습니다.
개선할 부분 많이 지적해주세요.
Backtracking 알고리즘으로 풀어봤습니다.
ChessBoard 클래스에 placeQueen(row, column) 메소드를 재귀적으로 호출합니다.
package eightqueen;
import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.*;
import org.junit.Test;
public class ChessBoardTest {
@Test
public void shouldNumberOfSolutionBe2AtSize4() {
ChessBoard chessBoard = new ChessBoard(4);
assertThat(chessBoard.getNumberOfSolution(), is(2));
}
@Test
public void shouldNumberOfSolutionBe92AtSize8() {
ChessBoard chessBoard = new ChessBoard(8);
assertThat(chessBoard.getNumberOfSolution(), is(92));
}
}
package eightqueen;
public class ChessBoard {
private Solution solution;
private int numberOfSolution;
private int chessBoardSize;
public ChessBoard(int chessBoardSize) {
this.solution = new Solution();
this.chessBoardSize = chessBoardSize;
this.numberOfSolution = 0;
}
private void placeQueen(int row) {
if (row > this.chessBoardSize) {
numberOfSolution++;
return;
}
for (int column = 1; column <= this.chessBoardSize; column++) {
if (solution.isSafePlace(row, column)) {
Queen queen = new Queen(row, column);
solution.add(queen);
placeQueen(row + 1);
solution.remove(queen);
}
}
}
public int getNumberOfSolution() {
placeQueen(1);
return numberOfSolution;
}
}
package eightqueen;
import java.util.ArrayList;
public class Solution {
private ArrayList<Integer> row = new ArrayList<Integer>();
private ArrayList<Integer> column = new ArrayList<Integer>();
private ArrayList<Integer> leftDiagonal = new ArrayList<Integer>();
private ArrayList<Integer> rightDiagonal = new ArrayList<Integer>();
public boolean isSafePlace(int x, int y) {
if (row.contains(x)) {
return false;
}
if (column.contains(y)) {
return false;
}
if (leftDiagonal.contains(x + y)) {
return false;
}
if (rightDiagonal.contains(x - y)) {
return false;
}
return true;
}
public void add(Queen queen) {
row.add(new Integer(queen.getRow()));
column.add(new Integer(queen.getColumn()));
leftDiagonal.add(new Integer(queen.getRow() + queen.getColumn()));
rightDiagonal.add(new Integer(queen.getRow() - queen.getColumn()));
}
public void remove(Queen queen) {
row.remove(new Integer(queen.getRow()));
column.remove(new Integer(queen.getColumn()));
leftDiagonal.remove(new Integer(queen.getRow() + queen.getColumn()));
rightDiagonal.remove(new Integer(queen.getRow() - queen.getColumn()));
}
}
solution 클래스가 안 보이네요 ^^
-
pahkey,
2014/03/31 22:51
@길가의풀 님 / 수정했습니다 ^^ 개선할만한 부분 지적해주시면 고쳐볼게요
-
Jaehyun, Park,
2014/04/01 10:23
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define QUEEN_CHECK 'Q'
#define IMPOSSIBLE_AREA 'X'
#define POSSIBLE_AREA '1'
typedef struct queen
{
int x;
int y;
}QUEEN;
void Init( char** pTable, QUEEN* pQueenArr, int size )
{
int i, j;
for( i = 0; i < size; i++ )
{
for( j = 0; j < size; j++ )
{
pTable[i][j] = POSSIBLE_AREA;
}
}
for( i = 0; i < size; i++ )
{
pQueenArr[i].y = i;
pQueenArr[i].x = -1;
}
}
int RefreshTableStatus( char** pTable, int queenNum, QUEEN* pQueenArr, int size )
{
int x, y, i;
int calcCrossX;
//하위 퀸 x좌표 초기화
for( i = queenNum+1; i < size; i++ )
{
pQueenArr[i].x = -1;
}
//현재 퀸 아래 테이블 초기화
for( y = queenNum+1; y < size; y++ )
{
for( x = 0; x < size; x++ )
{
pTable[x][y] = POSSIBLE_AREA;
}
}
//현재 퀸 아래 테이블 이동 불가 위치 'X' 표시
for( y = queenNum+1; y < size; y++ ) // 퀸 아래 Y
{
for( x = 0; x < size; x++ ) // 퀸 아래 X
{
for( i = 0; i <= queenNum; i++ ) // 퀸 배열 순회 for 문
{
if( pQueenArr[i].x == x ) // 같은 열 X
{
pTable[x][y] = IMPOSSIBLE_AREA;
}
// 오른쪽 대각선 체크
calcCrossX = (pQueenArr[i].x + y) - i;
if( x == calcCrossX)
{
pTable[x][y] = IMPOSSIBLE_AREA;
}
// 왼쪽 대각선 체크
calcCrossX = (pQueenArr[i].x - y) + i;
if( x == calcCrossX)
{
pTable[x][y] = IMPOSSIBLE_AREA;
}
}
}
}
}
int MoveQueen( char** pTable, int* queenNum, QUEEN* pQueenArr, int size )
{
int x, y;
while(TRUE)
{
x = pQueenArr[*queenNum].x;
y = pQueenArr[*queenNum].y;
// Queen이 마지막 칸이면
if( pQueenArr[*queenNum].x >= (size-1) )
{
//현재 퀸이 첫 행 퀸이면 프로그램 종료
if( (*queenNum) == 0 )
{
printf("MoveQueen, first queen\r\n");
return -1;
}
else // 상위 행 퀸을 움직임
{
(*queenNum)--;
return MoveQueen( pTable, queenNum, pQueenArr, size );
}
}
if( x != -1 )
pTable[x][y] = POSSIBLE_AREA;
pQueenArr[*queenNum].x++;
x = pQueenArr[*queenNum].x;
if( pTable[x][y] == POSSIBLE_AREA ) // 이동 가능 지역이면
{
pTable[x][y] = QUEEN_CHECK;
return *queenNum;
}
}
}
void PrintTable( char** pTable, int size )
{
int x, y;
printf("======================================\r\n");
for( y = 0; y < size; y++ )
{
for( x = 0; x < size; x++ )
{
printf("%4c", pTable[x][y] );
}
printf("\r\n\n");
}
}
int main( int* argc, char *argv[] )
{
char** pTable;
QUEEN* pQueenArr;
int iSize, i;
int ret, currentQueenNum, caseCount;
int x, y;
caseCount = 0;
if( argv[1] == 0 )
{
printf("Should input the size(integer)\r\n");
return 0;
}
iSize = atoi(argv[1]);
printf("Table size : %s X %s\r\n", argv[1], argv[1] );
pTable = (char**)malloc( sizeof(char) * (iSize * iSize) );
pQueenArr = (QUEEN*)malloc( sizeof(QUEEN) * iSize );
for( i = 0; i < iSize; i++ )
{
pTable[i] = (char*)malloc( sizeof(char) * (iSize) );
}
Init( pTable, pQueenArr, iSize );
currentQueenNum = 0;
while(TRUE)
{
ret = MoveQueen( pTable, ¤tQueenNum, pQueenArr, iSize );
if( ret == -1 )
{
break;
}
else if( ret == (iSize-1) )
{
caseCount++;
PrintTable( pTable, iSize );
}
else
{
RefreshTableStatus( pTable, currentQueenNum, pQueenArr, iSize );
currentQueenNum++;
}
}
printf("case : %d\r\n", caseCount );
free(pTable);
free(pQueenArr);
return 0;
}
- 테이블 크기를 실행 인자로 받습니다.
- 테이블을 초기화 합니다. 처음에는 모두 이동 가능 표시를 합니다 ('1' 표시 )
- 퀸 구조체 배열을 초기화 합니다. 각 행마다 하나의 퀸만 배치되도록 y좌표를 설정 합니다.
- 첫 번째 행의 퀸부터 이동 합니다. ( MoveQueen() )
- 이동이 완료 되면 이동 한 퀸의 아래 행 전체를 초기화 합니다. 그리고 대각선, 같은 열에 이동 불가 표시를 합니다 ('X' 표시)
- 다음 퀸을 이동 합니다. 이동 할 때는 이동 가능 칸으로만 이동 합니다.
- 만약 이동 가능한 칸이 없을 경우, 또는 현재 칸이 마지막 칸이라 이동이 불가능 할 경우에는 Queen 인덱스를 1 낮추고, 다시 MoveQueen()함수를 호출 합니다 (재귀)
- 만약 이동 가능한 칸이 없고 현재 퀸이 첫번째 행의 퀸일 경우에는 프로그램을 종료 합니다.
- 이동 한 퀸이 마지막 퀸일 경우에는 경우의 수를 +1 합니다.
C#으로 작성했습니다. 2-dimensional array를 가지고 0,0부터 backtracking을 시작합니다. queen이 8개 배치가 되어야 하기 때문에 일단 row를 중심으로 row가 0부터 7까지 모두 queen이 배치되어야 합니다. x에서 queen이 들어갈 자리를 찾으면, x를 1 올려줍니다. 마지막 row가 7일 때 queen이 배치가 되면 하나의 경우의 수를 찾은 걸로 계산, 재귀함수를 이용해 queen을 대입시켰을 때까지 나올 수 있는 모든 경우의 수를 다 더했더니 92가 나왔습니다. 8의 배수가 나올 줄 알았더니 아니었네요. 걸린 시간은 2 milliseconds 입니다.
public int CountEightQueens(bool[,] board, int row = 0, int count = 0)
{
for (int j = 0; j < 8; j++)
{
if (CheckBoard(board, row, j))
{
if (row < 7)
{
board[row, j] = true;
count = CountEightQueens(board, row + 1, count);
board[row, j] = false;
}
else return ++count;
}
}
return count;
}
public bool CheckBoard(bool[,] board, int x, int y)
{
for (int i = -8; i < 8; i++)
{
if (i >= 0 && (board[x, i] || board[i, y])) return false;
if (x + i >= 0 && x + i < 8 && i != 0)
{
if (y + i >= 0 && y + i < 8) if (board[x + i, y + i]) return false;
if (y - i >= 0 && y - i < 8) if (board[x + i, y - i]) return false;
}
}
return true;
}
ㅋㅋㅋ... 뭔가 지저분하고 끼워맞춘거같은 코드.. ㅠㅠ 그래도 92!! 라고 딱 답이 나오네요 ㅎㅎ 기분좋습니다!!
원리는 그냥 경우의수 계산하는것처럼 한줄씩 퀸을 배치할수 있으면 할수잇는데로 계속 배치하고 8개가 안됫는데 퀸을 더이상 놓을수 없다면 그이전줄로 가서 놓은것을 삭제하고 그 놓은것 다음칸부터 다시 넣어보고 하는것을 반복합니다.
수행시간은 실행하자마자 결과가 나와서 잘 모르겠는데 0.1초 정도일것 같네요.
//
// main.cpp
// CodingDojang_5
//
// Created by 최세현 on 2014. 9. 25..
// Copyright (c) 2014년 worldbright. All rights reserved.
//
#include <iostream>
#include <time.h>
using namespace std;
int chessBoard[8][8] = {0};
bool place(int, int, int, int);
void setPlace(int, int, int, int);
void returnPlace(bool*, int*, int&, int&, bool, int, int, int);
int main(int argc, const char * argv[]) {
bool nope[8] = {false};
int placed[8] = {-1};
int order = 0;
int countNumber = 0;
for(int i = 0; i < 8; i++) {
for(int j = placed[i]+1; j < 8; j++) {
if(nope[j]) continue;
if(place(j, i, 1, -1)) {
nope[j] = true;
placed[i] = j;
order++;
break;
}
}
if(i != order-1) {
if(i==0) break;
returnPlace(nope, placed, i, order, true, i-1, -2, -1);
} else if(order == 8) {
countNumber++;
returnPlace(nope, placed, i, order, false, i-1, 0, 0);
returnPlace(nope, placed, i, order, true, i, -2, -2);
}
}
cout << countNumber << endl;
return 0;
}
void returnPlace(bool *nope, int *placed, int &i, int &order, bool setPlaced, int iForUse, int deltaI, int deltaOrder) {
nope[placed[iForUse]] = false;
place(placed[iForUse], iForUse, 0, 1);
if(setPlaced) placed[i] = -1;
i += deltaI;
order += deltaOrder;
}
bool place(int x, int y, int set, int around) {
if (chessBoard[y][x] < 0)
return false;
setPlace((x - y < 0) ? 0 : x - y, (y - x < 0) ? 0 : y - x, 1, around);
setPlace((x + y > 7) ? 7 : x + y, (y - 7 + x < 0) ? 0 : y - 7 + x, -1, around);
chessBoard[y][x] = set;
return true;
}
void setPlace(int x, int y, int deltaX, int around) {
while(true) {
chessBoard[y][x] += around;
x += deltaX;
y++;
if(x == -1 || y == -1 || x == 8 || y == 8)
break;
}
}
코드에는 출력하는 구문이 없는데, 아무도 결과출력을 안하셨길래 한번 출력을 해보았습니다. 스압 죄송합니다;;ㅠㅠ
1번째 경우의수
@-------
----@---
-------@
-----@--
--@-----
------@-
-@------
---@----
2번째 경우의수
@-------
-----@--
-------@
--@-----
------@-
---@----
-@------
----@---
3번째 경우의수
@-------
------@-
---@----
-----@--
-------@
-@------
----@---
--@-----
4번째 경우의수
@-------
------@-
----@---
-------@
-@------
---@----
-----@--
--@-----
5번째 경우의수
-@------
---@----
-----@--
-------@
--@-----
@-------
------@-
----@---
6번째 경우의수
-@------
----@---
------@-
@-------
--@-----
-------@
-----@--
---@----
7번째 경우의수
-@------
----@---
------@-
---@----
@-------
-------@
-----@--
--@-----
8번째 경우의수
-@------
-----@--
@-------
------@-
---@----
-------@
--@-----
----@---
9번째 경우의수
-@------
-----@--
-------@
--@-----
@-------
---@----
------@-
----@---
10번째 경우의수
-@------
------@-
--@-----
-----@--
-------@
----@---
@-------
---@----
11번째 경우의수
-@------
------@-
----@---
-------@
@-------
---@----
-----@--
--@-----
12번째 경우의수
-@------
-------@
-----@--
@-------
--@-----
----@---
------@-
---@----
13번째 경우의수
--@-----
@-------
------@-
----@---
-------@
-@------
---@----
-----@--
14번째 경우의수
--@-----
----@---
-@------
-------@
@-------
------@-
---@----
-----@--
15번째 경우의수
--@-----
----@---
-@------
-------@
-----@--
---@----
------@-
@-------
16번째 경우의수
--@-----
----@---
------@-
@-------
---@----
-@------
-------@
-----@--
17번째 경우의수
--@-----
----@---
-------@
---@----
@-------
------@-
-@------
-----@--
18번째 경우의수
--@-----
-----@--
-@------
----@---
-------@
@-------
------@-
---@----
19번째 경우의수
--@-----
-----@--
-@------
------@-
@-------
---@----
-------@
----@---
20번째 경우의수
--@-----
-----@--
-@------
------@-
----@---
@-------
-------@
---@----
21번째 경우의수
--@-----
-----@--
---@----
@-------
-------@
----@---
------@-
-@------
22번째 경우의수
--@-----
-----@--
---@----
-@------
-------@
----@---
------@-
@-------
23번째 경우의수
--@-----
-----@--
-------@
@-------
---@----
------@-
----@---
-@------
24번째 경우의수
--@-----
-----@--
-------@
@-------
----@---
------@-
-@------
---@----
25번째 경우의수
--@-----
-----@--
-------@
-@------
---@----
@-------
------@-
----@---
26번째 경우의수
--@-----
------@-
-@------
-------@
----@---
@-------
---@----
-----@--
27번째 경우의수
--@-----
------@-
-@------
-------@
-----@--
---@----
@-------
----@---
28번째 경우의수
--@-----
-------@
---@----
------@-
@-------
-----@--
-@------
----@---
29번째 경우의수
---@----
@-------
----@---
-------@
-@------
------@-
--@-----
-----@--
30번째 경우의수
---@----
@-------
----@---
-------@
-----@--
--@-----
------@-
-@------
31번째 경우의수
---@----
-@------
----@---
-------@
-----@--
@-------
--@-----
------@-
32번째 경우의수
---@----
-@------
------@-
--@-----
-----@--
-------@
@-------
----@---
33번째 경우의수
---@----
-@------
------@-
--@-----
-----@--
-------@
----@---
@-------
34번째 경우의수
---@----
-@------
------@-
----@---
@-------
-------@
-----@--
--@-----
35번째 경우의수
---@----
-@------
-------@
----@---
------@-
@-------
--@-----
-----@--
36번째 경우의수
---@----
-@------
-------@
-----@--
@-------
--@-----
----@---
------@-
37번째 경우의수
---@----
-----@--
@-------
----@---
-@------
-------@
--@-----
------@-
38번째 경우의수
---@----
-----@--
-------@
-@------
------@-
@-------
--@-----
----@---
39번째 경우의수
---@----
-----@--
-------@
--@-----
@-------
------@-
----@---
-@------
40번째 경우의수
---@----
------@-
@-------
-------@
----@---
-@------
-----@--
--@-----
41번째 경우의수
---@----
------@-
--@-----
-------@
-@------
----@---
@-------
-----@--
42번째 경우의수
---@----
------@-
----@---
-@------
-----@--
@-------
--@-----
-------@
43번째 경우의수
---@----
------@-
----@---
--@-----
@-------
-----@--
-------@
-@------
44번째 경우의수
---@----
-------@
@-------
--@-----
-----@--
-@------
------@-
----@---
45번째 경우의수
---@----
-------@
@-------
----@---
------@-
-@------
-----@--
--@-----
46번째 경우의수
---@----
-------@
----@---
--@-----
@-------
------@-
-@------
-----@--
47번째 경우의수
----@---
@-------
---@----
-----@--
-------@
-@------
------@-
--@-----
48번째 경우의수
----@---
@-------
-------@
---@----
-@------
------@-
--@-----
-----@--
49번째 경우의수
----@---
@-------
-------@
-----@--
--@-----
------@-
-@------
---@----
50번째 경우의수
----@---
-@------
---@----
-----@--
-------@
--@-----
@-------
------@-
51번째 경우의수
----@---
-@------
---@----
------@-
--@-----
-------@
-----@--
@-------
52번째 경우의수
----@---
-@------
-----@--
@-------
------@-
---@----
-------@
--@-----
53번째 경우의수
----@---
-@------
-------@
@-------
---@----
------@-
--@-----
-----@--
54번째 경우의수
----@---
--@-----
@-------
-----@--
-------@
-@------
---@----
------@-
55번째 경우의수
----@---
--@-----
@-------
------@-
-@------
-------@
-----@--
---@----
56번째 경우의수
----@---
--@-----
-------@
---@----
------@-
@-------
-----@--
-@------
57번째 경우의수
----@---
------@-
@-------
--@-----
-------@
-----@--
---@----
-@------
58번째 경우의수
----@---
------@-
@-------
---@----
-@------
-------@
-----@--
--@-----
59번째 경우의수
----@---
------@-
-@------
---@----
-------@
@-------
--@-----
-----@--
60번째 경우의수
----@---
------@-
-@------
-----@--
--@-----
@-------
---@----
-------@
61번째 경우의수
----@---
------@-
-@------
-----@--
--@-----
@-------
-------@
---@----
62번째 경우의수
----@---
------@-
---@----
@-------
--@-----
-------@
-----@--
-@------
63번째 경우의수
----@---
-------@
---@----
@-------
--@-----
-----@--
-@------
------@-
64번째 경우의수
----@---
-------@
---@----
@-------
------@-
-@------
-----@--
--@-----
65번째 경우의수
-----@--
@-------
----@---
-@------
-------@
--@-----
------@-
---@----
66번째 경우의수
-----@--
-@------
------@-
@-------
--@-----
----@---
-------@
---@----
67번째 경우의수
-----@--
-@------
------@-
@-------
---@----
-------@
----@---
--@-----
68번째 경우의수
-----@--
--@-----
@-------
------@-
----@---
-------@
-@------
---@----
69번째 경우의수
-----@--
--@-----
@-------
-------@
---@----
-@------
------@-
----@---
70번째 경우의수
-----@--
--@-----
@-------
-------@
----@---
-@------
---@----
------@-
71번째 경우의수
-----@--
--@-----
----@---
------@-
@-------
---@----
-@------
-------@
72번째 경우의수
-----@--
--@-----
----@---
-------@
@-------
---@----
-@------
------@-
73번째 경우의수
-----@--
--@-----
------@-
-@------
---@----
-------@
@-------
----@---
74번째 경우의수
-----@--
--@-----
------@-
-@------
-------@
----@---
@-------
---@----
75번째 경우의수
-----@--
--@-----
------@-
---@----
@-------
-------@
-@------
----@---
76번째 경우의수
-----@--
---@----
@-------
----@---
-------@
-@------
------@-
--@-----
77번째 경우의수
-----@--
---@----
-@------
-------@
----@---
------@-
@-------
--@-----
78번째 경우의수
-----@--
---@----
------@-
@-------
--@-----
----@---
-@------
-------@
79번째 경우의수
-----@--
---@----
------@-
@-------
-------@
-@------
----@---
--@-----
80번째 경우의수
-----@--
-------@
-@------
---@----
@-------
------@-
----@---
--@-----
81번째 경우의수
------@-
@-------
--@-----
-------@
-----@--
---@----
-@------
----@---
82번째 경우의수
------@-
-@------
---@----
@-------
-------@
----@---
--@-----
-----@--
83번째 경우의수
------@-
-@------
-----@--
--@-----
@-------
---@----
-------@
----@---
84번째 경우의수
------@-
--@-----
@-------
-----@--
-------@
----@---
-@------
---@----
85번째 경우의수
------@-
--@-----
-------@
-@------
----@---
@-------
-----@--
---@----
86번째 경우의수
------@-
---@----
-@------
----@---
-------@
@-------
--@-----
-----@--
87번째 경우의수
------@-
---@----
-@------
-------@
-----@--
@-------
--@-----
----@---
88번째 경우의수
------@-
----@---
--@-----
@-------
-----@--
-------@
-@------
---@----
89번째 경우의수
-------@
-@------
---@----
@-------
------@-
----@---
--@-----
-----@--
90번째 경우의수
-------@
-@------
----@---
--@-----
@-------
------@-
---@----
-----@--
91번째 경우의수
-------@
--@-----
@-------
-----@--
-@------
----@---
------@-
---@----
92번째 경우의수
-------@
---@----
@-------
--@-----
-----@--
-@------
------@-
----@---
92
Program ended with exit code: 0
괜히 이상한 함수 파서 가능한 위치 리스트에 집어넣을려고 고생했네요... 저도 모르는 새에 중복 검사가 필요없게 알고리즘이 만들어진... 그나저나 제코드는 항상 왜이리 더러울까요 ㅠㅠ
#include <stdio.h>
#include <stdlib.h>
typedef struct linkedlist //data structrue linked list implementation.
{
int data[8];
struct linkedlist *next;
} LinkedQueens;
typedef struct allqueens //database which contains all possible 8-queen location.
{
int queensNum;
LinkedQueens *queensList;
} AllQueens;
LinkedQueens first;
LinkedQueens *pfirst = &first;
AllQueens Q = {0, NULL}; //global AllQueens var.
int num_of_8queen = 0;
int Delta(int a, int b) //returns the difference between a and b.
{
if (a>=b) return a-b;
else return b-a;
}
int IsValid(int queens[], int add_at)
{
//마지막 원소에 대해서만 검사하면 된다고 가정.
//i: iteration var
int i;
//마지막 원소의 index는 add_at
int last;
last = queens[add_at];
for(i=0;i<add_at;i++)
if (queens[i]==queens[add_at] || Delta(queens[i], queens[add_at]) == Delta(i,add_at)) return 0;
return 1;
}
int arraycmp(int a[], int b[]) //boolean "array a and b are same."
{
int i;
//assume a and b are both full.
for(i=0;i<a[8];i++)
if (a[i]!=b[i]) return 0;
return 1;
}
int IsIn(int q[]) //boolean "q is in Q.queensList"
{
LinkedQueens *lq;
for(lq=Q.queensList;lq!=NULL;lq=lq->next)
if (arraycmp(lq->data, q)) return 1;
return 0;
}
void ListUpdate(int q[]) //append q to Q.queensList
{
int i;
LinkedQueens *temp;
temp = Q.queensList;
//printf("hoo\n");
while (temp->next!=NULL)
{
temp = temp->next;
}
temp->next = malloc(sizeof(LinkedQueens));
for(i=0;i<8;i++)
{
temp->next->data[i] = q[i];
//printf("huh\n");
}
}
void BackTrack(int q[], int check_from, int add_at)
{
//if check_from is 8, end the program
if (check_from==8)
{
if (add_at==0) return;
add_at--;
check_from = q[add_at]+1;
BackTrack(q, check_from, add_at);
return;
}
//make array called "result" and copy q to it.
int *result;
result = (int *) malloc(sizeof(int)*8);
int i;
for(i=0;i<add_at;i++) result[i]=q[i];
//printf("hey\n");
//add_at = 8?
if (add_at==8)
{
add_at--;
check_from = q[add_at]+1;
int j;
for(j=0;j<8;j++) printf("%d ", q[j]);
printf("\n");
num_of_8queen++;
if (!IsIn(q))
{
//if (Q.queensList==NULL) Q.queensList
ListUpdate(q);
Q.queensNum++;
}
//printf("huh2\n");
BackTrack(q, check_from, add_at);
}
else
{
//printf("hee\n");
for(i=check_from;i<8;i++)
{
result[add_at]=i;
if (IsValid(result, add_at))
{
check_from = 0;
add_at++;
BackTrack(result, check_from, add_at);
return;
}
}
add_at--;
check_from = q[add_at]+1;
BackTrack(q, check_from, add_at);
}
}
int main()
{
Q.queensList = pfirst;
int q[8];
BackTrack(q, 0, 0);
LinkedQueens *probe;
printf("total: %d\n", num_of_8queen);
return 0;
}
void chkQueen(int queens[8], int stage, int *count)
{
for (int i = 0; i < 8; i++)
{
int chk = 0;
for (int j = 0; j < stage; j++)
{
if (queens[j] == i)
{
chk++;
break;
}
}
if (chk == 0)
{
for (int j = 0; j < stage; j++)
{
if (abs(queens[j] - i) == abs(stage - j))
{
chk++;
break;
}
}
}
if (chk == 0)
{
if (stage == 7)
(*count)++;
else
{
queens[stage] = i;
chkQueen(queens, stage + 1, count);
}
}
}
}
void exce6()
{
int queens[8];
int count = 0;
for (int i = 0; i < 8; i++)
queens[i] = -1;
chkQueen(queens,0, &count);
printf("%d가지\n", count);
}
우리가 원하는건 몇번째행 몇번째열에 깔면 되는지 알면 되는거니까 굳이 2차원 배열로 일일이 찍어보기보단 1차원 배열에다가 값을 몇번째인가로 표시였습니다.
이렇게 하면 기본적으로 각 행에 하나밖에 들어 갈 수 없으니 행 중복은 체크 할 필요 없구요 열 중복은 배열 안에 같은 숫자값이 있는지만 체크 하면됩니다. 대각선 중복 체크는 현재 위치에서n번째 거리에 있는 배열원소값이 나와 n만큼 차이나면 중복입니다.
import copy
w,h = 8,8
n=8
sol = []
def conflict(qlist,i,j):
for (qi,qj) in qlist:
if qi==i or qj==j or (abs(qi-i)==abs(qj-j)):
return True
return False
def nextQ(qlist):
re = []
lastQ = (0,0)
if len(qlist)!=0:
lastQ = qlist[-1]
else:
re.append((0,0))
for i in range(lastQ[0], h):
for j in range(w):
if i==lastQ[0] and j<=lastQ[1]:
continue
if not conflict(qlist, i, j):
re.append((i,j))
return re
def backtrack(qlist):
if len(qlist)==n:
sol.append(qlist)
else:
nextQs = nextQ(qlist)
while len(nextQs)!=0:
q = nextQs.pop(0)
cqlist = copy.deepcopy(qlist)
cqlist.append(q)
backtrack(cqlist)
def result_print():
print '<<<<solution>>>>'
for s in sol:
board = [['.' for i in range(w)] for i in range(h)]
for q in s:
board[q[0]][q[1]] = 'Q'
for i in range(h):
for j in range(w):
print '%2s' % board[i][j],
print ''
print ''
if __name__ == '__main__':
backtrack([])
print len(sol)
- Backtracking을 적용한 코드입니다.
- 현재까지 둔 queen의 좌표를 qlist에서 저장하고, qlist와 'conflict' 발생하지 않는 새로운 좌표를 찾습니다.
- 새로 찾은 좌표를 하나씩 qlist에 넣어서 계속 진행하고, 진행 도중 n개의 queen 좌표를 찾으면 solution에 추가합니다.
python 3.5
# N Queen Problem
N = 8
def placeQueen(queen_pos):
res = 0
n = len(queen_pos)
if n == N:
return 1
for i in range(N):
for j in range(n):
if i == queen_pos[j]: break
if n - j == i - queen_pos[j]: break
if n - j == queen_pos[j] - i: break
else:
res += placeQueen(queen_pos + [i])
return res
print(placeQueen([]))
python3으로 짰습니다. 퀸을 놓을 수 있는 곳을 0으로, 놓을 수 있는 곳을 1로 마킹하면서 재귀적으로 한줄씩 탐색하도록 알고리즘을 구성했습니다.
board = [[0 for y in range(0, 8)] for x in range(0, 8)]
def mark(l, bd):
nbd = [x[:] for x in bd[1:]]
for i in range(0, len(nbd)):
nbd[i][l] = 1
if l + i + 1 < 8: nbd[i][l + i + 1] = 1
if l - i - 1 >= 0: nbd[i][l - i - 1] = 1
return nbd
def checkline(bd):
if len(bd) == 0: return 1
cnt = 0
for l in range(0, 8):
if bd[0][l] == 0:
newbd = mark(l, bd)
cnt += checkline(newbd)
return cnt
print (checkline(board))
#include <iostream>
#include <chrono>
using namespace std;
bool isCollided(int(*board)[8], int pinX, int pinY)
{
for (int y = pinY - 1, xGap = 1; y >= 0; --y, ++xGap)
{
if (board[pinX][y] == 1
||
pinX - xGap >= 0 && board[pinX - xGap][y] == 1
||
pinX + xGap < 8 && board[pinX + xGap][y] == 1)
{
return true;
}
}
return false;
}
int setQueenAt(int(*board)[8], int line)
{
int completeCount = 0;
for (int x = 0; x < 8; ++x)
{
// Queen 배치
board[x][line] = 1;
// 다른 Queen과 충돌했으면 우측으로 넘어가고 아니면 다음 줄로 이어서 배치
if (isCollided(board, x, line))
{
// 현재 위치의 Queen 제거
board[x][line] = 0;
}
else
{
// 다음 줄이 있으면 이어서 Queen 배치
if (line < 7)
{
completeCount += setQueenAt(board, line + 1);
// Queen 제거
board[x][line] = 0;
}
else
{
// 마지막 줄 까지 충돌없이 배치에 성공했다는건
// 충돌이 없는 8 Queen 배치를 성공했다는 뜻
++completeCount;
}
}
}
return completeCount;
}
int main()
{
chrono::system_clock::time_point startTime = chrono::system_clock::now();
int board[8][8];
memset(board, 0, sizeof(board));
int completeCount = 0;
// 첫번째 가로줄의 첫번째 칸부터 Queen 배치를 시작
for (int x = 0; x < 8; ++x)
{
// Queen 설치
board[x][0] = 1;
// 이어서 다음 줄에 Queen 배치
completeCount += setQueenAt(board, 1);
// Queen 제거
board[x][0] = 0;
}
// 결과 출력
cout << completeCount << endl;
// 소요시간 출력
chrono::duration<double> leftTime = chrono::system_clock::now() - startTime;
cout << leftTime.count() << "s" << endl;
return 0;
}
문제에서 뽑아낸 전제조건으로 알고리즘을 최적화 시켰습니다.
답은 92 시간은 0.001초 내외입니다.
- python으로 작성하였습니다. 행(row)단위로 진행하며 queen을 이전까지 queen 위치로 구한 deadSpace를 피해 두는 로직으로 작성하였습니다.
leftM=lambda p:(p%8)+1
rightM=lambda p:8-(p%8)
upperM=lambda p:p//8+1
downM=lambda p:8-(p//8)
def getDeadSpaceX(p):
dl=set([p+(i*7) for i in range(0,min(downM(p),leftM(p))) if (p+(i*7))<64])
ur=set([p+(i*-7) for i in range(0,min(upperM(p),rightM(p))) if p+(i*-7)>=0])
dr=set([p+(i*9) for i in range(0,min(downM(p),rightM(p))) if p+(i*9)<64])
ul=set([p+(i*-9) for i in range(0,min(upperM(p),leftM(p))) if p+(i*-9)>=0])
return (dl|ur|dr|ul)
def getSafeSpace(pos,depth,safeSpace):
deadSpace=set([])
for pi in pos:
deadSpaceRow=set(range((pi//8)*8,(pi//8+1)*8))
deadSpaceColumn=set(range(pi%8,64,8))
deadSpaceX=getDeadSpaceX(pi)
deadSpace|=(deadSpaceRow|deadSpaceColumn|deadSpaceX)
for p in range(depth*8,(depth+1)*8):
if p not in deadSpace:
pos1=pos[:]
pos1.append(p)
if depth==7:
safeSpace.append(pos1)
else:
getSafeSpace(pos1,depth+1,safeSpace)
safeSpace=[]
getSafeSpace([],0,safeSpace)
print len(safeSpace)
print safeSpace
파이썬 2.7 입니다 숫자 8개의 순열을 하면 가로와 세로가 충돌하지 않는 8!개의 조합이 나옵니다. 여기서 대각선끼리 서로 충돌하지 않는지만 검사해서 카운팅을 했습니다.
from itertools import permutations as perm
count = 0
for case in perm(range(8)):
diagonalCollision = False
for i in range(7):
subcase = case[i+1:]
if case[i] in [subcase[j]+j+1 for j in range(len(subcase))] or\
case[i] in [subcase[j]-j-1 for j in range(len(subcase))]:
diagonalCollision = True
break
if not diagonalCollision :
count+=1
print count
global count
count = 0
def copy(br):
tmp = []
for x in br:
tmp.append(x[:])
return tmp
def locate(b, co):
br = copy(b)
y, x = (co[0], co[1])
if br[y][x] == 1:pass
else:
for i in range(8):
br[i][x] = 1
br[y][i] = 1
for i in range(min(x,7-y)):br[y+i+1][x-i-1] = 1
for i in range(min(x,y)):br[y-i-1][x-i-1] = 1
for i in range(min(7-x,7-y)):br[y+i+1][x+i+1] = 1
for i in range(min(7-x,y)):br[y-i-1][x+i+1] = 1
return br
def newbr(li = []):
br = li[:]
if br == []:
for i in range(8):
br.append([])
for j in range(8):
br[i].append(0)
return br
def n0(br, y):
tmp = []
if len(br[y]) == 0:return tmp
for x in range(len(br[y])):
if br[y][x] == 0:
tmp.append(x)
return tmp
def cal(br, depth = 0):
l0 = n0(br, depth)
if depth == 7:
global count
count += 1
return
for x in l0:
tmp = copy(br)
tmp = locate(tmp, (depth, x))
if len(n0(tmp, depth+1)) != 0:
cal(tmp, depth+1)
if __name__ == '__main__':
board = newbr()
cal(board)
print('\n'+str(count))
분명 리스트를 복사했는데 레퍼런스 취급돼서 한동안 머리를 싸맸습니다. 알고보니 이중 리스트 [[],[],[]] 의 [], [], [] 이게 레퍼런스더군요;; 파이썬 3.5.1
첫 행부터 시작해서 0 ~ 7의 각 위치에 퀸이 있는 경우 그 아래 행들은 맨 위행의 퀸과 같은 열과 그 대각선 위치에는 퀸을 놓을 수 없습니다.
따라서 첫 행에 한 위치에 퀸을 놓고 그 아래 행들에서 퀸을 놓을 수 없는 위치를 표시한 후, 아래 행들에서는 놓을 수 있는 위치만 검사합니다. 이런 식으로 재귀로 작성했습니다.
from copy import copy
def check(avs=None,):
if avs is None:
avs = [[True] * 8 for _ in range(8)]
result = 0
if len(avs) is 0:
return 1
head, *tail = avs
for a in range(8):
if not head[a]:
continue
navs = [copy(l) for l in tail]
for i, line in enumerate(navs):
line[a] = False
if (a - i - 1) >= 0:
line[a - i - 1] = False
if (a + i + 1) < 8:
line[a + i + 1] = False
result += check(navs)
return result
%time print(check())
# 24ms
Ruby
row를 증가시키며 재귀로 탐색. valid로 걸러진 각각을 카운트.
valid = ->xy,x,y { xy.reject {|cx,cy| cx==x || cy==y || cx+cy==x+y || cx-cy==x-y } }
cnt = ->n,xy,r=1 { xy.select {|x,y|x==r}.sum {|e|r<n ? cnt[n,valid[xy,*e],r+1]:1 } }
queens = ->n,m=[*1..n] { cnt[n, m.product(m)] }
Test
expect(queens[2]).to eq 0
expect(queens[4]).to eq 2
expect(queens[6]).to eq 4
expect(queens[7]).to eq 40
expect(queens[8]).to eq 92
expect(queens[10]).to eq 724
# for performance
expect(Benchmark.realtime { queens[8] }).to be_between(0.001, 0.008)
user system total real
8 Queens : 0.000000 0.000000 0.000000 ( 0.006572)
Output
=> queens[8]
92
package main
import (
"fmt"
"sync"
)
type Board struct {
data [8][8]int
count int
}
func (b Board) Puttable(x, y int) bool {
if x == 0 {
return true
}
j := y
k := y
for i := x-1; i >= 0; i-- {
j--
k++
if b.data[y][i] != 0 || (j >= 0 && b.data[j][i] != 0) || (k < 8 && b.data[k][i] != 0) {
return false
}
}
return true
}
func (b *Board) Set(x, y int) {
b.data[y][x] = 1
}
func (b *Board) Clear(x, y int) {
b.data[y][x] = 0
}
func (b *Board) Put(x, y int) bool {
if b.Puttable(x, y) {
b.Set(x, y)
if x == 7 {
b.count++
b.Clear(x, y)
return true
}
} else {
return false
}
x++
for i := 0; i < 8; i++ {
b.Put(x, i)
b.Clear(x, i)
}
return false
}
func main() {
board := [8]Board{}
count := 0
ch := make(chan int)
wg := sync.WaitGroup{}
for i := 0; i < 8; i++ {
wg.Add(1)
go func(i int) {
defer wg.Done()
board[i].Put(0, i)
ch <- board[i].count
}(i)
}
go func() {
wg.Wait()
close(ch)
}()
for c := range ch {
count += c
}
fmt.Println(count)
}
Delphi 2010 으로 변환함. ( iljimae님의 코드 참조)
function fnFindEightQueens(C_Queens: Integer): Integer;
var cnt: Integer;
pos: array of Integer;
function chk(queen, rowpos: Integer): boolean;
var i, rowpos2: Integer;
begin
for i := 0 to queen - 1 do
begin
rowpos2 := pos[i];
if (rowpos2 = rowpos) or (rowpos2 = rowpos - (queen - i)) or (rowpos2 = rowpos + (queen - i)) then
exit(False);
end;
result := true;
end;
procedure recur(x: Integer);
var i: Integer;
s: string;
begin
// if cnt > 0 then //1개만 찾는 경우
// Exit;
if (x = C_Queens) then
begin
Inc(cnt);
// Display 8 Queen Pos
// s := format('%2d: ', [cnt]);
// for i := 0 to C_Queens - 1 do
// s := s + format('%3d', [pos[i]]);
// Memo1.Lines.Add(s);
end
else
begin
for i := 0 to C_Queens - 1 do
begin
if chk(x, i) then
begin
pos[x] := i;
recur(x + 1);
end;
end;
end;
end;
begin
cnt := 0;
SetLength(pos, C_Queens + 1);
recur(0);
result := cnt;
end;
procedure TForm4.btnFind8QueenClick(Sender: TObject);
begin
Caption := IntToStr(fnFindEightQueens(8)); //8 Queens
end;
function fnFindEightQueens(C_Queens: Integer): Integer;
var
cnt: Integer;
pos: array of Integer;
function chk(queen, rowpos: Integer): boolean;
var
i, rowpos2: Integer;
begin
for i := 0 to queen - 1 do
begin
rowpos2 := pos[i];
if (rowpos2 = rowpos) or (rowpos2 = rowpos - (queen - i)) or (rowpos2 = rowpos + (queen - i)) then
exit(False);
end;
result := true;
end;
procedure recur(x: Integer);
var
i: Integer;
s: string;
begin
// if cnt > 0 then //1개만 찾는 경우
// Exit;
if (x = C_Queens) then
begin
Inc(cnt);
// Display 8 Queen Pos
// s := format('%2d: ', [cnt]);
// for i := 0 to C_Queens - 1 do
// s := s + format('%3d', [pos[i]]);
// Memo1.Lines.Add(s);
end
else
begin
for i := 0 to C_Queens - 1 do
begin
if chk(x, i) then
begin
pos[x] := i;
recur(x + 1);
end;
end;
end;
end;
begin
cnt := 0;
SetLength(pos, C_Queens + 1);
recur(0);
result := cnt;
end;
procedure TForm4.btnFind8QueenClick(Sender: TObject);
begin
Caption := IntToStr(fnFindEightQueens(13));
end;
체스판 사이즈는 size 변수로 퀸의 수는 count 변수로 조정 가능 ex) count = -8 퀸 8개 , -7 퀸 7개
#include <stdio.h>
#include <stdlib.h>
int cal(int** board);
int putChessPiece(int** board, int x, int y);
int rChessPiece(int** board, int x, int y);
int size = 8;
int count = -8;
int c = 0;
void main(void)
{
int NoC = 0;
int** board = (int**) malloc (sizeof(int*) * size);
for(int i = 0;i< size; i++)
board[i] = (int*) malloc (sizeof(int) * size);
for(int i = 0;i< size; i++)
for(int j = 0;j< size; j++)
board[i][j] = 0;
NoC = cal(board);
printf("\n\n");
printf("\n경우의 수 : %d\n", NoC);
}
int cal(int** board) {
for(int i = 0;i< size; i++) {
for(int j = 0;j< size; j++) {
if(board[i][j] > count && board[i][j] < 1) {
putChessPiece(board, i, j) ;
count++;
int temp = 0; // 0의 갯수
for(int k = 0;k< size; k++) {
for(int l = 0;l< size; l++) {
if(board[k][l] == 0)
temp++;
}
}
if(temp != 0) { // 0의 갯수가 하나라도 존재 할 때
cal(board);
}
if(count == 0) {
c++;
}
count--;
rChessPiece(board, i, j);
}
}
}
for(int i = 0;i< size; i++) {
for(int j = 0;j< size; j++) {
if(board[i][j] == count)
board[i][j] = 0;
}
}
return c;
}
int rChessPiece(int** board, int x, int y) {
for(int i = 0;i< size; i++) {
for(int j = 0;j< size; j++) {
if( x == i && board[i][j] > 0) {
board[i][j]--;
}
if( y == j && board[i][j] > 0) {
board[i][j]--;
}
if( (y-j) == (x-i) && board[i][j] > 0) {
board[i][j]--;
}
if( (y-j) == (i-x) && board[i][j] > 0) {
board[i][j]--;
}
}
}
board[x][y] = count;
return 0;
}
int putChessPiece(int** board, int x, int y) {
for(int i = 0;i< size; i++) {
for(int j = 0;j< size; j++) {
if( x == i && board[i][j] >= 0) {
board[i][j]++;
}
if( y == j && board[i][j] >= 0) {
board[i][j]++;
}
if( (y-j) == (x-i) && board[i][j] >= 0) {
board[i][j]++;
}
if( (y-j) == (i-x) && board[i][j] >= 0) {
board[i][j]++;
}
}
}
board[x][y] = count;
return 0;
}
#include <stdio.h>
#define SIZE 8
#define QUEEN 9
#define NONE 0
int s = 0;
void clearBoard(int board[SIZE][SIZE]) {
for(int i = 0; i < SIZE; i++) {
for(int j = 0; j < SIZE; j++) {
board[i][j] = 0;
}
}
}
void printBoard(int board[SIZE][SIZE]) {
printf("\nNo.%d\n+",s);
for(int i = 0; i < SIZE; i++) {
printf("-+");
}
printf("\n");
for(int i = 0; i < SIZE; i++) {
printf("|");
for(int j = 0; j < SIZE; j++) {
switch(board[i][j]) {
case QUEEN:
printf("Q|");
break;
case NONE:
printf(" |");
break;
default:
printf(".|");
break;
}
}
printf("\n+");
for(int i = 0; i < SIZE; i++) {
printf("-+");
}
printf("\n");
}
}
int putQueen(int row, int board[SIZE][SIZE]) {
int leftCol, rightCol;
for(int col = 0; col < SIZE; col++) {
if(board[row][col] == 0) {
if(row < SIZE) {
board[row][col] = QUEEN;
leftCol = col, rightCol = col;
for(int nextRow = row + 1; nextRow < 8; nextRow++) {
board[nextRow][col]++;
if(leftCol > 0)
board[nextRow][--leftCol]++;
if(rightCol < SIZE - 1)
board[nextRow][++rightCol]++;
}
putQueen(row + 1, board);
board[row][col] = NONE;
leftCol = col, rightCol = col;
for(int nextRow = row + 1; nextRow < 8; nextRow++) {
board[nextRow][col]--;
if(leftCol > 0)
board[nextRow][--leftCol]--;
if(rightCol < SIZE - 1)
board[nextRow][++rightCol]--;
}
} else {
s++;
board[row][col] = QUEEN;
printBoard(board);
board[row][col] = NONE;
}
}
}
}
int main(){
int board[SIZE][SIZE];
clearBoard(board);
putQueen(0, board);
}
.....
생략
.....
No.90
+-+-+-+-+-+-+-+-+
| | | | | | | |Q|
+-+-+-+-+-+-+-+-+
| |Q| | | | |.|.|
+-+-+-+-+-+-+-+-+
|.|.|.| |Q|.| |.|
+-+-+-+-+-+-+-+-+
| |.|Q|.|.|.| |.|
+-+-+-+-+-+-+-+-+
|Q|.|.|.|.| |.|.|
+-+-+-+-+-+-+-+-+
|.|.|.| |.|.|Q|.|
+-+-+-+-+-+-+-+-+
|.|.|.|Q|.|.|.|.|
+-+-+-+-+-+-+-+-+
|.|.|.|.|.|Q|.|.|
+-+-+-+-+-+-+-+-+
No.91
+-+-+-+-+-+-+-+-+
| | | | | | | |Q|
+-+-+-+-+-+-+-+-+
| | |Q| | | |.|.|
+-+-+-+-+-+-+-+-+
|Q|.|.|.| |.| |.|
+-+-+-+-+-+-+-+-+
|.|.|.| |.|Q| |.|
+-+-+-+-+-+-+-+-+
|.|Q|.|.|.|.|.|.|
+-+-+-+-+-+-+-+-+
|.|.|.|.|Q|.|.|.|
+-+-+-+-+-+-+-+-+
|.|.|.|.|.|.|Q|.|
+-+-+-+-+-+-+-+-+
|.|.|.|Q|.|.|.|.|
+-+-+-+-+-+-+-+-+
No.92
+-+-+-+-+-+-+-+-+
| | | | | | | |Q|
+-+-+-+-+-+-+-+-+
| | | |Q| | |.|.|
+-+-+-+-+-+-+-+-+
|Q| |.|.|.|.| |.|
+-+-+-+-+-+-+-+-+
|.|.|Q|.|.|.| |.|
+-+-+-+-+-+-+-+-+
|.|.|.|.| |Q|.|.|
+-+-+-+-+-+-+-+-+
|.|Q|.|.|.|.|.|.|
+-+-+-+-+-+-+-+-+
|.|.|.|.|.|.|Q|.|
+-+-+-+-+-+-+-+-+
|.|.|.|.|Q|.|.|.|
+-+-+-+-+-+-+-+-+
D:\16.minGW>
파이썬3.5
1. N x N board를 만들고, chk(board) 하면 최초 라인의 퀸을 놓을 수 있는 좌표(ij)를 튜플들을 리턴한다.
2. 반환된 튜플들을 fill(board, ij)로 1로 표시하고 가로,세로,대각선은 'x'로 표시한다.
3. 빈공간이 없을때까지 1, 2번을 반복한다.
4. board의 숫자합이 N 이 되면 1을 리턴하고, 그렇지 않으면 0을 리턴한다.
5. 리턴값을 더한값이 답이다.
import copy
def chk(board):
ij = []
for (i, line) in enumerate(board):
for (j, x) in enumerate(line):
if x == 0:
ij.append((i, j))
if ij:
return ij
def fill(board_, ij):
board = copy.deepcopy(board_)
i, j = ij
for x in range(N):
board[i][x] = 'x'
for y in range(N):
board[y][j] = 'x'
for n in range(1, N):
if i-n >= 0 and j-n >= 0:
board[i-n][j-n] = 'x'
if i-n >= 0 and j+n < N:
board[i-n][j+n] = 'x'
if i+n < N and j-n >= 0:
board[i+n][j-n] = 'x'
if i+n < N and j+n < N:
board[i+n][j+n] = 'x'
board[i][j] = 1
return board
def f(board):
if not any(0 == x for line in board for x in line):
if sum(x for line in board for x in line if type(x) != str) == N:
return 1
else:
return 0
return sum(f(fill(board, ij)) for ij in chk(board))
N = 8
board = [[0] * N for _ in range(N)]
print(f(board))
# 92
# 1 loop, best of 3: 245 ms per loop
#!/usr/bin/python3
import copy
class Board():
col = 8
row = 8
def __init__(self):
self.board = [[None for col in range(self.row)] for j in range(self.col)]
self.queen_arr = []
def __str__(self):
s = ''
for c in range(self.col):
for r in range(self.row):
if self.board[c][r] == 2:
s += "%4s " % 'Q'
else:
s += "%4s " % self.board[c][r]
s += '\n'
return s
def clean(self):
self.board = [[None for col in range(self.row)] for j in range(self.col)]
def ableQ(self,col,row):
col -= 1
row -= 1
if self.board[col][row] == None:
return True
else :
return False
def queen(self, col, row):
if (col < 1 or col > 9) or (row < 1 or row > 9):
return False
col -= 1
row -= 1
for i in range(8):
self.board[col][i] = 1
self.board[i][row] = 1
for i in range(8):
if col+i > 7 or row+i > 7:
break
self.board[col+i][row+i] = 1
for i in range(8):
if col-i < 0 or row-i < 0:
break
self.board[col-i][row-i] = 1
for i in range(8):
if col-i < 0 or row+i > 7:
break
self.board[col-i][row+i] = 1
for i in range(8):
if col+i > 7 or row-i < 0:
break
self.board[col+i][row-i] = 1
self.queen_arr.append(str(col)+str(row))
self.queen_set()
return True
def queen_set(self):
for arr in self.queen_arr:
self.board[int(arr[0])][int(arr[1])] = 2
def queen_recursive(board,num):
b = None
count = 0
for i in range(1,9):
b = copy.deepcopy(board)
if b.ableQ(num,i):
b.queen(num,i)
if num > 1 :
count += queen_recursive(b,num-1)
else:
count += 1
return count
b = Board()
print(queen_recursive(b, 8))
파이썬3
#!/usr/bin/env python3
# 검사배열
cols = [0 for _ in range(10)] # cols[10]
inc = [0 for _ in range(20)] # inc[20], 증가하는 대각선, 좌표합은 일정, 4x4에서 2~8
dec = [0 for _ in range(20)] # dec[20], 감소하는 대각선, 좌표차는 일정
# 인덱스가 음수가 되면 안되므로 안정범위로 조절
# 4x4에서 -3~3이므로 증가하는 대각선과 맞추기
# 위해 5를 더하면 되는데, 이는 N+1임.
cnt = 0
def solve(row):
global cnt #
if row > N:
cnt += 1
return
for col in range(1, N + 1):
incN = row + col
decN = N + (row - col) + 1
# 검사배열 조건에 맞다면
if not cols[col] and not inc[incN] and not dec[decN]:
cols[col] = inc[incN] = dec[decN] = 1 # 체크
solve(row + 1)
cols[col] = inc[incN] = dec[decN] = 0 # 백트랙킹
if __name__ == '__main__':
N = 8 # 체스판 크기 및 퀸의 수
solve(1) # 1 행에 퀸을 놓는다
print(cnt)
# 보드는 1, 1 부터 시작한다고 가정
# 퀸은 한 행에 하나만 존재 할 수 있다
# 퀸을 1, 1부터 놓으면, 그 다음 퀸은 2행부터 놓아야한다
# 2행부터는 퀸이 놓일 자리를 대각선, 같은 열을 피해서 놓아야한다
# 놓아야 할 자리, 놓지 말아야 할 자리를 판단하기 위해 열, 증가대각선,
# 감소대각선 별로 배열을 준비한다. 이를 검사배열이라고 하자
# 퀸을 임의의 위치에 놓았다면 각 검사배열에 맞는 인덱스를 찾아서 1로 채운다
# 퀸을 놓는 함수는 그 다음 행으로 호출한다
# 함수호출의 종료조건은 보드 크기보다 인자의 행이 더 클때 종료한다
# 종료된 함수는 그 전의 검사배열에 체크했던 인덱스를 찾아가 지워야한다
# 이를 백트랙킹이라고 한다
javascript
var queens = [];
var count = 0;
var place = function (row, col) {
console.log(row, col, queens)
for (let i = 0; i < row; i++) {
if (queens[i] === col || queens[i] === col - (row - i) || queens[i] === col + (row - i)) {
return false;
}
}
return true;
};
var chess = function (row) {
if (row == 8) count++;
for (let col = 0; col < 8; col++) {
if (place(row, col)) {
queens[row] = col;
chess(row + 1);
}
}
}
chess(0);
console.log(count);
굳이 8x8 판을 만들지 않고 좌표만으로 계산합니다.
def cross(p, q):
return p[1] == q[1] or abs(p[0] - q[0]) == abs(p[1] - q[1])
# 1줄에 하나씩 배치
def queens(x, Q):
if x >= 8:
return 1
else:
return sum([
queens(x + 1, Q + [(x, y)])
for y in range(8)
if all([not cross((x, y), (qx, qy)) for (qx, qy) in Q])
])
print(queens(0, [])) # 92
JAVA입니다.
public class eX014 {
static byte[][] screen = new byte[8][8];
static int caseCount = 0;
public static void main(String[] args) {
// TODO Auto-generated method stub
//
long start = System.nanoTime();
count(0);
System.out.println("경우의수: "+ String.valueOf(caseCount));
long stop = System.nanoTime();
System.out.println(stop - start + " ns");
System.out.println((stop - start) / 1000000 + " ms");
System.out.println((stop - start) / 1000000 / 1000 + " sec");
}
static void count(int row) {
//해당 행의 모든 열을 탐색하여 퀸이 놓일 수 있는 위치의 개수를 구한다.
for(int i=0; i<screen[0].length; i++) {
//해당 위치에 퀸을 놓는다.(1대입)
screen[row][i] = 1;
//해당 위치에 퀸을 놓을 수 있으면 true, 아니면 false
if(canSet(row,i)) {
if(row == screen.length-1) {
caseCount += 1;
screen[row][i] = 0;
continue;
}
count(row+1);
}
//해당 위치에 놓아져있는 퀸을 뺀다!
screen[row][i] = 0;
}
}
static boolean canSet(int row, int column) {
//세로체크
for(int i=0; i< screen.length; i++) {
if(i == row)
continue;
if(screen[i][column] == 1)
return false;
}
//가로체크
for(int i=0; i<screen[0].length; i++) {
if(i == column)
continue;
if(screen[row][i] == 1)
return false;
}
int cRow,cColumn;
//우상단대각 체크(우상단방향)
for(cRow = row-1, cColumn=column+1; ( cRow >= 0 && cColumn < screen[0].length ); cRow-=1,cColumn+=1) {
if(screen[cRow][cColumn] == 1)
return false;
}
//우상단대각 체크(좌하단방향)
for(cRow = row+1, cColumn=column-1; ( cRow < screen.length && cColumn >= 0 ); cRow+=1,cColumn-=1) {
if(screen[cRow][cColumn] == 1)
return false;
}
//좌상단대각 체크(좌상단방향)
for(cRow = row-1, cColumn=column-1; ( cRow >= 0 && cColumn >= 0 ); cRow-=1,cColumn-=1) {
if(screen[cRow][cColumn] == 1)
return false;
}
//좌상단대각 체크(우하단방향)
for(cRow = row+1, cColumn=column+1; ( cRow < screen.length && cColumn < screen[0].length ); cRow+=1,cColumn+=1) {
if(screen[cRow][cColumn] == 1)
return false;
}
return true;
}
}
<결과 및 실행시간> 경우의수: 92 2639911 ns 2 ms 0 sec
8x8 byte배열을 만듭니다. 퀸이 놓여져 있는 부분은 1대입, 이외에 0(기본값) 맨처음 0번째 행부터 시작합니다. 0번째 행의 0~7번째 열을 반복문으로 탐색합니다. 반복문이 돌며 해당 위치에 퀸을 놓을 수 있는지 검사를 합니다.(canSet함수) 해당 위치에 퀸을 놓을 수 있다면 다음 행에 대해서 위의 과정을 반복합니다.(재귀) 마지막 행을 검사할 때, 퀸을 놓을 수 있는 위치가 발견된다면 case가 1개 발견되었으므로 변수에 +1을 해줍니다.
코드가 더럽다고 생각되네요... 비효율적인 부분이나, 코드를 깔끔히 정리할 수 있어 보이는 부분 지적 부탁드립니다.(__)
[Python 3.6]
import math
cnt = 0
def findQueenPosition(positionArray, line):
global cnt
if(line == 8):
cnt += 1
return
for row in range(8):
newPositionArray = ckeckQueenPosition(positionArray, line, row)
if(newPositionArray):
findQueenPosition(newPositionArray, line + 1)
def ckeckQueenPosition(positionArray, line, row):
newPositionArray = positionArray[:]
for position in newPositionArray:
if (position[0] == line or position[1] == row or math.fabs(position[0] - line) == math.fabs(position[1] - row)): return
newPositionArray.append((line, row))
return newPositionArray
findQueenPosition([], 0)
print(cnt)
Python 3으로 풀었습니다.
def count_of_eight_queens():
def can_choose(columns, new_c):
new_r = len(columns)
for r in range(len(columns)):
c = columns[r]
if new_c == c or abs(new_r - r) == abs(new_c - c):
return False
return True
def choose_in(columns, items):
if not items:
nonlocal count
count += 1
# print(columns)
return
for col_idx in range(len(items)):
col = items[col_idx]
if can_choose(columns, col):
columns.append(col)
choose_in(columns, items[0:col_idx] + items[col_idx+1:])
columns.remove(col)
count = 0
columns = []
items = [i for i in range(8)]
choose_in(columns, items)
return count
// Queen 클래스
namespace CodingTest
{
class Queens
{
int row;
int col;
public static int count = 0;
// 마지막으로 성공했던 상위 위치를 저장합니다.
Queens parent;
public Queens(int row,int col,Queens parent)
{
this.row = row;
this.col = col;
this.parent = parent;
}
// 이 위치에 놓여도 안전한지 다른 Queen과 비교합니다.
bool IsSafe(Queens other)
{
if(this.row != other.row && this.col != other.col && Math.Abs(this.row-other.row) != Math.Abs(this.col-other.col))
{
return true;
}
return false;
}
// 재귀호출
public void Test()
{
var row = this.row + 1;
if (row >7)
{
return;
}
for (int col = 0; col < 8; col++)
{
Queens queens = new Queens(row, col,this);
var parent = queens.parent;
bool success = false;
// 현재 위치와 지금까지 성공했던 위치들과 비교해서 모두 안전하면 다음 줄로 이동합니다.
while(parent != null)
{
if (parent.IsSafe(queens))
{
if(parent.parent == null)
{
success = true;
break;
}
else
{
parent = parent.parent;
}
}
else
{
break;
}
}
if (success)
{ // 체스의 마지막 줄이면 성공.
if(row == 7)
{
count++;
}
else //다음 줄로 가서 다시 테스트.
{
queens.Test();
}
}
}
}
}
}
// 테스트 코드
namespace CodingTest
{
class Program
{
static void Main(string[] args)
{
int row = 0;
System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
timer.Start();
for(int col = 0; col < 8; col++)
{
Queens queens = new Queens(row, col,null);
queens.Test();
}
timer.Stop();
Console.WriteLine("elapsed: {0} , count: {1}",timer.ElapsedMilliseconds,Queens.count);
}
}
}
1~2 밀리 초가 걸리고 92가 나옵니다.
import java.util.ArrayList;
public class Main {
static final int size = 8;
static final int q = 8;
public static boolean isSafe(int row, int col, int[] queens){
//row : row of queen to be placed
//col : cul of queen to be placed
//queens : contains (row-1) queens whose row is index, and column is element
for(int i=0; i<row; i++){
if(queens[i]==col||Math.abs(queens[i]-col)==Math.abs(i-row)) return false;
}
return true;
}
public static ArrayList<int[]> NQueen(){
ArrayList<int[]> ans = new ArrayList<int[]>();
int[] queens = new int[size];
NQ(0,queens,ans);
return ans;
}
public static void NQ(int row, int[] queens,ArrayList<int[]> ans){
//row : current row/current # of queens-1
//queens : contains (row-1) queens whose row is index, and column is element
for(int i=0; i<size; i++){
//columns
queens[row] = i;
if(isSafe(row,i,queens)){
if(row==q-1){
ans.add(queens);
}
else NQ(row+1,queens,ans);
}
}
}
public static void main(String[] args) {
ArrayList<int[]> ans = NQueen();
System.out.println(ans.size());
}
}
가로세로가 중복되지 않는 8!개의 후보 중에서 대각선상으로도 중복되지 않는 (<=> x+y 또는 x-y가 겹치지 않는) 해를 찾습니다.
solutions :: [[(Int, Int)]]
solutions = filter (liftA2 (&&) diagChk1 diagChk2) possibleSolutions
where
possibleSolutions = zip [1..] <$> permutations [1..8]
diagChk1 = (== 8) . length . nub . fmap (uncurry (+))
diagChk2 = diagChk1 . fmap (fmap negate)
main = putStrLn . show $ length $ solutions
파이썬 3.6
"""
아이디어> # back-tracking 기법 적용
1. 각 행에 queen은 한개만 올 수 있으므로, 각 행의 퀸의 위치를 요소로 하는 리스트를 생성합니다.
2. 각 행(col)의 각 열마다 퀸이 위치했을때, 그 다음 행(col+1)에 대해 퀸을 놓을 수 있는 위치를 (back_tracking(col+1)) 찾습니다.
3. col이 n이 된다면 (n-1)행까지 퀸을 조건에 맞는 위치에 무사히 놓게되는 것이므로 '해'로 판단하고 result에 담습니다.(이때, result에 같은'해'가 있는 지 확인합니다.)
"""
def back_tracking(col):
tmp = []
queens = [['x' for i in range(n)] for i in range(n)]
if col == n: # n-1 번째 행까지 무사히 퀸을 놓은 경우 '해'이므로 result에 담습니다.
if len(set(chess)) == n:
if chess not in result: # '해' 중복 체크
tmp.extend(chess)
result.append(tmp)
else:
for i in range(n):
chess[col] = i
if check(col): # col번째 퀸을 놓을 수 있다면 col+1번째 행의 퀸 위치 탐색
back_tracking(col+1)
def check(col): # 세로, 대각선 방향 퀸 유무 확인
for i in range(col):
if chess[i] == chess[col] or abs(col-i) == abs(chess[col]-chess[i]):
return False
return True
# 세로 방향 => chess[i] : 해당행의 퀸이 있는 위치(index)가 i임을 뜻함 chess[col] 과 같을 경우 False
# 대각선 방향 => 각 행의 퀸의 위치의 가로 방향 차이(abs(col-i))와 세로방향 차이(abs(col-i) == abs(chess[col]-chess[i]))가 같은 경우 대각선 상에 있게 되므로 False
def queen(n):
for col in range(n):
back_tracking(col)
print("▶ %d x %d chess %d-Queen case : %d"%(n,n,n,len(result)))
if __name__ == "__main__":
n = int(input(''))
chess = [0 for k in range(n)]
result = []
queen(n)
- 결과값
8
▶ 8 x 8 chess 8-Queen case : 92
queens(m, n)은 m개의 행과 n개의 열을 가진 직사각형 판에(즉, 세로 m 가로 n) 열에 하나씩 문제의 조건을 만족하며 퀸을 위치하는 모든 경우의 수를 출력합니다. 구하는 답은 len(queens(8,8)) = 92가 되겠네요.
def queens(m, n):
result = list()
if n == 1:
for i in range(1,m+1):
result.append([i])
return result
elif m < n:
return []
else:
for i in queens(m, n-1):
for j in range(1,m+1):
if not(j in i) and all([abs(i[k] - j) != (n-1-k) for k in range(n-1)]):
result.append(i+[j])
return result
import java.util.Arrays;
public class EightQueens {
static int successCount = 0;
static int failCount = 0;
public static void board(int row, int vertical, boolean[][] paramBoard, int count){
boolean[][] board = new boolean[8][8];
for(int i = 0; i< paramBoard.length; i++ ){
System.arraycopy(paramBoard[i], 0, board[i], 0, paramBoard.length);
}
if(!board[row][vertical]){ // 퀸을 둘수 없을 경우
if(vertical < 7){
board(row, vertical+1, board, count);
}else if(vertical == 7){
board(row+1, 0, board, count);
}
}else{ //퀸을 둘수 있을 경우
for(int i=0; i<row; i++){ // 퀸 있는 같은 위 row 모두 false 처리
board[i][vertical] = false;
}
for(int i=row+1; i<8; i++){ // 퀸 있는 같은 아래 row 모두 false 처리
board[i][vertical] = false;
}
for(int i=0; i<vertical; i++){ // 퀸 있는 같은 왼쪽 vertical 모두 false 처리
board[row][i] = false;
}
for(int i=vertical+1; i<8; i++){ // 퀸 있는 같은 오른쪽 vertical 모두 false 처리
board[row][i] = false;
}
for(int i = row-1, j = vertical-1; i >= 0 && j >= 0 ; i--, j--){ // 퀸 있는 좌상 방향 모두 false 처리
board[i][j] = false;
}
for(int i = row-1, j = vertical+1; i >= 0 && j < 8 ; i--, j++){ // 퀸 있는 우상 방향 모두 false 처리
board[i][j] = false;
}
for(int i = row+1, j = vertical+1; i < 8 && j < 8 ; i++, j++){ // 퀸 있는 우하 방향 모두 false 처리
board[i][j] = false;
}
for(int i = row+1, j = vertical-1; i < 8 && j >= 0 ; i++, j--){ // 퀸 있는 좌하 방향 모두 false 처리
board[i][j] = false;
}
count--;
if(row == 7 && count == 0){
successCount++;
return;
}else{
for(int i=0; i<8; i++){
if(board[row+1][i]){
board(row+1, i, board, count);
}
}
}
}
}
public static void main(String[] args) {
boolean[][] board = new boolean[8][8];
for(int i=0; i<8; i++){
Arrays.fill(board[i], 0, board[i].length, true);
}
int count = 8;
for(int i = 0; i < 8; i++){
board(0, i, board, count); // 이걸 vertical 0~8까지 해주면 될듯
}
System.out.println(successCount);
}
}
Swift입니다.
import Foundation
var total = 0
var mapSize = 8
func placeQ(_ prevBoard: [[Int]], _ y: Int, _ x: Int) {
var board = Array(prevBoard)
if board[y][x] == 0 {
for j in 0..<mapSize {
board[j][x] = -1
board[y][j] = -1
if y + j < mapSize && x + j < mapSize{
board[y + j][x + j] = -1
}
if y + j < mapSize && x - j >= 0{
board[y + j][x - j] = -1
}
}
if y == (mapSize - 1) {
total += 1
} else {
for i in 0..<mapSize {
placeQ(board, y + 1, i)
}
}
}
}
var boardArray = Array(repeating: (Array(repeating: 0, count: mapSize)), count: mapSize)
for i in 0..<mapSize {
placeQ(boardArray, 0, i)
}
print(total)
public class eX014 {
static byte[][] screen = new byte[8][8];
static int caseCount = 0;
public static void main(String[] args) {
// TODO Auto-generated method stub
//
long start = System.nanoTime();
count(0);
System.out.println("경우의수: "+ String.valueOf(caseCount));
long stop = System.nanoTime();
System.out.println(stop - start + " ns");
System.out.println((stop - start) / 1000000 + " ms");
System.out.println((stop - start) / 1000000 / 1000 + " sec");
}
static void count(int row) {
//해당 행의 모든 열을 탐색하여 퀸이 놓일 수 있는 위치의 개수를 구한다.
for(int i=0; i<screen[0].length; i++) {
//해당 위치에 퀸을 놓는다.(1대입)
screen[row][i] = 1;
//해당 위치에 퀸을 놓을 수 있으면 true, 아니면 false
if(canSet(row,i)) {
if(row == screen.length-1) {
caseCount += 1;
screen[row][i] = 0;
continue;
}
count(row+1);
}
//해당 위치에 놓아져있는 퀸을 뺀다!
screen[row][i] = 0;
}
}
static boolean canSet(int row, int column) {
//세로체크
for(int i=0; i< screen.length; i++) {
if(i == row)
continue;
if(screen[i][column] == 1)
return false;
}
//가로체크
for(int i=0; i<screen[0].length; i++) {
if(i == column)
continue;
if(screen[row][i] == 1)
return false;
}
int cRow,cColumn;
//우상단대각 체크(우상단방향)
for(cRow = row-1, cColumn=column+1; ( cRow >= 0 && cColumn < screen[0].length ); cRow-=1,cColumn+=1) {
if(screen[cRow][cColumn] == 1)
return false;
}
//우상단대각 체크(좌하단방향)
for(cRow = row+1, cColumn=column-1; ( cRow < screen.length && cColumn >= 0 ); cRow+=1,cColumn-=1) {
if(screen[cRow][cColumn] == 1)
return false;
}
//좌상단대각 체크(좌상단방향)
for(cRow = row-1, cColumn=column-1; ( cRow >= 0 && cColumn >= 0 ); cRow-=1,cColumn-=1) {
if(screen[cRow][cColumn] == 1)
return false;
}
//좌상단대각 체크(우하단방향)
for(cRow = row+1, cColumn=column+1; ( cRow < screen.length && cColumn < screen[0].length ); cRow+=1,cColumn+=1) {
if(screen[cRow][cColumn] == 1)
return false;
}
return true;
}
}
퀸의 위치를 1로 두고 비트연산으로 다음줄 퀸이 올 수 있는 위치를 추적하였습니다.
퀸의 위치는 대칭으로 2개씩 가지므로 4줄만 검사했습니다.
def queen(arr):
tmp = 0
for i in range(len(arr)):
tmp = tmp | arr[-i-1] | (arr[-i-1]>>(i+1)) | ( (arr[-i-1]<<(i+1)) & 0b11111111 )
return tmp ^ 0b11111111
def queen_pl(n):
if n <= 1: return n
i = 0
while n>1:
n,i = n>>1,i+1
return n<<i
arr = []
count = 0
for i in range(4):
arr.clear()
check = [0]+[0b100000000]*7
arr.append(0b10000000>>i)
while len(arr) != 0:
while len(arr) < 8:
if check[len(arr)] == 0:
check[len(arr)] = 0b100000000
break
if check[len(arr)] == 0b100000000: tmp = queen(arr)
else: tmp = check[len(arr)]
if tmp == 0: break
tmp2 = queen_pl(tmp)
check[len(arr)] = tmp - tmp2
arr.append(tmp2)
if len(arr) != 8: del arr[-1]
else:
count += 1
del arr[-1]
print('경우의 수: {}'.format(count<<1))
경우의 수: 92
class Program
{
static int count = 0;
public static bool isPromising(int[] q, int n)
{
for (int i = 0; i < n; i++)
{
if (q[i] == q[n]) return false; // 같은 열인지
if ((q[i] - q[n]) == (n - i)) return false; // '\' 방향
if ((q[n] - q[i]) == (n - i)) return false; // '/' 방향
}
return true;
}
public static void enumerate(int N)
{
int[] a = new int[N];
enumerate(a, 0);
}
public static void enumerate(int[] q, int n)
{
int N = q.Length;
// n이 끝까지 돌았다면 카운트를 증가한다.
if (n == N)
{
count++;
}
else
{
for (int i = 0; i < N; i++)
{
q[n] = i;
if (isPromising(q, n)) enumerate(q, n + 1); // 유망하다면 계속 탐색(재귀호출)
}
}
}
static void Main(string[] args)
{
int n = int.Parse(Console.ReadLine());
enumerate(n);
Console.WriteLine("solution count is " + count);
}
}
from copy import deepcopy
def can_place_queen(temp_board, row, i):
for j in range(8):
if(temp_board[row][j] == 'X'): return False
if(temp_board[j][i] == 'X'): return False
if((row+j<8) and (i+j<8) and (temp_board[row+j][i+j] == 'X')): return False
if((row+j<8) and (i-j>=0) and (temp_board[row+j][i-j] == 'X')): return False
if((row-j>=0) and (i+j<8) and (temp_board[row-j][i+j] == 'X')): return False
if((row-j>=0) and (i-j>=0) and (temp_board[row-j][i-j] == 'X')): return False
return True
def place_row(row, temp_board):
result = {}
for i in range(8):
if(can_place_queen(temp_board, row, i)):
temp_temp_board = deepcopy(temp_board)
temp_temp_board[row][i] = 'X'
if(row < 7):
place_row(row+1, temp_temp_board)
elif(row == 7):
global count
count = count + 1
for m in range(8):
for n in range(8):
print(temp_temp_board[m][n], end="")
print()
print(count)
count = 0
board = [[0]*8 for i in range(8)]
place_row(0, board)
#include <iostream>
using namespace std;
int isSafe(int q,int *r,int n);
int rcs(int *r,int n);
int main()
{
int r[8]={0,};
cout<<rcs(r,0);
return 0;
}
int rcs(int *r,int n){
int total=0;
if(n==8) return 1;
for(int i=0;i<8;i++){
if(n==0){
r[n]=i;
total += rcs(r,1);
}else
{
if(isSafe(i,r,n)){
r[n]=i;
total+=rcs(r,n+1);
}
}
}
return total;
}
int isSafe(int q, int *r,int n)
{
for (int i=0;i<n;i++) if(r[i]==q) return 0;
for(int i=0;i<n;i++)if(r[i]-(n-i)==q||r[i]+(n-i)==q) return 0;
return 1;
}
처음에 모든 경우의 수를 다 확인하며 프로그램을 돌리니 시간이 너무 오래 걸리더군요. 생각해보니 시간이 별로 걸리지 않도록 만드는게 목표인것 같아서 한번에 모든 조건을 다 처리하지 않고 단계를 나누어서 문제를 푸는 방법으로 접근했습니다. 1단계 : 가로와 세로가 겹치지 않는 좌표들을 구한다. (8! = 40320 개) 2단계 : 위의 조건을 만족하는 좌표들 중에서 대각선이 서로 겹치지 않는 경우를 구한다.(92개)
단계를 나누어서 접근하니 계산이 간단해져서 바로 나오네요.
import itertools
cand_list = []
ans_list = []
# 가로와 세로가 겹치지 않는 좌표들의 리스트를 생성
for cand in itertools.permutations([0,1,2,3,4,5,6,7]):
tmp_list = []
for num in range(8):
tmp_list.append((num,cand[num]))
cand_list.append(tmp_list)
# 대각선이 겹치는 애들을 제외하고 정답 리스트에 추가
for cand in cand_list:
sum_list = []
sub_list = []
for num in range(len(cand)):
sum_list.append(cand[num][0]+cand[num][1])
sub_list.append(cand[num][0]-cand[num][1])
if (len(set(sum_list)) ==8) and (len(set(sub_list))==8):
ans_list.append(cand)
print(len(ans_list))
def isSafe(qlist, i, j): #(i,j)의 퀸이 이전에 놓여진 퀸과 겹치는지 확인
for (qi, qj) in qlist:
if qi == i or qj == j or abs(qi-i)==abs(qj-j):
return False
return True
sol = []
def search(qlist, n, depth): #depth는 1부터 n까지
for i in range(1, n+1): #depth번째 줄에서 1부터 n까지 탐색
if isSafe(qlist, i, depth): #겹치지 않는다면
temp_list = qlist[:]
temp_list.append((i,depth)) #qlist에 추가하고
if n == depth:
sol.append(temp_list) #탐색하는 줄이 마지막줄이라면 솔루션에 추가
return
search(temp_list, n, depth+1) #다음 줄에서 탐색
return
search([],8,1)
print(len(sol))
import itertools
count = 0
for perm in itertools.permutations([n for n in range(0,8)]):
check = 1
for i in range(0,8):
if check == 0:
break
else:
for j in range(i+1,8):
if perm[j] in {perm[i]+j-i, perm[i]-j+i}:
check = 0
break
count += check
print(count)
행열이 겹치지 않게 8 팩토리얼 가짓수로 board 종류를 만든 후 대각선 체크를 해서 정답 92가 나왔습니다.
import numpy as np
import copy
board=np.zeros((8,8))
poss_ct=0
def diag_chk(board):
flag=True
n,n=board.shape
for i in range(int(n)):
diag_1=list(np.diag(board[n-1-i:n,:i+1]))
diag_2=list(np.diag(board[:i+1,n-1-i:n]))
b_tmp_1=board[:i+1,:i+1][:, ::-1]
diag_3=list(np.diag(b_tmp_1))
b_tmp_2=board[n-1-i:n,n-1-i:n][:, ::-1]
diag_4=list(np.diag(b_tmp_2))
if diag_1.count(1)>1 or diag_2.count(1)>1 or diag_3.count(1)>1 or diag_4.count(1)>1:
flag=False
break
return flag
poss_id_boards=[]
def poss_id_boards_arrange(n):
n=int(n)
poss_id_boards=[]
if n==1:
poss_id_boards=[[0]]
else:
for b in poss_id_boards_arrange(n-1):
for i in range(n):
poss_b=copy.deepcopy(b)
poss_b.insert(i,n-1)
poss_id_boards.append(poss_b)
return poss_id_boards
poss_id_boards=poss_id_boards_arrange(8)
# board arrange and diag check
for idb in poss_id_boards:
rb=copy.deepcopy(board)
for i in range(8):
row_id=idb[i]
rb[row_id,i]=1
if diag_chk(rb):
poss_ct+=1
print(poss_ct)
파이썬 3.7.2
def check_safe(q, Map):
for x in [x for x in range(8) if x != q[0]]:
if Map[q[1]][x] == 1:
return False
for y in [y for y in range(8) if y != q[1]]:
if Map[y][q[0]] == 1:
return False
for x,y in [(x, y-q[0]+q[1]) for x in range(8) if x < 8 and x != q[0] for y in range(8) if 0 <= y-q[0]+q[1] < 8 and y-q[0]+q[1] != q[1]]:
if x-y == q[0]-q[1]:
if Map[y][x] == 1:
return False
a = [x for x in range(8)]
a.reverse()
for x,y in [(x, y) for x in range(8) if x < 8 and x != q[0] for y in a if 0 <= y < 7 and y != q[1]]:
if x+y == q[0]+q[1]:
if Map[y][x] == 1:
return False
return True
Q = []
t = 0
nlist = [x for x in range(87654322) if set(str(x)) == {'1','2','3','4','5','6','7','8'}]
for n in nlist:
a,b,c,d,e,f,g,h = str(n)
a = int(a)-1
b = int(b)-1
c = int(c)-1
d = int(d)-1
e = int(e)-1
f = int(f)-1
g = int(g)-1
h = int(h)-1
Map = [[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]]
if {a,b,c,d,e,f,g,h} == {0,1,2,3,4,5,6,7}:
Map[0][a] = 1
Map[1][b] = 1
Map[2][c] = 1
Map[3][d] = 1
Map[4][e] = 1
Map[5][f] = 1
Map[6][g] = 1
Map[7][h] = 1
if check_safe([a,0],Map) and check_safe([b,1],Map) and check_safe([c,2],Map) and check_safe([d,3],Map) and check_safe([e,4],Map) and check_safe([f,5],Map) and check_safe([g,6],Map) and check_safe([h,7],Map):
s = ""
for y in range(len(Map)):
for x in range(len(Map)):
if Map[y][x] == 0:
s += "0"
elif Map[y][x] == 1:
s += "1"
s += "\n"
t += 1
print(a,b,c,d,e,f,g,h," ㅡ",t)
print(s+"\n\n")
print("total :",t)
좀 오래 걸리네요....
C#
static int N = 8, S = 1 << N, sum;
static void Queen(int q, int y, int l, int r)
{
if (++y > N)
sum++;
else
for (int b = 1; b < S; b *= 2)
if (((q & b) | (l & b << y) | (r & b << N - y)) == 0)
Queen(q | b, y, l | b << y, r | b << N - y);
}
static void Main()
{
Queen(0, 0, 0, 0);
Console.WriteLine(sum);
}
출력:
92
- 재귀 함수가 만들어 놓으면 심플한데 만들기가 참 어렵네요.
- 속도 최적화 하느라 비트 연산써서 안 심플한건 함정..
-
N=14 일때 1초를 목표로 했습니다.
-
N: 놓을 퀸 개수(=행=열)
- S: 퀸의 열비트 범위(N=4일때 S=10000, B=0001 ~ 1000)
- q: 각열에 놓인 퀸 비트 ..000011 첫열과 두째열에 퀸 놓임,
- y: 이전 퀸이 놓인 행,
- l, r: 퀸들에 의해 점유된 좌,우 대각선들의 비트
res = ['0', '1', '2', '3', '4', '5', '6', '7']
while len(res[0]) <= 7 :
n = res.pop(0)
imp_add = set(n) # 이미 출현했었던 열 제외
for imp_num in n :
rin = (int(imp_num)+n.index(imp_num))-(len(n)) # 대각성분 제외 - 왼쪽 아래(row+col = 좌표 합)
if 7 >= rin >= 0 : imp_add.add(str(rin))
rin = int(imp_num)+(len(n)-(n.index(imp_num))) # 대각성분 제외 - 오른쪽 아래
if 7 >= rin >= 0 : imp_add.add(str(rin))
for i in range(0, 8) : # 0~7 중 추가 불가능한 수(imp_add안에 있는 수)이외의 수를 더하여, 그 모든 경우의 수를 res의 가장 뒤에 추가
if not str(i) in imp_add :
res.append(n+str(i))
def get_dis(R) : #찾아낸 결과를 표현
count = 1
for ss in R :
print('\n', count)
count += 1
for ii in ss :
print(" ".join('-'*int(ii)+'Q'+'-'*(7-int(ii))))
get_dis(res)
젓 행부터 시작해서, 불가능한 경우(같은 열, 대각선)를 제외한 모든 경우의 수를 차례로 내려가며 탐색하도록 만들었습니다. 결과는 92개 나왔는데 그 중 1번째와 92번째만 아래에 작성하겠습니다.
결과
1
Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
92
- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
Javascript(ES6)...
`Q 를 놓을 수 있는 경우를 나타낼 때, 체스판에서 각 row 에는 Q 를 하나씩밖에 놓을 수 없으므로 각 row 별로 어느 column 에 Q 가 위치해있는 가를 기준으로 표시함 (예를들어 위 문제 예시의 경우는 '25317460')
각 row, column 이 겹치지 않도록 Q 를 놓을 수 있는 모든 경우의 수를 재귀함수를 사용하여 _find_permutations 제너레이트 함수 구현, 경우의 수들은 각 row, column 중복이 없으므로 대각선 검사만 따로 시행, 대각선 검사를 통과한 경우의 수만 별도로 queens 배열에 포함시킴
참고로 대각선 검사를 할 때는 맨 위 row 부터 왼쪽-아래, 오른쪽-아래 검사만 수행하면 됨 (왼쪽-위, 오른쪽-위 검사는 중복이기 때문에 불필요)
또한 경우의 수를 찾는 _find_permutations 함수는 별도의 라이브러리를 사용하지않고 직접 구현`;
class EightQueen {
constructor() {
this.queens = this._find_queens();
}
// 체스판에 Q 를 놓을 수 있는 모든 경우의 수를 반환하는 제너레이트 재귀함수
* _find_permutations(q) {
// 하나의 경우의 수가 완성되었으면 yield
if(q.length == 8) { yield q; }
// 하나의 경우의 수가 완성되지 않았으면 다음 row 에 들어갈 column 을 대입하고 재귀호출
for(let i = 0; i < 8; i++) {
// column 이 겹치면 continue
if(q.indexOf(i.toString()) > -1) { continue; }
// column 이 겹치지 않으면 q 뒤에 추가하여 재귀호출
yield * this._find_permutations(q + i.toString());
}
}
// Q 경우의 수를 찾아내는 함수
_find_queens() {
let queens = [];
for(let q of this._find_permutations('')) {
// 대각선 검사, nested 함수로 구현
function check_diagonal(q) {
for(let [idx, str_n] of [...q].entries()) {
for(let i = 1; i < 8 - idx; i++) {
if( Number(str_n) + i === Number(q[idx + i])
|| Number(str_n) - i === Number(q[idx + i])) {
return false;
}
}
}
return true;
}
if(check_diagonal(q)) { queens.push(q); }
}
return queens;
}
// 경우의 수들과 그 개수 출력 함수
print_number_of_queens() {
console.log(this.queens);
console.log(this.queens.length);
}
}
new EightQueen().print_number_of_queens(); // 92
Python 3...
class EightQueens:
def __init__(self):
self.queens = self.__find_queens()
# 제너레이트 재귀함수
def __find_permutations(self, q):
# 하나의 케이스 완성하면 yield
if len(q) == 8:
yield q
# 하나의 케이스가 완성되지 않았으면 다음 row 에 들어갈 column 을 대입하고 재귀호출
for i in range(8):
# column 이 겹치면 continue
if str(i) in q:
continue
# column 이 안겹치면 재귀호출
yield from self.__find_permutations(q + str(i))
# 모든 Q 케이스를 찾는 함수
def __find_queens(self):
# 대각선 검사 수행, nested 함수
def check_diagonal(q):
for idx, str_n in enumerate(q):
for i in range(1, 8 - idx):
if int(str_n) + i == int(q[i + idx]) or int(str_n) - i == int(q[i + idx]):
return False;
return True;
queens = []
for q in self.__find_permutations(''):
if check_diagonal(q):
queens.append(q)
return queens
def print_number_of_queens(self):
print(self.queens)
print(len(self.queens))
EightQueens().print_number_of_queens() # 92
- 인생은 짧으니 itertools 의 permutation 사용
from itertools import permutations
class EightQueens:
def __init__(self):
self.queens = self.__find_queens()
# 모든 Q 케이스를 찾는 함수
def __find_queens(self):
# 대각선 검사 수행, nested 함수
def check_diagonal(q):
for idx, str_n in enumerate(q):
for i in range(1, 8 - idx):
if int(str_n) + i == int(q[i + idx]) or int(str_n) - i == int(q[i + idx]):
return False;
return True;
queens = []
for q in permutations('01234567'):
_q = ''.join(q)
if check_diagonal(_q):
queens.append(_q)
return queens
def print_number_of_queens(self):
print(self.queens)
print(len(self.queens))
EightQueens().print_number_of_queens() # 92
CT="""--------
--------
--------
--------
--------
--------
--------
--------"""
lst=[list(ln) for ln in CT.split("\n")] #체스테이블을 리스트 형식으로 리스트에 담음
def Qpossible(y,x): #lst[y][x]에 Q를 놓아도 되는지 체크하는 함수
global lst
if lst[y].count("Q")>0: #행에 Q가 있으면 False
return False
for i in range(8): #열에 Q가 있으면 False
if lst[i][x]=="Q":
return False
for dy,dx in [(-1,-1),(-1,1),(1,1),(1,-1)]: #(y,x)에서 대각 4방향 이동하여 Q가 있으면 False
y1,x1=y,x #맨 처음 y,x를 y1,x1에 저장(y1,x1을 초기화하기 위함)
for i in range(8): #y,x가 0,0이라고 가정했을 때 최대 이동 가능한 횟수는 8번
y1,x1=y1+dy,x1+dx #y1,x1에 -1,-1을 8번 더하고 Q 유무 확인, (y1,x1 초기화), -1,1을 8번 더하고 확인(반복)
if 0<=x1<len(lst[0]) and 0<=y1<len(lst): #단, +-한 y1,x1이 리스트의 인덱스 사이여야 함
if lst[y1][x1]=="Q": #대각 이동 해봤더니 Q가 있으면 False
return False
return True #그 외엔 True
NOA,QN,row=0,0,0 #NOA 정답 개수, QN 퀸의 수, row 행
def solve(row):
global lst,NOA,QN
for x in range(8):
if row>7: #행이 7보다 크면 리턴하고 for 구문 반복
return
elif Qpossible(row,x) and lst[row][x]=="-": #lst[row][x]에 Q를 넣을 수 있으면
lst[row][x]="Q" #lst[row][x]에 Q를 넣고,
row=row+1 #행(row)을 다음 행(row+1)으로 옮긴다
QN+=1 #Q를 넣었으니 QN(퀸의 개수)에 1을 더한다
if QN==8: #만약 QN이 8이 되면(퀸의 개수가 8이 되면)
NOA+=1 #NOA(정답 개수)에 1을 더하고
print(NOA) #NOA를 출력하고
for ln in lst: #lst를 행별로 출력한다
for cmp in ln:
print("%3s"%cmp, end="")
print()
solve(row) #기존 row에 +1된 row를 넣고 재귀를 돌린다. 그런데 만약 다음 행에 Q를 넣을 수 없는 상태면,
row=row-1 #row와 QN에 -1을 하고, lst[row][x]="-"으로 하여 이전 상태로 복귀시킨다(백트랙킹)
QN-=1
lst[row][x]="-"
solve(0) #0번째 행(의 0번째 열~8번째 열까지)에 Q를 넣어보고 정답의 개수와 그 케이스를 출력
답: 92개
1
Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
2
Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -
....(중략)....
91
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - Q - - -
- - - - - - Q -
- - - Q - - - -
92
- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
""" board[row][col] 0 : empty 1 : queen 2 : forbidden """ from copy import deepcopy def prettyprint(board): print '\n'.join(str(r) for r in board),'\n' return
def markposs(board, row, col): board[row] = [2] * 8 for r in xrange(len(board)): board[r][col] = 2 if row > col: s = (row - col, 0) else: s = (0, col - row) while s[0] < len(board) and s[1] < len(board[0]): board[s[0]][s[1]] = 2 s = (s[0] + 1, s[1] + 1) if row + col > len(board) - 1: s = (row + col - (len(board) - 1), (len(board) - 1)) else: s = (0, row+ + col) while s[0] < len(board) and s[1] > -1: board[s[0]][s[1]] = 2 s = (s[0] + 1, s[1] - 1) board[row][col] = 1 return
solve = []
def branchposs(board, rest = 8): #prettyprint(board) global solve if rest == 0: solve.append(reduce(lambda x,y : ''.join(map(str,x))+''.join(map(str,y)), board).replace("2","0")) for r in xrange(len(board)): for c in xrange(len(board[0])): if(board[r][c] == 0): b = deepcopy(board) markposs(b, r, c) branchposs(b, rest - 1) elif(board[r][c] == 1): break return
b = [[0]*8 for a in xrange(8)] branchposs(b) print set(solve)
#include <iostream>
#include <cmath>
using namespace std;
int N;
int vy[111], vx[111];
int go(int y,int x) { //y is row, x is column
// back tracking Helps saving time
for(int i=0;i<y;i++) {
if(vy[i]==y) return 0; //horizontal test
if(vx[i]==x) return 0; //vertical test
if(abs(vx[i]-x)==abs(vy[i]-y)) return 0; //diagonal test
}
vx[y]=x, vy[y]=y; //saving Queens' move
if (y==N-1) return 1; // Successfully getting to the end of the row. count++
int r=0;
for(int i =0;i<N;i++) r+=go(y+1,i); //row++ with all of x
return r;
}
int main() {
cin >> N;
int r=0;
for(int i =0;i<N;i++) r+=go(0,i);
cout << r << endl;
return 0;
}
``````{.cpp}
#queen의 자리를 순서쌍으로 지정 q1 = (1,1), q2 = (2,3) 등
#8명의 queen은 같은 행 또는 열이 나올 수 없고, 서로 구분할 수 없으므로 q1의 x좌표를 1, q2의 x좌표를 2 ...로 설정
#대각선이 겹친다는 건 두 점 사이 기울기가 +-1이라는 것
#q의 y좌표를 배열할 때는 순열 8!을 전부 판별하는 방법도 있고, 한 개 랜덤으로 뽑고, 나머지를 set에 넣어서 랜덤 뽑기를 반복하는 방법도 있고, shuffle도 있다.
#먼저 shuffle함수를 이용해서 작성해보면 다음과 같다.
#queens(이하 qs)에 랜덤으로 셔플한 각 q의 좌표를 대입하고 판별해본다.
#판별 결과 이상 없고 이전 것과 겹침이 없으면 qss에 넣어서 답을 도출한다.
import random
qss=[]
n=0
ys_q = []
for n in range(400000):
y_q=list(range(1,9))
random.shuffle(y_q)
#print(y_q)
qs =[]
for i in range(8):
guardian= False
qs.append([i+1,y_q[i]])
if i==0:
continue
for j in range(i): #i=4, 0123
if (qs[i-j-1][1]-qs[i][1])/(qs[i-j-1][0]-qs[i][0]) ==1 or (qs[i-j-1][1]-qs[i][1])/(qs[i-j-1][0]-qs[i][0]) ==-1:
guardian=True
break
#print(qs)
if guardian:
break
if guardian:
continue
elif qs in qss:
continue
else:
qss.append(qs)
print(qss)
print(len(qss))
#보다시피 400000번 이상은 반복해야 안정적으로 92라는 답이 나옴을 알 수 있는데
#순열 경우의 수 자체가 8!=40320이므로 랜덤함수 말고 순열을 생성하는 itertools를 이용해서 겹침 없이 순열 생성하는 게 더 효율적임을 알 수 있다.
#아래는 순열 생성 함수를 활용해서 답을 구한 경우다.
import itertools
qss=[]
n=0
y = list(range(1,9))
ys_q = list(itertools.permutations(y))
for n in range(40320):
y_q = list(ys_q[n])
#print(y_q)
qs =[]
for i in range(8):
guardian= False
qs.append([i+1,y_q[i]])
if i==0:
continue
for j in range(i): #i=4, 0123
if (qs[i-j-1][1]-qs[i][1])/(qs[i-j-1][0]-qs[i][0]) ==1 or (qs[i-j-1][1]-qs[i][1])/(qs[i-j-1][0]-qs[i][0]) ==-1:
guardian=True
break
#print(qs)
if guardian:
break
if guardian:
continue
elif qs in qss:
continue
else:
qss.append(qs)
print(qss)
print(len(qss))
# Eight Queens Problem
# 8 x 8
# occupied : 각 줄에서 1의 위치 (0~7)
max_n = 8
occupied = []
total = 0
def print_result(result):
print('*'*30)
print(occupied, '\n')
for i in range(max_n):
for j in range(max_n):
if j == occupied[i]:
print('Q', end=' ')
else:
print('.', end=' ')
print()
# input()
def mapping(n): # n : 줄
global total
if len(occupied) == max_n:
total = total + 1
# print(occupied, total)
print_result(occupied)
return
for i in range(max_n):
if i not in occupied:
mapped = True
for j in range(len(occupied)):
if i == occupied[j]-n+j or i == occupied[j]+n-j:
mapped = False
break
if mapped:
occupied.append(i)
mapping(n+1)
occupied.pop()
for i in range(max_n):
occupied = [i]
mapping(1)
print('\n', 'Total Cases : ', total)
def check_unpossible(b, r, c):
dr = [-1,0,1]
for i in range(3):
R, C = r, c
while 0<=R<8 and 0<=C<8:
b[R][C] = c+1
R, C = R + dr[i], C + 1
return b
def cb_copy(cb, nb):
for r in range(8):
for c in range(8):
nb[r][c] = cb[r][c]
return nb
cnt = 0
def put_queens(cb, r, c):
global cnt
if c==7:
cnt += 1
# for k in range(8):
# print(cb[k][0:])
# print()
return
cb = check_unpossible(cb, r, c)
c += 1
for i in range(8):
if cb[i][c] == 0:
nb = [[0 for _ in range(8)] for _ in range(8)]
nb = cb_copy(cb, nb)
put_queens(nb, i, c)
for r in range(8):
put_queens([[0 for _ in range(8)] for _ in range(8)], r, 0)
print(cnt)
JAVA입니다.
package eight_queens_problem;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
ChessBoard cb = new ChessBoard();
final int size = cb.board.length;
System.out.println(countTree(cb, size, 0));
}
static int countTree(ChessBoard cb, int size, int row) {
//해당 열에서 가능한 모든 경우의 수를 세는 재귀함수
int count = 0;
for (int i = 0; i < size; i++) {
if(!cb.getCell(i, row)) {
if(row == 7) {
count++;
}
else {
ChessBoard newCb = cb.placeQueen(i, row);
count += countTree(newCb, size, row + 1);
//해당 위치에 퀸을 놓음을 전제로 이후 열의 경우의 수 계산
}
}
}
return count;
}
}
package eight_queens_problem;
public class ChessBoard {
boolean[][] board = new boolean[8][8]; //false: 위치 가능, true: 위치 불가
boolean getCell(int vert, int hori) { //getter
/*
* (0, 0) ... (7, 0)
* ...
* (0, 7) ... (7, 7)
*/
return board[hori][vert];
}
void setCell(int vert, int hori, boolean state) { //setter
board[hori][vert] = state;
}
ChessBoard placeQueen(int vert, int hori) {
//현재 배열에서 해당 위치에 새로 퀸을 놓았을 때의 배열을 반환
ChessBoard cb = new ChessBoard();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
cb.board[i][j] = board[i][j];
}
}
for (int i = 0; i < board.length; i++) {
cb.setCell(vert, i, true);
cb.setCell(i, hori, true);
}
try { //대각선 칸수 처리가 복잡할 것 같아 try catch 문으로 때웠습니다
for (int i = 0; i < cb.board.length; i++) {
cb.setCell(vert + i, hori - i, true); //오른쪽 위
}
} catch (ArrayIndexOutOfBoundsException e) {
// TODO: handle exception
}
try {
for (int i = 0; i < cb.board.length; i++) {
cb.setCell(vert - i, hori - i, true); //왼쪽 위
}
} catch (ArrayIndexOutOfBoundsException e) {
// TODO: handle exception
}
try {
for (int i = 0; i < cb.board.length; i++) {
cb.setCell(vert + i, hori + i, true); //오른쪽 아래
}
} catch (ArrayIndexOutOfBoundsException e) {
// TODO: handle exception
}
try {
for (int i = 0; i < cb.board.length; i++) {
cb.setCell(vert - i, hori + i, true); //왼쪽 아래
}
} catch (ArrayIndexOutOfBoundsException e) {
// TODO: handle exception
}
/*사실 위에서부터 아래로 내려가며 퀸을 배치할 것이므로 같은 행, 오른쪽/왼쪽 위는 없어도 됩니다만
프로그램의 범용성을 위해 남겨두었습니다.*/
return cb;
}
}