N-Queen

문제: NQUEEN / 조합탐색

해결전략 1. 이중배열 이용

[출처] [AOJ 문제] N-Queen|작성자 DevMoon

1) 퀸을 놓기전에 상, 좌상, 우상 방향에 퀸이 있는지 검사한다.

 

2) 있으면 다른 칸에 놓는 것을 시도하고, 없으면 그 자리에 놓는다.

 

3) 다음 퀸을 놓기위해 재귀함수를 호출한다.

[출처] [AOJ 문제] N-Queen|작성자 DevMoon

코드: https://github.com/xgate/algospot/blob/master/SEARCH/NQUEEN1.cpp

해결전략 2. bit 연산 이용

 

1) queen의 위치를 bit로 표현한다.

 

2) 위의 행에 있는 queen과 겹치는지 bit 연산을 이용해서 판단한다.

 

3) 다음 퀸을 놓기위해 재귀함수를 호출한다.

[출처] [AOJ 문제] N-Queen|작성자 DevMoon

코드: https://github.com/xgate/algospot/blob/master/SEARCH/NQUEEN2.cpp