[알고리즘]n-queens problem의 backtracking 알고리즘 구현

소개글

알고리즘 시간에 n-queens problem을 backtracking알고리즘으로 구현한 프로그램입니다. 사용자가 소스를 약간만 수정하여 모든 해를 구할수도 있습니다.
해가 너무 많아 처음과 마지막 해만 구하고 해의 갯수와 여러가지 정보만 출력하였습니다. 알고리즘 시간에 A를 맞은 프로그램입니다.
공부하는 데 많은 참고 하시기 바랍니다.

컴파일 실행환경

C파일을 피주얼 스튜디오로 실행시키시면 됩니다.

본문내용

교재의 제 200쪽에 있는 n-queens problem의 backtracking 알고리즘을 C 언어로 구현하시오. 아래에서 요구하는 출력 사항을 만족하기 위하여 알고리즘을 적절히 수정 보완하여야 한다.

입력 사항: 꼭 한 개의 n 값을 화면에서 입력 받는다.

출력 사항:
(1) backtracking algorithm에 의하여 첫 번째로 찾아지는 해(solution) [해는 배열 row의 내용을 출력함으로서 표현한다.]
(2) (a) 첫 번째 해(solution)가 얻어질 때까지 position_ok 함수가 호출된 횟수
(b) 그 중에서 position_ok 가 TRUE를 return 한 횟수
(c) position_ok 가 FALSE를 return 한 횟수
(3) 마지막으로 얻어지는 해
(4) 모든 해의 개수
(5) (a) 모든 해를 구하는 동안 position_ok 가 호출된 회수
(b) 그 중에서 position_ok 가 TRUE를 return 한 횟수
(c) position_ok 가 FALSE를 return 한 횟수

추가 사항: 프로그램이 다룰 수 있는 n 의 최대값 (실행 가능한 n의 최대값)을 소스 프로그램의 documentation에 포함한다.

압축파일 내 파일목록

algorithm1.JPG
algorithm1.c
Homework#1(1).hwp
algorithm1.exe

참고 자료

없음