N개의 여왕 문제 : 퇴각 검색기법

N개의 여왕 문제를 통해 퇴각 검색기법의 개념을 알아보도록 하자.

몇개일까?
인간은 Trial n Error의 반복을 통해 성장한다.

나의 풀이과정은 아래와 같다.

첫번재 칸에 퀸을 배치하고 모든 경우의 수를 계산해보았는데
3개밖에 배치가 안됐다.

그래서 난 뭔가 잘못된것을 눈치채고 다시 처음으로 돌아가서 두번째 칸에 퀸을 배치했다.
그리고 그 결과 멋지게 4개의 퀸을 체스판 위에 배치할 수 있었다.

이것이 바로 '퇴각 검색'의 개념이다.
뭔가 잘못됐을 때, 전 단계로 돌아가서 다음 경우의 수를 실행해보는 것.

퇴각검색에 관한 자세한 알고리즘 코드는 아래 블로그에 잘 설명이 되어있다.
https://tomining.tistory.com/170


문득 미로찾기가 생각났다.
미로를 찾다가 길이 아니면 다시 이전 갈림길로 돌아가서 다른 길을 탐색하는 게 상책이다.
이 알고리즘으로 세상에서 제일 어려운 미로 문제를 풀 수 있겠다는 생각이 든다.