N-Queens 문제 해결… 어디까지 갈 수 있을까요?
https://stackoverflow.com/questions/1863531
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
N-Queens 문제:
이 문제는 N x N 크기의 체스판이 주어졌을 때 어느 누구도 서로 위협하지 않고 N개의 여왕을 체스판 위에 놓을 수 있는 다양한 순열을 찾는 것입니다.
내 질문은 다음과 같습니다
프로그램이 합리적인 시간 내에 답을 계산할 수 있는 N의 최대값은 얼마입니까?아니면 지금까지 우리가 본 가장 큰 N은 무엇입니까?
CLPFD(Prolog)의 내 프로그램은 다음과 같습니다.
generate([],_).
generate([H|T],N) :-
H in 1..N ,
generate(T,N).
lenlist(L,N) :-
lenlist(L,0,N).
lenlist([],N,N).
lenlist([_|T],P,N) :-
P1 is P+1,
lenlist(T,P1,N).
queens(N,L) :-
generate(L,N),lenlist(L,N),
safe(L),
!,
labeling([ffc],L).
notattack(X,Xs) :-
notattack(X,Xs,1).
notattack(X,[],N).
notattack(X,[Y|Ys],N) :-
X #\= Y,
X #\= Y - N,
X #\= Y + N,
N1 is N + 1,
notattack(X,Ys,N1).
safe([]).
safe([F|T]) :-
notattack(F,T),
safe(T).
이 프로그램은 잘 작동하지만 N에 따라 소요 시간이 계속 늘어납니다.다음은 샘플 실행입니다.
?- queens(4,L).
L = [2, 4, 1, 3] ;
L = [3, 1, 4, 2] ;
No
즉, 4개의 퀸을 Column1의 2행, Column 2의 4행, 3의 1행, 4의 3행에 배치한다는 의미입니다.(4 x 4 체스판에서)
이제 이 프로그램이 어떻게 수행되는지 살펴보겠습니다(첫 번째 순열을 계산하는 데 걸리는 시간).
N=4,5.....10의 경우 1초 내에 계산됩니다.
N=11-30의 경우 -1-3초 소요
N=40..50의 경우 여전히 1분 이내에 계산됩니다.
N=60에서는 글로벌 스택을 벗어납니다(검색 공간이 엄청남).
이것은 과거의 숙제 문제였습니다.(원래 문제는 N-Queens를 코딩하는 것뿐이었습니다)
나는 또한 다른 언어의 대체 구현(내 구현보다 성능이 더 좋음)을 보거나 내 알고리즘/프로그램에 개선의 여지가 있는지 알아보고 싶습니다.
해결책
pycon의 raymond hettinger가 제시한 짧은 솔루션: Python의 쉬운 AI
#!/usr/bin/env python
from itertools import permutations
n = 12
cols = range(n)
for vec in permutations(cols):
if (n == len(set(vec[i] + i for i in cols))
== len(set(vec[i] - i for i in cols))):
print vec
그러나 모든 순열을 계산하는 것은 확장 가능하지 않습니다(O(n!))
다른 팁
이 논의는 세 가지 다른 계산 문제를 통합합니다.(1) N 퀸즈 문제에 대한 해결책 찾기, (2) 일부 고정 N에 대한 모든 솔루션 나열, (3) 일부 고정 N에 대한 모든 솔루션 계산.첫 번째 문제는 N=8과 같은 보드 크기의 경우 처음에는 까다로워 보입니다.그러나 Wikipedia에서 알 수 있듯이 N이 클 때 몇 가지 주요 방법은 쉽습니다.큰 보드 위의 퀸들은 그다지 많은 의사소통을 하지 않습니다.메모리 제약을 제외하면 휴리스틱 복구 알고리즘은 N이 증가함에 따라 작업이 더 쉽고 쉬워집니다.
모든 솔루션을 나열하는 것은 다른 문제입니다.이는 출력을 읽는 데 아무런 의미가 없을 만큼 충분히 큰 크기까지 좋은 동적 프로그래밍 코드를 사용하여 수행할 수 있습니다.
질문의 가장 흥미로운 버전은 솔루션 수를 세는 것입니다.최신 기술은 다음과 같은 멋진 참고 자료에 요약되어 있습니다. 정수 시퀀스 백과사전.N=26까지 계산되었습니다.나는 그것도 동적 프로그래밍을 사용한다고 추측하지만 모든 솔루션을 나열하는 경우와 달리 알고리즘 문제는 훨씬 더 깊고 더 발전할 가능성이 열려 있습니다.
로렌 페치텔(Loren Pechtel)은 이렇게 말했습니다."이제 진짜 미친 짓을 해보겠습니다.29는 9초가 걸렸습니다.30은 거의 6분 걸렸어요!"
다양한 보드 크기에 대한 역추적 복잡성의 예측 가능성이 매우 부족하다는 점이 이 퍼즐에서 제가 가장 관심을 보인 부분이었습니다.수년 동안 나는 다음을 찾는 데 필요한 알고리즘 단계의 '개수' 목록을 작성해 왔습니다. 첫 번째 솔루션 각 보드 크기에 대해 - 재귀 C++ 함수에서 간단하고 잘 알려진 깊이 우선 알고리즘을 사용합니다.
다음은 최대 N=49까지의 보드에 대한 모든 '개수' 목록입니다. 마이너스 N=46 및 N=48은 아직 작업 중입니다.:
http://queens.cspea.co.uk/csp-q-allplaced.html
(OEIS(Encyclopedia of Integer Sequences)에 다음과 같이 나열되어 있습니다. A140450)
해당 페이지에는 일치하는 첫 번째 솔루션 목록에 대한 링크가 포함되어 있습니다.
(내 목록은 첫 번째 솔루션 OEIS 시퀀스 번호입니다. A141843)
나는 주로 각 솔루션에 필요한 처리 시간을 기록하지 않고 각 보드의 알고리즘 우선 솔루션을 발견하기 전에 실패한 퀸 배치 횟수를 기록합니다.물론 퀸 배치 비율은 CPU 성능에 따라 다르지만 특정 CPU 및 특정 보드 크기에 대한 빠른 테스트 실행을 고려하면 이러한 '발견된' 솔루션 중 하나를 해결하는 데 걸린 시간을 쉽게 계산할 수 있습니다.
예를 들어 Intel Pentium D 3.4GHz CPU에서 단일 CPU 스레드를 사용하는 경우 -
- N=35의 경우 내 프로그램은 초당 2,400만 개의 퀸을 '배치'했으며 첫 번째 솔루션을 찾는 데 단 6분밖에 걸리지 않았습니다.
- N=47의 경우 내 프로그램은 초당 2,050만 개의 여왕을 '배치'했고 199일이 걸렸습니다.
내 현재 2.8GHz i7-860은 N=48에 대한 첫 번째 솔루션을 찾으려고 초당 약 2,860만 개의 퀸을 처리하고 있습니다.UN이 성공적으로 1,369,331,731,000,000(그리고 빠르게 증가하는) 여왕을 배치하는 데는 지금까지 550일 이상이 걸렸습니다(이론적으로 중단이 없었다면).
내 웹 사이트에는 (아직) C++ 코드가 표시되지 않지만 해당 웹 페이지에 N=5 보드를 해결하는 데 필요한 15가지 알고리즘 단계 각각에 대한 간단한 그림에 대한 링크를 제공합니다.
정말 맛있는 퍼즐이군요!
어떤 Prolog 시스템을 사용하고 있나요?예를 들어, 최신 버전의 SWI-Prolog를 사용하면 다음에 대한 솔루션을 쉽게 찾을 수 있습니다. N=80 그리고 N=100 원본 코드를 사용하여 몇 초 안에.다른 많은 Prolog 시스템은 그보다 훨씬 빠릅니다.
N-queens 문제는 SWI-Prolog의 온라인 예제 중 하나에도 등장합니다. CLP(FD) 퀸즈 SWISH에서.
예 퀸 100명:
?- time((n_queens(100, Qs), labeling([ff], Qs))). Qs = [1, 3, 5, 57, 59 | ...] . 2,984,158 inferences, 0.299 CPU 0.299초 안에 (100% CPU, 9964202 Lips)
SWISH는 솔루션의 좋은 이미지도 보여줍니다.
다음은 전체 솔루션 프로세스를 보여주는 애니메이션 GIF입니다. N=40 SWI-프롤로그가 있는 퀸:
컴퓨터가 해결한 가장 큰 N이 무엇인지에 관해 문헌에는 충돌 복구 알고리즘을 사용하여 약 3*10^6의 N에 대한 솔루션을 찾은 참고 자료가 있습니다(예:지역 검색).예를 들어 [소식과 구].
역추적을 통한 정확한 해결과 관련하여 역추적을 거의 하지 않고 올바른 구성을 달성하는 몇 가지 영리한 분기 휴리스틱이 있습니다.이러한 휴리스틱을 사용하여 다음을 찾을 수도 있습니다. 퍼스트케이 문제에 대한 해결책:초기의 올바른 구성을 찾은 후 검색은 역추적하여 근처의 다른 유효한 구성을 찾습니다.
프로그램이 합리적인 시간 내에 답을 계산할 수 있는 N의 최대값은 얼마입니까?아니면 지금까지 우리가 본 가장 큰 N은 무엇입니까?
제한은 없습니다.즉, 솔루션의 유효성을 확인하는 것은 하나의 솔루션과 7개의 대칭 솔루션을 구성하는 것보다 비용이 더 많이 듭니다.
위키피디아를 참조하세요:"모든 n ≥ 4에 대해 n × n 보드에 n 퀸을 배치하기 위한 명시적인 솔루션이 존재하며 조합 검색이 전혀 필요하지 않습니다.".
주어진 보드 크기에 대한 솔루션 수를 계산하는 오래된 Delphi 프로그램을 끌어서 한 번 히트한 후에 멈추도록 빠르게 수정했는데 데이터에서 이상한 패턴이 보입니다.
해결하는 데 1초 이상 걸린 첫 번째 보드는 n = 20이었습니다.하지만 21개는 62밀리초 만에 풀렸습니다.(메모:이는 고정밀 시스템이 아닌 Now를 기반으로 합니다.) 22는 10초가 걸렸으며 28까지 반복되지 않았습니다.
최적화 규칙이 매우 달랐던 시절부터 이것은 원래 고도로 최적화된 루틴이었기 때문에 최적화가 얼마나 좋은지 모르겠습니다.하지만 나는 대부분의 구현과는 매우 다른 작업을 수행했습니다. 보드가 없다는 것입니다.오히려 어떤 열과 대각선이 공격을 받는지 추적하고 행당 하나의 퀸을 추가하고 있습니다.이는 테스트된 셀당 3개의 배열 조회를 의미하며 곱셈은 전혀 수행되지 않습니다.(내가 말했듯이, 규칙은 매우 달랐습니다.)
이제 진짜 광기의 경우 :29는 9초가 걸렸습니다.30개는 거의 6분 정도 걸렸어요!
Bakore가 설명한 것과 같이 실제로 제한된 랜덤 워크(생성 및 테스트)는 신속하게 생성될 수 있기 때문에 소수의 솔루션이 필요한 경우에 사용할 수 있는 방법입니다.저는 20세 또는 21세 때 한 수업에서 이 작업을 수행했으며 1987년 3월 Journal of Pascal, Ada & Modula-2, "The Queens Problem Revisited"에 해결책을 발표했습니다.오늘 그 기사에서 코드를 제거했고(이것은 매우 비효율적인 코드입니다) 몇 가지 문제를 해결한 후 N=26이 생성되었습니다.N=60 솔루션.
1개의 솔루션만 원한다면 선형 시간 O(N)에서 탐욕스럽게 찾을 수 있습니다.내 파이썬 코드:
import numpy as np
n = int(raw_input("Enter n: "))
rs = np.zeros(n,dtype=np.int64)
board=np.zeros((n,n),dtype=np.int64)
k=0
if n%6==2 :
for i in range(2,n+1,2) :
#print i,
rs[k]=i-1
k+=1
rs[k]=3-1
k+=1
rs[k]=1-1
k+=1
for i in range(7,n+1,2) :
rs[k]=i-1
k+=1
rs[k]=5-1
elif n%6==3 :
rs[k]=4-1
k+=1
for i in range(6,n+1,2) :
rs[k]=i-1
k+=1
rs[k]=2-1
k+=1
for i in range(5,n+1,2) :
rs[k]=i-1
k+=1
rs[k]=1-1
k+=1
rs[k]=3-1
else :
for i in range(2,n+1,2) :
rs[k]=i-1
k+=1
for i in range(1,n+1,2) :
rs[k]=i-1
k+=1
for i in range(n) :
board[rs[i]][i]=1
print "\n"
for i in range(n) :
for j in range(n) :
print board[i][j],
print
그러나 여기서 인쇄하는 데는 O(N^2) 시간이 걸리며 Python은 느린 언어이므로 누구나 C/C++ 또는 Java와 같은 다른 언어로 구현해 볼 수 있습니다.그러나 Python을 사용하더라도 1~2초 내에 n=1000에 대한 첫 번째 솔루션을 얻을 수 있습니다.
