처음 와이어드>에 수수께끼 하나에 영국 ‘야단법석’이 게재되었던 날, 심심하던 차에 바로 게임을 해봤다. 묘한 재미가 있기에 직접 수도쿠 생성 프로그램을 만들어보기로 했다. 이런 말 하기 창피하지만 결과는 대실패였다. 게임의 규칙을 잘못 이해한 상태에서 개발에 들어갔으니 당연한 결과였다. 다시 시도해 보기엔 이미 지쳐버리기도 했고, 생각보다 규칙이 자유로운 것도 문제였다. NP-Problem이 아닌가 하는 생각까지 들어서 학교 BBS ARA에 질문을 올려봤지만, 아무런 대답도 얻지 못했다. 귀찮은 마음에 내버려두고 잊고 있었는데, 오늘 likejazz님의 블로그에 관련 글이 포스팅된 것을 보고 그때 생각이 났다.
수도쿠 예제를 보면 보통 1 ~ 9 사이의 숫자만 사용한다. 하지만 만약 Grid의 크기와 숫자의 범위에 제한을 두지 않은 상태에서 수도쿠를 생성하려면 쉽지 않다. 혹시 수도쿠 생성 알고리즘을 알고 있는 분이 계시다면 꼭~ 알려주시기 바랍니다. (부탁하는 입장이라 마지막 줄만 존대말을……)
최근에 한국에서도 The Book of Sudoku 1라는 책이 판매되기 시작했다. 바야흐로 한국에도 수도쿠 열풍이 부는 것은 아닌지 모르겠다.
[2005년 11월 05일] 스도쿠 논리퍼즐 1 : 두뇌의 힘을 키우는라는 책이 번역되어 출판됐다.
Author Details
Kubernetes, DevSecOps, AWS, 클라우드 보안, 클라우드 비용관리, SaaS 의 활용과 내재화 등 소프트웨어 개발 전반에 도움이 필요하다면 도움을 요청하세요. 지인이라면 가볍게 도와드리겠습니다. 전문적인 도움이 필요하다면 저의 현업에 방해가 되지 않는 선에서 협의가능합니다.
Sudoku 게임과 생성기
Sudoku라는 퍼즐 게임이 있다. 영국에서 미칠듯한 스피드로 사람들이 풀어제끼고 있다고 한다. 뭐… 퍼즐을 좋아하기는 하지만, 단순한 스타일이라서 아직은 얼마나 재미있는지는 모르겠다. 그러다가 어느분이 생성알고리즘에 대해 거론하였기에 한번 만들어봤다.
이크. 트랙백이 깨졌네요. 아마도 제 MT에서 UTF-8로 보내는것 같은데. 아무튼, 심심해서 Sudoku 생성기 만들어봤습니다.
아주 지극히 간단한 brute force 알고리즘으로 생성합니다. -_-
그리드의 크기가 바뀌어도 룰만 약간 손보면 생성하는데 문제는 없을듯 합니다. 생성시 두가지만 받으면 될듯합니다. 첫번째로,
블럭의 크기(오리지널은 3×3)와 sudoku의 크기(3×3) 두가지를 받아서 만들면 되겠네요. 조금아까 소스 작성할때 지금 제가
말하고 있는 점을 염두에두지 않고 작성하긴 했지만, 한 3-4줄만 바꾸면 그리드크기와 관계없이 생성이 가능할듯 합니다.
오늘은 몸 상태가 말이 아니라 내일 한번 살펴보겠습니다. 저도 처음엔 3×3 그리드에 1~9 조합만 생각했었는데 규모를 늘리니 brute force로는 힘들었더랬죠.
4×4까지 1초안에 해결가능. 5×5는 1초~10분정도 사이에 해결가능하더군요.
문제에 때라서는 10분이 넘게 안 끝나는경우도 있습니다.
일단 궁금해서 사이트를 좀 뒤져봤는데, 이 퍼즐에 대해서 wikipedia를 찾
아보니 아무래도 생성하는 문제는 NP가 맞는거 같네요. wikipedia에 문제
에 대한 해결법을 써놓은것이 전부 brute force더군요
wikipedia 생각은 못했네요. 저도 살펴보겠습니다. 감사합니다.