네모로직 풀이 알고리즘에 대한 소개

네모로직 풀이 알고리즘은 크게 유전알고리즘(Genetic algorithm)을 통한 풀이 방법과

 

깊이우선탐색(Depth first search) 방식이 있습니다.

 

 

문제 해결 시간에 소요되는 시간은 작은 사이즈이 네모로직일 수록 깊이우선탐색이 빠르고, 크기가 큰 문제일 경우 유전 알고리즘이 빠릅니다.

 

그러나, 유전 알고리즘의 경우 지역최적점에 잘못된 수렴의 가능성으로 문제 풀이가 안될 가능성이 있습니다.

 

 

시간 제한이 없다면 모든 네모로직 문제는 깊이우선탐색 방법에 의해 풀이가 가능합니다.

 

그러나, 퍼즐 열(row)의 갯수와 열에 존재하는 domain variable 의 갯수, 행(column)에 해당하는 값들의 팩토리얼 곱만큼의 계산량(complexity)가 발생합니다.

 

 

대만의 컴퓨터 공학자 분들이 네모로직을 제약 충족 문제(constraint satisfaction problem)의 관점에서 발전된 알고리즘을 제안한게 있는데, 그건 다음 시간에 소개를...