C# - Lights Out 퍼즐 풀기
역시 "코딩 더 매트릭스"의 이야기입니다.
코딩 더 매트릭스
; http://www.yes24.co.kr/24/goods/17967245
(검색해 보면, '전구 불끄기 게임'으로 알려진) Lights Out 게임에 대한 설명이 있는데요.
Lights Out (game)
; https://en.wikipedia.org/wiki/Lights_Out_(game)
규칙은 간단합니다. 버튼을 누르면 그것의 On/Off 상태가 토글되면서 동시에 그 버튼의 상/하/좌/우 4개의 버튼도 상태가 토글됩니다. 임의의 N1 * N2 격자로 된 버튼들이 제각각 임의의 상태로 초기화되었을 때 일련의 버튼들을 눌러 모든 버튼을 Off 상태로 만드는 것이 문제입니다.
예를 들어, 다음의 초기 상태를 갖는 버튼(빨간색 == 1, 파란색 == 0)들이 있을 때,
여기서 (0,0) 버튼을 누르면 다음과 같이 상태가 변경됩니다.
이어서 (1,1) 버튼을 누르면 다음과 같이 상태가 변경되는 것이고.
이런 식으로 일련의 버튼을 눌러, 모든 상태를 Off 상태(위의 그림에서는 파란색)로 만들어야 합니다.
이 책이 재미있는 것은, 그 상태 변화의 규칙을 나타내는 정확한 수학적 풀이를 먼저 해본다는 것입니다.
우선 버튼이 토글되는 것에 대한 상태 변화를,
0 상태의 버튼을 누르면 1
1 상태의 버튼을 누르면 0
다음과 같이 GF(2) 연산으로 연결한다는 점입니다.
0 상태이므로 0 스스로를 더해서 1로.
1 상태이므로 1 스스로를 더해서 0으로.
이와 함께 각각의 버튼에 대해 변화하는 버튼들을 일련의 리스트로 정의합니다. 예를 들어, (0, 0)의 버튼을 누르는 경우 변화되는 버튼들은 다음과 같습니다.
v0 = { (0,0), (0,1), (1,0) }
이런 식으로 버튼 하나를 누를 때마다 변화되는 버튼들을 v
0, v
1, ..., v
24로 정의할 수 있습니다. 이와 함께 현재의 원본 버튼 상태를 s라고 해보면, 이제 모든 버튼의 상태를 끄는 것을 다음의 수식으로 정리할 수 있습니다.
s + (v0 + v1 + ... + v24) = { 0, ...., 0 }
그리고 위의 수식 양변에 동일하게 (+ s)를 해봅니다. 그럼, 좌변은 (s + s)는 XOR 결합이므로 { 0, ..., 0 }로 되고, 우변은 { 0, ..., 0 } + s가 되므로 결국 s가 됩니다. 따라서 다음과 같이 정리가 됩니다.
(v0 + v1 + ... + v24) = s
게다가 GF(2)는 교환법칙이 성립하는 연산이라는 점과, 동일한 v
n 연산이 2번 나오는 경우 스스로 {0,...,0}으로 상쇄된다는 점을 고려했을 때 버튼을 누르는 동작은 단 한 번이라는 걸로 한정 지을 수 있습니다.
따라서, 문제를 풀이하는 방법은 결국 v
0 ~ v
24의 상태를 조합해서 연산한 다음 그것이 s 상태의 값과 같은 것이 있는지를 찾으면 되는 것입니다.
와~~~ 멋있습니다. ^^
이렇게 수식으로 증명되었으니 남은 것은 그에 맞게 코딩을 하면 됩니다. 우선, 지난번 소개한 GF(2) 코드를 기반으로,
C# - 갈루아 필드 GF(2) 연산
; https://www.sysnet.pe.kr/2/0/10972
초기 버튼 상태 s를 다음과 같이 설정할 수 있습니다.
using System;
using System.Collections.Generic;
using FiniteFieldArithmetics;
namespace LightsOutSample
{
class Program
{
static FiniteField GF2 = new FiniteField(2);
static Polynomial one = new Polynomial(GF2, 1);
static Polynomial zero = new Polynomial(GF2, 0);
static void Main(string[] args)
{
Polynomial[,] s = new Polynomial[,]
{
{ one, one, one, one, zero },
{ one, one, one, zero, one},
{ one, one, one, zero, one },
{ zero, zero, zero, one, one },
{ one, one, zero, one, one },
};
}
}
}
그리고, 각 버튼이 눌렸을 때 그 버튼과 함께 상태 변화가 될 버튼 목록 v
0 ~ v
24을 구해둡니다.
List<ButtonVector> v = InitButtonList(s);
private static List<ButtonVector> InitButtonList(Polynomial[,] s)
{
List<ButtonVector> list = new List<ButtonVector>();
for (int row = 0; row < s.GetLength(0); row++)
{
for (int col = 0; col < s.GetLength(1); col++)
{
ButtonState[] items = GetButtonList(s, row, col);
ButtonVector v = new ButtonVector(items, string.Format("v({0},{1})", row, col));
list.Add(v);
}
}
return list;
}
private static ButtonState[] GetButtonList(Polynomial[,] s, int row, int col)
{
List<ButtonState> list = new List<ButtonState>();
list.Add(new ButtonState(one, row, col));
if (row != 0)
{
list.Add(new ButtonState(one, row - 1, col));
}
if (col != 0)
{
list.Add(new ButtonState(one, row, col - 1));
}
if (row != s.GetLength(0) - 1)
{
list.Add(new ButtonState(one, row + 1, col));
}
if (col != s.GetLength(1) - 1)
{
list.Add(new ButtonState(one, row, col + 1));
}
return list.ToArray();
}
이제, 버튼에 따른 상태 변화 목록을 다음의 코드를 이용해,
C# - 모든 경우의 수를 조합하는 코드 (1)
; https://www.sysnet.pe.kr/2/0/10977
모든 경우의 수를 열람하고, 그 열람된 경우의 수에 대한 상태를 모두 반영한 값과 처음의 s 목록을 비교하는 것으로 코드를 완료할 수 있습니다.
Polynomial[,] newState = new Polynomial[,]
{
{ zero, zero, zero, zero, zero },
{ zero, zero, zero, zero, zero },
{ zero, zero, zero, zero, zero },
{ zero, zero, zero, zero, zero },
{ zero, zero, zero, zero, zero },
};
Combination<ButtonVector> c = new Combination<ButtonVector>(v.ToArray());
int equalState = 0;
foreach (var elems in c.Successor())
{
ButtonVector[] items = c.Apply();
MakeZero(newState);
ApplyState(newState, items);
if (IsEquals(s, newState) == true)
{
PrintCombinations(items);
Console.WriteLine(" == s");
equalState++;
}
}
예제 코드의 경우, 다음과 같은 4가지 조합이 출력됩니다.
{ v(0,0) + v(0,1) + v(0,2) + v(0,4) + v(1,0) + v(1,2) + v(1,3) + v(1,4) + v(2,0) + v(2,3) + v(3,0) + v(3,2) + v(3,4) + v(4,2) + } == s
{ v(0,0) + v(0,3) + v(0,4) + v(1,3) + v(2,1) + v(2,4) + v(4,1) + v(4,3) + } == s
{ v(0,1) + v(1,3) + v(2,0) + v(2,3) + v(4,0) + v(4,4) + } == s
{ v(0,2) + v(0,3) + v(1,0) + v(1,2) + v(1,3) + v(1,4) + v(2,1) + v(2,4) + v(3,0) + v(3,2) + v(3,4) + v(4,0) + v(4,1) + v(4,2) + v(4,3) + v(4,4) + } == s
어디, 답이 맞는지 직접 테스트 해볼까요? ^^ 다음의 사이트에 가서,
A Lights Out Puzzle with Solver (JavaScript)
; http://www.ueda.info.waseda.ac.jp/~n-kato/lightsout/
직접 상태를 편집한 다음 위에서 나온 해답으로 좌표에 따른 버튼을 눌러봅니다.
첨부한 파일은 이 글의 예제 코드를 포함하는데요. FiniteField 클래스로 계산하는 것이 느려 XOR 연산으로 바꾼 소스 코드를 함께 첨부해 두었습니다. 참고로, XOR로 바꿨어도 2
25의 조합에 따른 상태 값 계산이 그다지 빠르지 않습니다. 제 컴퓨터 기준으로 약 1분 가량이 소모되었는데요, 재미있는 것은 "
A Lights Out Puzzle with Solver (JavaScript)" 웹 페이지의 "Solve" 버튼의 계산 결과는 바로 나온다는 점입니다. ^^ 왜냐하면...
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]