N-Queen 솔루션을 확인하기위한 체크섬

Question

백 트랙킹 알고리즘을 사용하여 N-Queen 문제를 해결했으며 C#에서 고유하고 구별되는 솔루션을 모두 생성 할 수 있습니다. 모든 행에서 유효한 위치를 찾아서 재귀 수준을 제한했지만 알고리즘은 N> 15에서 절망적으로 느려질 것입니다. 그 이유는 모든 새로운 솔루션에 대해 8 가지 대칭 대응을 생성하고이를 발견 된 솔루션. 이들 중 어느 것도 이미 포함되어 있지 않으면 새로운 솔루션을 고유 한 솔루션에 추가 할 수 있습니다.

각 솔루션에 체크섬을 연결하고 체크섬을 키로 사용하고 솔루션을 목록으로 사용하는 사전을 만들었습니다. 기사를 찾을 수 없으며 체크섬 개념에 새로운 것이 있습니다.

이 문제에 대한 도움을 주시면 감사하겠습니다.

Answer 1

N-queens의 해시 또는 체크섬 생성? 몇 가지 포인트 :

1. 퀸즈는 서로 동일합니다. 이것은 우리가 체크섬의 여왕 조건을 연속적으로 곱하여 구별하기를 원하지 않는다는 것을 의미합니다.

2. 위치는 무엇이 중요합니다.

   public int hashSolution (Queen[] queens) { 
       int h = 0; 
       for (Queen q : queens) { 
        int queenHash = (q.getX() * 23) + q.getY();  // 23 is a prime. 
        h += queenHash; 
       } 
       return h; 
   } 
   

   :

그래서 우리는 같은과 함께 시작할 수