8퀸 문제

8퀸 문제란?

재귀 알고리즘에 대해서 설명할 때 자주 언급되는 알고리즘 문제이다.

8*8 체스판에 8개의 퀸을 배치하되 서로 공격하지 않게 배치해야된다.

 

퀸을 배치할 때 세가지 조건을 확인해야 됩니다.

 

1. 퀸을 배치하고자 하는 위치에서 같은 행에 퀸이 있는지 체크                        ㅡ    

2. 퀸을 배치하고자 하는 위치에서 오른쪽 대각선 방향으로 퀸이 있는지 체크    ( i행 + j열 )        /

3. 퀸을 배치하고자 하는 위치에서 왼쪽 대각선 방향으로 퀸이 있는지 체크       (j 열 + i행 -7 ) ＼

 

각 행에 퀸이 있는지 체크는 크기가 8인 배열 변수로 체크를 한다.

오른쪽 대각선 방향에 퀸이 있는지 체크는 크기가 15인 배열 변수로 체크를 한다.

왼쪽 대각선 방향에 퀸이 있는지 체크는 크기가 15인 배열 변수로 체크를 한다.

 

오른쪽 대각선 방향과 왼쪽 대각선 방향에 체크 배열 변수 크기를 왜 15로 두었는지 아래 그림을 통해서 확인하실 수 있습니다.

 

i행 j열을 더하면 모두 같은 값을 가지는 것을 확인 하실수 있습니다.

오른쪽 대각선은 i+j 값으로 인덱스를 구할 수 있습니다.

 

다음 아래 그림은 왼쪽 대각선 방향일때 체크 배열 인덱스 값입니다.

 

 

왼쪽 대각선은 i행 j열의 값을 j-i+7로 구한 값입니다.

위에 모두 같은 표시된 영역에 좌표들이 같은 값을 가지는 것을 확인 하실 수 있습니다.

 

위 세가지 체크 변수를 이용해서 그 자리에 배치를 할 수 있는지 확인 후 배치하면 됩니다.

 

 

 

자바 소스 코드

 

https://github.com/jokerKwu/java/blob/master/JavaStructure/src/EightQueen.java