스도쿠 규칙 검사의 하스켈 구현

원문은 Monaca: 스도쿠 규칙 검사 에서 가져왔습니다. 저는 한단계 건너서 rein 님의 Quiz: 스도쿠 규칙 검사 를 보고 알게 되었습니다.

스도쿠는 1~9까지 숫자가 겹치지 않게 채워 넣는 게임이다.

여기서는 규칙을 조금 단순하게 해서 한 열에 1~9까지 숫자가 빠짐없이 들어 있는지 검사하는 코드를 작성한다고 가정하자.

입력 값이 규칙에 맞으면 True, 틀리면 False를 출력한다.

입력
123456789
112345678
223456788
012345678
134445679

출력
True
False
False
False
False

이런 문제를 풀 수 있는 방법은 대략

1. 정렬 후 비교
2. 원소 카운팅 – 카운팅 소트(counting sort)에서 사용하는
3. set 같은 자료구조를 사용하는 방법

등이 있습니다.

아무래도 속도가 가장 빠른 방법은 카운팅 소트에서처럼 입력값을 쭉 읽어나가면서 1부터 9의 갯수를 세는 방법인데, 이 경우 길이가 9로 고정되어 있으므로 아무 카운트나 2가 되면 중간에 바로 False 를 리턴할 수 있습니다.

그 외에 파이썬의 경우 정렬 후 비교나 set() 으로 만든 후 비교해도 코드가 간단하게 한줄로 나옵니다.

이미 속도에 중점을 둔 방식이나 그 외에 방식들은 많은 분들이 좋은 코드를 올려주셔서 뭔가 다른 방법 없나 생각해보다가 원래 문제 의미를 그대로 풀어쓰는 형태로 Haskell 로 짜보기로 했습니다.

그렇게 해서 나온 하스켈 코드가 …

sudoku_check x = all (flip elem x) [1..9]

실행 결과 (ghci 사용¹)

Prelude> let sudoku_check x= all (flip elem x) [1..9]
Prelude> sudoku_check [1,2,3,4,5,6,7,8,9]
True
Prelude> sudoku_check [1,1,2,3,4,5,6,7,8]
False
…

입니다. 보시면 아시겠지만 1부터 9까지의 숫자가 모두 입력값에 있어야만 True 를 리턴하는 함수입니다.² 입력값을 여러번 읽으므로 물론 속도는 느리지만 문제의 의미를 그냥 코드로 옮겨적은 형태고 간단해 보여서 올립니다.

하지만 임의의 길이의 입력값들도 다 처리할 수 있는 일반적인 솔루션이기 때문에 입력값의 길이가 9로 제한되어 있다는 조건을 유용하게 사용하지 못한 점은 약간 아쉽네요.

1. ghci 에 바로 입력 시에는 앞에 “let ” 을 붙여줘야 합니다. [↩]
2. 중간에 flip 은 인자 순서 때문에 들어간 보조 함수고 의미 상은 all (elem’ x) [1..9] 와 같습니다. [↩]

This work, unless otherwise expressly stated, is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 2.0 Korea License.

관련된 포스트들

• 개미 수열의 하스켈 구현 (0)
• C++ Labyrinth #1 (4)
• 홀짝도 구분 못하는 STL (5)
• 모든 상위 클래스의 소멸자는 가상이어야 하는가? (2)
• 내부 개발툴 자동 업데이트 기능 구현하기 (4)