성태의 닷넷 이야기
홈 주인
모아 놓은 자료
프로그래밍
질문/답변
사용자 관리
사용자
메뉴
아티클
외부 아티클
유용한 코드
온라인 기능
MathJax 입력기
최근 덧글
[정성태] How can I tell whether two programs...
[정성태] The case of the fail-fast crashes c...
[정성태] Creating Docker multi-arch images f...
[정성태] BinaryFormatter removed from .NET 9...
[정성태] Extending the Windows Shell Progres...
[우광현] 와..... 범위를 잡았으니 클라이언트가 해당 범위를 확인해본다...
[정성태] 딱히, 그것 이상으로 더 설명할 내용이 없습니다. 동적 포...
[정성태] If Windows 3.11 required a 32-bit p...
[정성태] What is a hard error, and what make...
[괴물신인] 질문작성자인데 이 글을 이제봤네요 ㄷㄷ 이 글처럼 타입별로 인...
글쓰기
제목
이름
암호
전자우편
HTML
홈페이지
유형
제니퍼 .NET
닷넷
COM 개체 관련
스크립트
VC++
VS.NET IDE
Windows
Team Foundation Server
디버깅 기술
오류 유형
개발 환경 구성
웹
기타
Linux
Java
DDK
Math
Phone
Graphics
사물인터넷
부모글 보이기/감추기
내용
<div style='display: inline'> <h1 style='font-family: Malgun Gothic, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>C# - Lights Out 퍼즐 풀기</h1> <p> 역시 "코딩 더 매트릭스"의 이야기입니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 코딩 더 매트릭스 ; <a target='tab' href='http://www.yes24.co.kr/24/goods/17967245'>http://www.yes24.co.kr/24/goods/17967245</a> </pre> <br /> (검색해 보면, '전구 불끄기 게임'으로 알려진) Lights Out 게임에 대한 설명이 있는데요.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > Lights Out (game) ; <a target='tab' href='https://en.wikipedia.org/wiki/Lights_Out_(game)'>https://en.wikipedia.org/wiki/Lights_Out_(game)</a> </pre> <br /> 규칙은 간단합니다. 버튼을 누르면 그것의 On/Off 상태가 토글되면서 동시에 그 버튼의 상/하/좌/우 4개의 버튼도 상태가 토글됩니다. 임의의 N1 * N2 격자로 된 버튼들이 제각각 임의의 상태로 초기화되었을 때 일련의 버튼들을 눌러 모든 버튼을 Off 상태로 만드는 것이 문제입니다.<br /> <br /> 예를 들어, 다음의 초기 상태를 갖는 버튼(빨간색 == 1, 파란색 == 0)들이 있을 때,<br /> <br /> <img alt='lightsOut_gf2_1.png' src='/SysWebRes/bbs/lightsOut_gf2_1.png' /><br /> <br /> 여기서 (0,0) 버튼을 누르면 다음과 같이 상태가 변경됩니다.<br /> <br /> <img alt='lightsOut_gf2_2.png' src='/SysWebRes/bbs/lightsOut_gf2_2.png' /><br /> <br /> 이어서 (1,1) 버튼을 누르면 다음과 같이 상태가 변경되는 것이고.<br /> <br /> <img alt='lightsOut_gf2_3.png' src='/SysWebRes/bbs/lightsOut_gf2_3.png' /><br /> <br /> 이런 식으로 일련의 버튼을 눌러, 모든 상태를 Off 상태(위의 그림에서는 파란색)로 만들어야 합니다.<br /> <br /> 이 책이 재미있는 것은, 그 상태 변화의 규칙을 나타내는 정확한 수학적 풀이를 먼저 해본다는 것입니다.<br /> <br /> 우선 버튼이 토글되는 것에 대한 상태 변화를,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 0 상태의 버튼을 누르면 1 1 상태의 버튼을 누르면 0 </pre> <br /> 다음과 같이 GF(2) 연산으로 연결한다는 점입니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 0 상태이므로 0 스스로를 더해서 1로. 1 상태이므로 1 스스로를 더해서 0으로. </pre> <br /> 이와 함께 각각의 버튼에 대해 변화하는 버튼들을 일련의 리스트로 정의합니다. 예를 들어, (0, 0)의 버튼을 누르는 경우 변화되는 버튼들은 다음과 같습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > v<sub>0</sub> = { (0,0), (0,1), (1,0) } </pre> <br /> 이런 식으로 버튼 하나를 누를 때마다 변화되는 버튼들을 v<sub>0</sub>, v<sub>1</sub>, ..., v<sub>24</sub>로 정의할 수 있습니다. 이와 함께 현재의 원본 버튼 상태를 s라고 해보면, 이제 모든 버튼의 상태를 끄는 것을 다음의 수식으로 정리할 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > s + (v<sub>0</sub> + v<sub>1</sub> + ... + v<sub>24</sub>) = { 0, ...., 0 } </pre> <br /> 그리고 위의 수식 양변에 동일하게 (+ s)를 해봅니다. 그럼, 좌변은 (s + s)는 XOR 결합이므로 { 0, ..., 0 }로 되고, 우변은 { 0, ..., 0 } + s가 되므로 결국 s가 됩니다. 따라서 다음과 같이 정리가 됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > (v<sub>0</sub> + v<sub>1</sub> + ... + v<sub>24</sub>) = s </pre> <br /> 게다가 GF(2)는 교환법칙이 성립하는 연산이라는 점과, 동일한 v<sub>n</sub> 연산이 2번 나오는 경우 스스로 {0,...,0}으로 상쇄된다는 점을 고려했을 때 버튼을 누르는 동작은 단 한 번이라는 걸로 한정 지을 수 있습니다.<br /> <br /> 따라서, 문제를 풀이하는 방법은 결국 v<sub>0</sub> ~ v<sub>24</sub>의 상태를 조합해서 연산한 다음 그것이 s 상태의 값과 같은 것이 있는지를 찾으면 되는 것입니다.<br /> <br /> 와~~~ 멋있습니다. ^^<br /> <br /> 이렇게 수식으로 증명되었으니 남은 것은 그에 맞게 코딩을 하면 됩니다. 우선, 지난번 소개한 GF(2) 코드를 기반으로,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > C# - 갈루아 필드 GF(2) 연산 ; <a target='tab' href='http://www.sysnet.pe.kr/2/0/10972'>http://www.sysnet.pe.kr/2/0/10972</a> </pre> <br /> 초기 버튼 상태 s를 다음과 같이 설정할 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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 }, }; } } } </pre> <br /> 그리고, 각 버튼이 눌렸을 때 그 버튼과 함께 상태 변화가 될 버튼 목록 v<sub>0</sub> ~ v<sub>24</sub>을 구해둡니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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(); } </pre> <br /> 이제, 버튼에 따른 상태 변화 목록을 다음의 코드를 이용해,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > C# - 모든 경우의 수를 조합하는 코드 (1) ; <a target='tab' href='http://www.sysnet.pe.kr/2/0/10977'>http://www.sysnet.pe.kr/2/0/10977</a> </pre> <br /> 모든 경우의 수를 열람하고, 그 열람된 경우의 수에 대한 상태를 모두 반영한 값과 처음의 s 목록을 비교하는 것으로 코드를 완료할 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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++; } } </pre> <br /> 예제 코드의 경우, 다음과 같은 4가지 조합이 출력됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > { 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 </pre> <br /> 어디, 답이 맞는지 직접 테스트 해볼까요? ^^ 다음의 사이트에 가서,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > A Lights Out Puzzle with Solver (JavaScript) ; <a target='tab' href='http://www.ueda.info.waseda.ac.jp/~n-kato/lightsout/'>http://www.ueda.info.waseda.ac.jp/~n-kato/lightsout/</a> </pre> <br /> 직접 상태를 편집한 다음 위에서 나온 해답으로 좌표에 따른 버튼을 눌러봅니다.<br /> <br /> <hr style='width: 50%' /><br /> <br /> <a target='tab' href='http://www.sysnet.pe.kr/bbs/DownloadAttachment.aspx?fid=1037&boardid=331301885'>첨부한 파일은 이 글의 예제 코드를 포함</a>하는데요. FiniteField 클래스로 계산하는 것이 느려 XOR 연산으로 바꾼 소스 코드를 함께 첨부해 두었습니다. 참고로, XOR로 바꿨어도 2<sup>25</sup>의 조합에 따른 상태 값 계산이 그다지 빠르지 않습니다. 제 컴퓨터 기준으로 약 1분 가량이 소모되었는데요, 재미있는 것은 "<a target='tab' href='http://www.ueda.info.waseda.ac.jp/~n-kato/lightsout/'>A Lights Out Puzzle with Solver (JavaScript)</a>" 웹 페이지의 "Solve" 버튼의 계산 결과는 바로 나온다는 점입니다. ^^ 왜냐하면...<br /> </p><br /> <br /><hr /><span style='color: Maroon'>[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]</span> </div>
첨부파일
스팸 방지용 인증 번호
9618
(왼쪽의 숫자를 입력해야 합니다.)