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₀, v₁, ..., v₂₄로 정의할 수 있습니다. 이와 함께 현재의 원본 버튼 상태를 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₀ ~ v₂₄의 상태를 조합해서 연산한 다음 그것이 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₀ ~ v₂₄을 구해둡니다.

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²⁵의 조합에 따른 상태 값 계산이 그다지 빠르지 않습니다. 제 컴퓨터 기준으로 약 1분 가량이 소모되었는데요, 재미있는 것은 "A Lights Out Puzzle with Solver (JavaScript)" 웹 페이지의 "Solve" 버튼의 계산 결과는 바로 나온다는 점입니다. ^^ 왜냐하면...

---

[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]

[최초 등록일: 5/24/2016]
[최종 수정일: 4/6/2023]


이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

by SeongTae Jeong, mailto:techsharer at outlook.com