| [ QuizWit ] in KIDS 글 쓴 이(By): dkkang (압셍트) 날 짜 (Date): 2003년 4월 25일 금요일 오전 11시 28분 13초 제 목(Title): Re: 퍼즐풀기.. 인공지능 기초에서 가끔 나오는 건 데, 일단 A* 알고리즘같은 게 아닌 규칙들로 알고리즘을 만들어야 한다면 숫자를 빈칸으로 움직이는 걸로 생각하기 보다는, 빈칸이 상하 좌우의 숫자와 교환되는 걸로, 즉 빈 칸을 위주로 생각하면 됩니다. 그렇게 생각하면 흐트러 놓는 거는 빈칸을 무작위로 움직이는 거니까 일단 간단하고요. 정렬된 상태에서 흐트러 놓는 move들을 스택에 넣다가 다시 빼면 당연히 원래대로 돌아오겠죠. :) 16 개 짜리나 9개 짜리의 경우 제가 나름대로 하는 푸는 규칙이 있긴 한 데, 최적의 알고리즘인지는 모르겠고, 인터넷에서 "8 puzzle, 9 puzzle" 뭐 그런 식으로 검색하면 많이 나올 거 같군요. 아하!인지 뭔지 하는 수학 교양서에서 본 적이 있는 데, 옛날에 아마 마틴 가드너가 15-puzzle을 가지고 장난을 친 적이 있었을 겁니다. 일부러 안풀리게 해놓고 풀면 현상금을 준다나 그랬었습니다. 음, 인터넷에서 찾으니까 간단히 나오는군요. http://www.mathematische-basteleien.de/15puzzle.htm |