다이내믹 프로그래밍을 사용하는 8 퀸 문제

Question

다이내믹 프로그래밍을 사용하여 8 개 여왕 문제를 구현하는 아이디어에 혼란 스럽습니다. 문제가 일련의 하부 문제로 분해되고 각 하부 문제에 대한 최적 해가 발견되면, 그 결과 해결책은 이러한 하부 문제에 대한 해결책을 통해 실현 될 것이다. 이 구조가없는 동적 프로그래밍으로 해결할 수 없습니다 "(Reference). 이를 고려해 볼 때 7x7 보드를위한 최적의 솔루션은 8x8의 경우 최적의 솔루션이 아닐 수도 있습니다. 따라서 문제의 결과는 하위 문제의 최적 해법을 통해 깨닫지 못할 수도 있습니다.

반면에 DP는 백 트랙킹 문제에 대한 최적화입니다. 그렇다면 8 개 여왕 문제는 백 트랙킹으로 해결할 수 있습니다 ... 데드 엔드 만 저장하면 역 추적 솔루션을 DP로 변환 할 수 있습니까? 그렇다면, 2,1은 부모 1,1에 대해 실현 가능하지 않을 수도 있지만 1,2에 대해 실행 가능할 수도있다.

업데이트

사람이 8 여왕 또는 n-퀸 문제는 동적 프로그래밍을 사용하여 해결 될 수 있는지 여부를한다는 생각을 가지고? 그렇다면 위의 관찰에 대한 귀하의 의견은 무엇입니까?

Answer 1

최적의 솔루션입니다.

네, 맞습니다. 그러나 이것은 문제를 분리하는 좋은 방법이 아닙니다. paper yi_H posted in his answer, 정리 2.4를 살펴보고 알고리즘 설명을보십시오. 이들은 솔루션을 폐선 집합 (즉, 퀸즈가 위협하는 선)에 따라 등가 클래스로 나눕니다. 정리 2.4는 특정 닫힌 선 세트의 하위 문제를 해결하면 을 보장하며 나머지는 별도로 해결 한 다음 결과를 결합 할 수 있습니다. 매우 영리합니다.

Answer 2

그냥 분명 구글의 히트 게시 :

A dynamic programming solution to the n-queens problem

참고 : 큰 N의에 대한 매우 느린이 여전히를, O (F (N) * 8^n)이, 당신은 더 나은 다른를 사용 알고리즘 : 수도없는 최적의도 (심지어 잘못된) 8 × 8을위한 7 × 7 보드

A Polynomial Time Algorithm for the N-Queens Problem