김태석, 김종수 Tai Suk Kim, Jong Soo Kim 1. 서론 완전문제임이증명된스도쿠게임은구글의신경망네트워크를가지는알파고와다르게현재의데스크탑컴퓨터의자원을이용해서주어진문제를빠른시간내에해결할수있는알고리즘구현을위한좋은소재로사용될수있다 수학자오일러의라틴방진을응용한스도쿠는약 개의경우의수를가지는복잡한문제이면서 바둑과같이상대방이필요한턴방식의게임이아니므로해당기능구현이필요없다는장점이있다 또다른 완전문제인바둑의경우에는오픈된 소스인 그리고 와같은인공지능이있으며 이러한인공지능들의추정기력은대략 급이상인것으로알려져있다 분산환경에서 개의 와 개의 로구성된구글의딥마인드알파고는머신러닝과몬테카를로트리순회기술을조합한알고리즘을사용하여 개의경우의수를가지는바둑에서인간의지능을뛰어넘는인공지능을만들어냈다 알파고에서는트리전개를최소화하기위한기법으로심층신경망기술을적용하여주요핵심기술인정책네트워크와가치네트워크구현하였는데 초기신경망을구축하기위한방법으로 천만수정도의바둑프로기사들
의기보를데이터베이스로사용하였으며 어느정도안정화되어서는 개의알파고가서로대국하여만들어진기보를사용하여다시머신러닝을강화하도록학습시켰다 문제를해결하기위한인공지능은반드시최적의해법을구해야할필요는없기때문에짧은시간에해를구할수있는알고리즘의개발이중요하다고할수있다 본논문에서는 완전문제인스도쿠의풀이기위해트리순회와잘알려져있는풀이방법을구현한알고리즘과욕심쟁이기법 을이용하여트리를순회를최소화하기위한예를보인다 2. 관련연구 2.1 P-NP 문제 년스티븐쿡의정리증명절차의복잡성 이라는문제에서처음제안된 문제의 는비결정론적튜링기계를사용하여다항시간내에답을구할수있는문제집합으로정의된다 완전문제가 차혹은선형시간안에풀릴수있는지아닌지를묻는문제가클레이수학연구소에서발표한 개의 밀레니엄문제 중하나이며컴퓨터과학에서중요한위치를차지하고있다 완전 은 집합에속하는결정문제중에서가장어려운문제의부분집합으로 모든 문제를다항시간내에 완전문제로환산할수있다 완전문제의예는해밀턴경로문제 외판원문제 그래프색칠문제 시간표짜기문제들이있으며 스도쿠와바둑게임도이에속 한다 컴퓨터과학자들은 완전문제를실용적인관점에서해결하기위해서다항방정식을찾는대신근사알고리즘 이나휴리스틱알고리즘을사용하거나욕심쟁이알고리즘을사용하여훨씬적은양의계산으로빠르게정답을찾는방법을사용한다 2.2 기존연구스도쿠를풀이하기위한프로그램의대표적인예는호도쿠 와재귀적호출을사용하는방법이있다 먼저스도쿠문제의풀이방법을도와주기위해제작된호도쿠는다양한풀이방법을구현하고있다 호도쿠에서사용되는휴리스틱알고리즘이구현된클래스를 에서볼수있다 스도쿠풀이를위해사용될수있는알고리즘의구현하기위하여 패턴을사용하였고 를확장한 그리고 와같은다양한메서드들이구현되었음을볼수있다 총 개의클래스를사용하여 개의풀이방법을구현하고있다 호도쿠외에도스도쿠풀이기를위한방법으로는재귀적방법이있다 이를응용하는풀이예는 에소개되어있다 이연구는재귀적알고리즘을적용하기전에탐색횟수를줄일수있도록행 열그리고그룹에서탐색대상이되는숫자가가장작은세트부터숫자를채워나가는욕심쟁이기법을구현하고있다 는구현되지않았으며 컴퓨터의계산능력을충분히활용하여시간복잡도를최적화시켰다 재귀적호출을사용하는방식을의사코드로나타내면 과같다 Fig. 1. class diagram for solving method.
Table 1. pseudo code for the recursive call method 3. 스도쿠풀이를위한알고리즘설계 3.1 완전이진트리탐색의응용 수학자들에의해 문제풀이에대한다항방정식을 정의할수없는 완전문제임이증명된스도쿠 문제를컴퓨터로풀이하는데있어서좋은방법중에 하나는 의초고속연산능력을최대한활용할수 있는재귀적인호출을이용하는것이지만 구현되는 코드에불필요한코드가추가되면재귀호출횟수만 큼소요시간이증가한다는단점이있다 스도쿠와같 은 완전문제를풀이하기위한또다른방법은 각각에해당하는경우를계산하기위한트리전개를 하는것이며이경우트리전개를최소화하는방법에 대한연구가필요하다 트리는전개하는데있어서네트워크로연결된다 수의컴퓨터자원을활용할수있는경우에는완전이 진트리탐색을활용할수있다 이미출제된스도쿠 문제는 개이상의부분문제로분할하여각부분문 제의해결안을바탕으로최종해결안을도출할수도 있다 는제안된방법이완전이진트리를전개 하는방식을보여준다 수행횟수 번째인 은휴리스틱알고리즘이 적용되어계산된단계이며 주어진문제에서더이상 적용할수있는휴리스틱알고리즘이없는경우 완 Fig. 2. The complete binary tree expansion of proposed algorithm. 전이진트리를전개한다 주어진스도쿠문제를부분 문제로분할하면통상적으로원래의문제와는입력 크기만다를뿐동일한문제가된다 일반적으로완 전이진트리의시간복잡도계산은다음과같이이루 어진다 처음입력된개수를 이라고하면 첫번째이진트리전개에서좌우로반씩나누어짐 으로 이되며 두번째시행후에는또다시반으로 나누어짐으로 이된다 세번째수행에서도반 으로나누어짐으로 이되는데 번수행 후의탐색할자료의수는수식 과같이일반화된다 탐색이끝나는 번째에남는자료의숫자를생각 해볼때 최악의탐색결과는수식 와같이자료가 개남을때까지탐색하는것이다 양변에 를곱하면 이되며 다시양변에 를밑으로하는로그를취하면 완전이진트리의탐색시간복잡도 은수식 과 같이계산된다 log 시간복잡도 표기법으로는수식 가된다
log 완전이진트리에서는각각의잎노드를네트워크 망에연결된컴퓨터로분산하여계산을수행할수 있도록구성할수도있는데 앞의식들에서깊이가 수행횟수 를나타냄으로 네트워크로분산된개별 완전이진트리의수행횟수는 이되며따라서시 간복잡도 log log 은수식 과같이줄어든다 3.2 풀이방법들과욕심쟁이기법의적용 제안된방법은기존에알려진휴리스틱알고리즘 과욕심쟁이기법을사용하여트리전개를최소화하 는기법을사용한다 에서제안된방법을사용 하여스도쿠문제를풀이하기위한전체순서도를 볼수있다 초기에문제가출제되면전처리과정을거친후 과 로알려진알고리즘으 로부분정답을찾아내거나전개가불필요한가지를 친다 스도쿠방진전체가임의로선택된숫자로채 워지면정답검증기를사용하여정답을검증한후 정답이면결과를출력하여종료하고 정답이아닐경 우에는다시문제를초기화한후 트리를생성하고 최소깊이전개를위해욕심쟁이기법을사용하여 전처리된셀들중에서시간복잡도를최소화할수있는 을구한후 해당 에포함된숫자들을사용하여자식노드로전개한다 정답검증기의주요역할은현재정답이검증되고있는잎노드가속한경로가앞으로계속해서깊이전개를해야하는지가치를평가하는것이며 가치평가의결과는현재잎이정답인경우스도쿠방진을리턴하고 추가적인깊이전개가더필요한경우욕심쟁이기법으로찾은 을이용하여가장깊은잎노드를대상으로자식노드를추가해나간다 해당잎노드가오답인경우더이상깊이전개가되지않도록가지를친다 다음으로전개된잎노드를사용하여새로운스도쿠문제를생성한후 전처리과정과정답검증기를거치는호출을정답을찾을때까지계속한다 3.3 전처리기구현스도쿠를풀이하기위한첫번째단계는각각의정답이주어진각셀을제외하고정답이아닌셀에대하여정답이될수있는숫자들의집합을찾아내는것이다 제안된방법에서 클래스는스도쿠문제를풀이하기위한기본정보를가지고있는데 의좌표와입력가능한숫자의집합이다 스도쿠문제의전처리를위한사용자인터페이스는 에나타냈다 주어진문제의전처리결과 그리고 의숫자가올수있음을볼수있다 3.4 휴리스틱알고리즘을이용한부분정답찾기 제안된방법에서는스도쿠풀이를위해적용될수 Fig. 3. Flow diagram of proposed method. Fig. 4. preprocessing execution (left: before, right: after).
문제풀이시간을단축하기위해서가장적은숫자들의원소를가지는셀선택 로선택된셀이여러개가있을경우 해당셀이가진원소가정답으로설정되었을때 정답이아닌셀들이포함하고있는숫자를가장많이제거할수있는셀을우선적으로선택 Fig. 5. Hidden Single before (left) and after (right). 있는알고리즘중에서사용빈도수가비교적높은 그리고 만을구현하였다 이중 과 은전처리과정에서사용되며 정답을찾기위해 과 가사용되었다 에서 이수행된결과를볼수있다 먼저 를살펴보면 에포함된원소는 인데 여기에포함된원소중에서숫자 가 이다 에대해서도숫자 이 임을볼수있다 좌측의실행전그림을살펴보면정답이아닌전체셀에대하여 을찾아내기위한구현을위해행과열그리고그룹에대하여모두구현해야될것처럼보이지만실제로는행이나열 또는그룹중에서한가지경우에서만 을탐색하면된다는것을볼수있다 해당행과열그리고그룹에서각각숫자 와 이제거된것을볼수있다 알고리즘을수행한결과가 를리턴하면다시전처리된다 3.5 최소깊이전개를위한욕심쟁이기법 과 를사용하는전처리과정을거친후에도스도쿠방진전체가숫자로채워지지않으면 다음단계는욕심쟁이기법을사용하여최소깊이전개에가장효과적인 을검색한후 트리의전체잎에해당 의숫자들을자식노드로추가한다 이렇게생성된잎노드를사용하여스도쿠방진을다시생성하며 만약스도쿠방진이숫자로다채워지면정답검증기를사용하여정답을검증하는과정을반복한다 트리전개에서최소깊이를생성하기위한욕심쟁이기법은다음과같다 욕심쟁이기법이적용되는과정은다음과같다 앞의문제에대해서먼저전처리를거친실행결과에 서 을적용하면 와 의두개의셀이가장적은원소의개수를가지 고있다는것을볼수있다 후보의개수가 개이상 일경우 를적용한다 두후보에서각각의 값이정답으로설정되었을때 정답으로설정되지않 은행열또는그룹에서가장많은값을제거하는 숫자선택해서새로생성되는 의자식노드로 추가한다 이후 다시전처리를수행하며 스도쿠방 진이전부채워졌을경우정답검증기를사용하여가 치평가를수행하여불필요한가지를친다 제안된알 고리즘의의사코드를 에서볼수있다 셀에포함된원소의개수가최소이면서해당 을정답으로설정했을때다른 들에있 Table 2. pseudo code for the proposed method
는원소들을가장많이제거할수있는 들의정보가있는 이가진원소들을정답으로설정하여만들어지는각각의 로정답설정 스도쿠방진 제는다음과같다 에구현된스도쿠풀이기가문제풀이를위 해완전이진트리를전개하는방식을나타냈다 호도쿠 재귀적호출그리고제안된방법으로 을풀이한결과를 에정리하였다 Fig. 6. The result of the complete binary tree expansion for solving the sudoku. 해당문제에서는깊이 에서정답을찾았으며 번의가지치기가있었다 4. 성능평가 각각의프로그램에대한테스트를위한환경은 과같다 호도쿠나재귀적호출을사용하는방법의서로다 른설계목적을가지고있음으로각각의구현방법에 대한성능평가를위해임의로출제된난이도가높은 스도쿠문제를대상으로처리시간과주요항목을측 정하였고 이를위해호도쿠와재귀적호출방법은기 존의프로그램에해당코드를추가하였다 주어진문 Table 3. Test environment 총 개의알려진풀이방법으로구성된호도쿠는주어진문제에서적용할수있는알고리즘의탐색시간이많이소요되었다 이것은같은조건에서사용될수있는여러개의알고리즘을모두탐색하기때문으로예상된다 호도쿠에서가장많이사용되는풀이방법은 이였으며 다음으로 등이였다 를구현하지않고오직스도쿠문제풀이를위한코드로만구현된재귀적호출방법이가장빠른시간을보였지만 호도쿠에서전체알고리즘의수나제안된방법에서의깊이와잎의곱을호출횟수로가정한다면다른 개의방법보다메서드호출횟수가많은것을알수있다 재귀적방법에서는불필요한호출을최적화하기힘들다는단점도있다 트리를전개하면서 알고리즘과욕심쟁이기법을사용하는제안된방법은깊이전개를최소화하고필요없는가지를쳐냄으로써계산에필요한잎노드를많이줄인것을볼수있다 정형스도쿠에서 개의숫자가공개된문제의경우에서볼때 단순하게트리만을전개하는경우에는최악의경우 단계의깊이전개가필요하고 그에따른잎도엄청나게늘어날수있지만 제안된방법에서는주어진문제들에대하여전개된깊이가 단계로줄어들었으며 계산에필요한잎노드가 개로
Table 4. Measuring execution time (unit: milliseconds) 줄어든볼수있었다 구현된 를코드를없애고 가장많이적용되는알고리즘을추가적으로구현하고 욕심쟁이기법을최적화하면계산시간이더욱단축될수있을것으로보인다 5. 결론본논문에서바둑과같이 완전문제중에하나인스도쿠를풀이할수있는풀이기설계방법을제안하였다 아주복잡한난이도를가지는 문제들은정확한수학적공식이나일반적인해법을찾을수없는경우가많다 특히복잡도가높은많은문제를다루어야할경우 한정된자원을사용하여최적의해를빠르게도출할수있는방법이필요하며 이러한경우주어진시간내에서어느정도최적한된풀이방법에빠르게도달하기위해서는컴퓨터의빠른계산능력을활용하는것이좋은방법이다 본논문에서도많은계산량을가지는게임인스도쿠문제의풀이기를설계하는데있어서트리전개바탕으로욕심쟁이기법을사용하여완전이진트리에서전개될깊이를최소화는방법과자주사용되는알고리즘을사용하여불필요한가지를쳐냄으로써계산되어야할잎노드를최소화시키는방법을보였다 향후일상생활에서접할수있는다양한 완전문제들에대하여최적의풀이를수행할수있도록제안된방법을응용하고개선할수있는연구가지속적으로필요하다 REFERENCE
년경북대학교전자공학과공학사졸업 년일본 대학이공학부계산기과학전공공학석사 년일본 대학이공학부계산기과학전공 공학박사 년일본국제전신전화연구소 기술고문 년일본 대학이공학부객원연구원 년 현재동의대학교컴퓨터소프트웨어공학과교수관심분야 정보시스템 기계번역 인터넷비즈니스 년부경대학교냉동공학전공공학사졸업 년부산외국어대학교컴퓨터공학전공공학석사 년동의대학교컴퓨터소프트웨어공학전공공학박사 년동의대학교산업기술개발연구소 연구원 년 현재한국승강기대학승강기공학부교수관심분야 소프트웨어설계 게임