알고리즘 연습도 해볼겸, 다양한 퍼즐의 solver 프로그램을 직접 만들어보고 싶기도 해서 시작해보려고 한다.
다양한 퍼즐이 있지만, 스도쿠 같은 유명한 종류들은 solver가 이미 존재한다.
처음 스타트로 잡으려고 하는 Skyscrapers 퍼즐 같은 경우도 이미 solver가 존재하긴 하지만, 지금부터 만드려고 하는 solver들의 목적은 바로 '특수 규칙'도 다룰 수 있는 solver를 만들고 싶다는 점이다.
퍼즐 마니아들을 일반 퍼즐 규칙에 특수 규칙이 붙거나, 두 종류 이상의 퍼즐 규칙이 융합된 퍼즐들을 자주 풀게 되는데, 그러한 퍼즐들도 solver에 입력될 수 있으면 좋겠다고 생각했다.
각 퍼즐의 특수 규칙(variant)들 그때 그때 다루기로 하고, 이번 포스트에는 기본적인 Skyscrapers 규칙을 적어보고, 어떤 식으로 접근해야 할지에 대해서 생각해보는 것으로 한다.
Skyscrapers 규칙
참고 링크 : https://www.gmpuzzles.com/blog/skyscrapers-rules-and-info/
NxN 판에 1~N까지의 숫자를 채우는데, 스도쿠와 비슷하게 가로, 세로상의 줄에는 중복되는 숫자 없이 각 숫자가 한번씩 와야 한다.
판 안에 있는 숫자는 건물의 '높이'를 상징한다.
판 밖에 있는 숫자는, 해당 숫자에서 판을 바라봤을 때, '보이는 건물'의 갯수를 의미하는데, 만약 높이가 더 높은 건물이 앞에 있다면, 그보다 낮은 건물은 보이지 않는다.
예시로, 위 그림의 아래쪽 힌트 중 첫번째 5의 힌트는, 해당 세로줄을 바라봤을 때 보이는 건물은 총 5개라는 의미이다.
정답을 봤을 때 아래서부터 읽으면 "1 2 3 4 6 5"인데, 맨 마지막 5의 건물은 6 건물에 의해 가려지기 때문에 보이지 않는 판정인 것이다.
가끔 등장하는 특수 규칙 종류
여기에 설명된 특수 규칙보다 다양할 수 있지만, 보통 자주 등장하는 규칙으로는
- 판에 이미 숫자가 적혀져 있을 수 있다. 이 경우에는 그 숫자는 고정이다.
- 힌트가 숫자가 아닐 수 있다. (보통 ABC로 표시) 이럴 경우, 해당 기호가 어떤 숫자인지는 퍼즐을 푸는 사람이 알아서 알아내야 한다.
(Cipher 룰)
- 힌트 및 판에 특수 표시가 되어 있다. 해당 기호는 그 칸에 해당하는 숫자가 짝수인지 홀수인지를 의미한다. (Even/Odd 룰)
최종적으로 만들 solver에 적용할 특수 규칙은 Cipher룰 위주로 생각 중이다.
접근법
보통 Skyscrapers 퍼즐을 푼다고 하면 다음과 같은 방식을 사용한다.
- Edge clue initialization
- Resolved cell constraint propagation
- Process of elimination
- Clue elimination
각 방식의 자세한 설명은 아래를 참고하면 좋을 것 같다.
(링크 : https://www.krnsk0.dev/posts/skyscraper-puzzle-1/)
해당 링크에 나온 설명은 JS로 구현한 프로그램을 설명해준다.
앞으로 저걸 참고로 코드를 작성해볼 예정이다.
초기 설정
하다가 조금 바뀔 수 있다고 생각은 들지만,
대략적으로 한번 정해보겠다.
일단 기본 Skyscrapers 퍼즐 틀을 만든다고 생각하고 생각해보면,
필요한 건 우선 보드 크기 N x N 을 정하는 것이다.
힌트 같은 경우는 저분처럼 왼쪽 위부터 시작해서 4 x N 크기의 배열에 저장하는 것으로 생각 중이다.
위의 그림을 예시로 들어보면,
[0,0,3,0,3,3,0,4,4,4,0,0,0,0,5,0,5,0,0,2,2,0,2,0] 이런 식으로 표시할 수 있겠다.
방향성을 생각해서 아예 4개로 나눌 수도 있다고 생각은 들지만, 우선 이렇게 해볼 생각이다.
백준 문제 풀이처럼 지금은 주어진 입력과 출력을 대략 정해보도록 하겠다.
입력
첫째 줄에 판의 크기(N)이 주어진다.
2 ~ 5번째 줄에는 외부 힌트가 왼쪽 위부터 시작해서 시계 방향으로 (4 x N)개의 정보가 주어진다. 힌트가 빈칸인 경우는 0으로 표시한다.
출력
N x N 판의 정답을 출력한다.
예제 입력
6
0 0 3 0 3 3
0 4 4 4 0 0
0 0 5 0 5 0
0 2 2 0 2 0
예제 출력
2 5 3 6 1 4
1 6 2 5 4 3
6 4 5 1 3 2
5 3 6 4 2 1
4 2 1 3 6 5
3 1 4 2 5 6
