Microsoft MVP성태의 닷넷 이야기
.NET Framework: 592. C# - Lights Out 퍼즐 풀기 [링크 복사], [링크+제목 복사],
조회: 17001
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
(연관된 글이 2개 있습니다.)

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)들이 있을 때,

lightsOut_gf2_1.png

여기서 (0,0) 버튼을 누르면 다음과 같이 상태가 변경됩니다.

lightsOut_gf2_2.png

이어서 (1,1) 버튼을 누르면 다음과 같이 상태가 변경되는 것이고.

lightsOut_gf2_3.png

이런 식으로 일련의 버튼을 눌러, 모든 상태를 Off 상태(위의 그림에서는 파란색)로 만들어야 합니다.

이 책이 재미있는 것은, 그 상태 변화의 규칙을 나타내는 정확한 수학적 풀이를 먼저 해본다는 것입니다.

우선 버튼이 토글되는 것에 대한 상태 변화를,

0 상태의 버튼을 누르면 1
1 상태의 버튼을 누르면 0

다음과 같이 GF(2) 연산으로 연결한다는 점입니다.

0 상태이므로 0 스스로를 더해서 1로.
1 상태이므로 1 스스로를 더해서 0으로.

이와 함께 각각의 버튼에 대해 변화하는 버튼들을 일련의 리스트로 정의합니다. 예를 들어, (0, 0)의 버튼을 누르는 경우 변화되는 버튼들은 다음과 같습니다.

v0 = { (0,0), (0,1), (1,0) }

이런 식으로 버튼 하나를 누를 때마다 변화되는 버튼들을 v0, v1, ..., v24로 정의할 수 있습니다. 이와 함께 현재의 원본 버튼 상태를 s라고 해보면, 이제 모든 버튼의 상태를 끄는 것을 다음의 수식으로 정리할 수 있습니다.

s + (v0 + v1 + ... + v24) = { 0, ...., 0 }

그리고 위의 수식 양변에 동일하게 (+ s)를 해봅니다. 그럼, 좌변은 (s + s)는 XOR 결합이므로 { 0, ..., 0 }로 되고, 우변은 { 0, ..., 0 } + s가 되므로 결국 s가 됩니다. 따라서 다음과 같이 정리가 됩니다.

(v0 + v1 + ... + v24) = s

게다가 GF(2)는 교환법칙이 성립하는 연산이라는 점과, 동일한 vn 연산이 2번 나오는 경우 스스로 {0,...,0}으로 상쇄된다는 점을 고려했을 때 버튼을 누르는 동작은 단 한 번이라는 걸로 한정 지을 수 있습니다.

따라서, 문제를 풀이하는 방법은 결국 v0 ~ v24의 상태를 조합해서 연산한 다음 그것이 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 },
            };
        }
    }
}

그리고, 각 버튼이 눌렸을 때 그 버튼과 함께 상태 변화가 될 버튼 목록 v0 ~ v24을 구해둡니다.

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




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

[연관 글]






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

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 작성자
 



2016-05-25 08시12분
[spowner] 네.. 감사합니다. 개인적인 호기심때문에 여럿 공부를 하시는 모습이 너무 보기 좋습니다. 또 다니시는 회사에 그런 여유를 어느정도 제공하지 않나 해서 부럽기도 하네요
[guest]
2016-05-25 04시39분
여러 가지 기웃거리다 보니, 전문성이 떨어지는 기분입니다. ^^ 그래도 어쨌든 직업이 그렇고, 공부 자체도 재미가 있으니 꾸준히 하게 되는 것 같습니다.
정성태

... 31  32  33  34  35  36  37  38  39  40  41  42  43  [44]  45  ...
NoWriterDateCnt.TitleFile(s)
12545정성태3/2/202111459.NET Framework: 1026. 닷넷 5에 추가된 POH (Pinned Object Heap) [10]
12544정성태2/26/202111675.NET Framework: 1025. C# - Control의 Invalidate, Update, Refresh 차이점 [2]
12543정성태2/26/202110011VS.NET IDE: 158. C# - 디자인 타임(design-time)과 런타임(runtime)의 코드 실행 구분
12542정성태2/20/202112342개발 환경 구성: 544. github repo의 Release 활성화 및 Actions를 이용한 자동화 방법 [1]
12541정성태2/18/20219575개발 환경 구성: 543. 애저듣보잡 - Github Workflow/Actions 소개
12540정성태2/17/20219902.NET Framework: 1024. C# - Win32 API에 대한 P/Invoke를 대신하는 Microsoft.Windows.CsWin32 패키지
12539정성태2/16/20219809Windows: 189. WM_TIMER의 동작 방식 개요파일 다운로드1
12538정성태2/15/202110217.NET Framework: 1023. C# - GC 힙이 아닌 Native 힙에 인스턴스 생성 - 0SuperComicLib.LowLevel 라이브러리 소개 [2]
12537정성태2/11/202111272.NET Framework: 1022. UI 요소의 접근은 반드시 그 UI를 만든 스레드에서! - 두 번째 이야기 [2]
12536정성태2/9/202110218개발 환경 구성: 542. BDP(Bandwidth-delay product)와 TCP Receive Window
12535정성태2/9/20219374개발 환경 구성: 541. Wireshark로 확인하는 LSO(Large Send Offload), RSC(Receive Segment Coalescing) 옵션
12534정성태2/8/20219878개발 환경 구성: 540. Wireshark + C/C++로 확인하는 TCP 연결에서의 closesocket 동작 [1]파일 다운로드1
12533정성태2/8/20219593개발 환경 구성: 539. Wireshark + C/C++로 확인하는 TCP 연결에서의 shutdown 동작파일 다운로드1
12532정성태2/6/202110091개발 환경 구성: 538. Wireshark + C#으로 확인하는 ReceiveBufferSize(SO_RCVBUF), SendBufferSize(SO_SNDBUF) [3]
12531정성태2/5/20219084개발 환경 구성: 537. Wireshark + C#으로 확인하는 PSH flag와 Nagle 알고리듬파일 다운로드1
12530정성태2/4/202113297개발 환경 구성: 536. Wireshark + C#으로 확인하는 TCP 통신의 Receive Window
12529정성태2/4/202110307개발 환경 구성: 535. Wireshark + C#으로 확인하는 TCP 통신의 MIN RTO [1]
12528정성태2/1/20219722개발 환경 구성: 534. Wireshark + C#으로 확인하는 TCP 통신의 MSS(Maximum Segment Size) - 윈도우 환경
12527정성태2/1/20219897개발 환경 구성: 533. Wireshark + C#으로 확인하는 TCP 통신의 MSS(Maximum Segment Size) - 리눅스 환경파일 다운로드1
12526정성태2/1/20217724개발 환경 구성: 532. Azure Devops의 파이프라인 빌드 시 snk 파일 다루는 방법 - Secure file
12525정성태2/1/20217433개발 환경 구성: 531. Azure Devops - 파이프라인 실행 시 빌드 이벤트를 생략하는 방법
12524정성태1/31/20218575개발 환경 구성: 530. 기존 github 프로젝트를 Azure Devops의 빌드 Pipeline에 연결하는 방법 [1]
12523정성태1/31/20218635개발 환경 구성: 529. 기존 github 프로젝트를 Azure Devops의 Board에 연결하는 방법
12522정성태1/31/202110157개발 환경 구성: 528. 오라클 클라우드의 리눅스 VM - 9000 MTU Jumbo Frame 테스트
12521정성태1/31/202110100개발 환경 구성: 527. 이더넷(Ethernet) 환경의 TCP 통신에서 MSS(Maximum Segment Size) 확인 [1]
12520정성태1/30/20218644개발 환경 구성: 526. 오라클 클라우드의 VM에 ping ICMP 여는 방법
... 31  32  33  34  35  36  37  38  39  40  41  42  43  [44]  45  ...