1. Lone Ranger
lone ranger는 row, column, minigrid의 각 셀의 possible values 중에서 오로지 한 셀에서만 가능한 값을 말한다. 아래 그림을 참조.
(2, 1) 셀만 값 '8' 이 가능하므로 셀 (2, 1)은 값 '8'로 confirm 된다.
2. minigrid 안에서의 lone ranger
세번째 minigrid 의 셀 (7,2)에서 lone ranger '1'이 발견된다. 이 셀은 '1'로 confirm.
3. Row에서의 lone ranger
5번째 row의 셀 (6,5)에서 lone ranger '2'가 발견된다. 이 셀은 '2'로 confirm.
4. Column 에서의 lone ranger
8번째 column의 셀 (8,5)에서 lone ranger '8'을 발견할 수 있다. 이 셀은 '8'로 confirm 된다.
5. 구현 - minigrid에서 lone ranger 찾기
아래의 서브루틴을 추가한다.
// // Look for lone rangers in minigrid // public bool LookForLoneRangersinMinigrids() { bool changes = false; bool NextMiniGrid; int occurrence; int cPos = 0; int rPos = 0; // check for each number from 1 to 9 for ( int n = 1; n < 10; n++ ) { // check the 9 minigrids for ( int r = 1; r < 10; r = r + 3 ) { for ( int c = 1; c < 10; c = c + 3 ) { NextMiniGrid = false; // check within the minigrid occurrence = 0; for ( int rr = 0; rr < 3; rr++ ) { for ( int cc = 0; cc < 3; cc++ ) { if ( (actual[c + cc, r + rr] == 0) && possible[c + cc, r + rr].Contains(n.ToString()) ) { occurrence += 1; cPos = c + cc; rPos = r + rr; if ( occurrence > 1 ) { NextMiniGrid = true; break; } } } if ( NextMiniGrid ) break; } if ( ( !NextMiniGrid ) && ( occurrence == 1 ) ) { // that means number is confirmed SetCell( cPos, rPos, n, 1 ); SetToolTip( cPos, rPos, n.ToString() ); // save the moves into the stack Moves.Push( cPos.ToString() + rPos.ToString() + n.ToString() ); DisplayActivity( "Look for Lone Rangers in Minigrid", false ); DisplayActivity( "===================", false ); DisplayActivity( "Inserted value " + n.ToString() + " in (" + cPos + ", " + rPos + ")", false ); Application.DoEvents(); changes = true; // if user clicks the hint button, exit the function if (HintMode) return true; } } } } return changes; }
6. 구현 - row에서 lone ranger 찾기
아래의 서브루틴을 작성해 추가한다.
// // Look for Lone Rangers in Rows // public bool LookForLoneRangersinRows() { bool changes = false; int occurrence; int cPos = 0; int rPos = 0; // check by row for ( int r = 1; r < 10; r++ ) { for ( int n = 1; n < 10; n++ ) { occurrence = 0; for ( int c = 1; c < 10; c++ ) { if ( ( actual[c, r] == 0 ) && possible[c, r].Contains( n.ToString() ) ) { occurrence += 1; // if multiple occurrence, not a lone any more if ( occurrence > 1 ) break; cPos = c; rPos = r; } } if ( occurrence == 1 ) { // number is confirmed SetCell( cPos, rPos, n, 1 ); SetToolTip( cPos, rPos, n.ToString() ); // save the move into the stack Moves.Push( cPos.ToString() + rPos.ToString() + n.ToString() ); DisplayActivity( "Look for Lone Ranges in Rows", false ); DisplayActivity( "===================", false ); DisplayActivity( "Inserted value " + n.ToString() + " in (" + cPos + rPos + ")", false ); Application.DoEvents(); changes = true; // if user clicks the Hint button, exit function if ( HintMode ) return true; } } } return changes; }
7. 구현 - column 에서 lone ranger 찾기
아래의 코드를 추가한다.
// // Look for Lone Rangers in Columns // public bool LookForLoneRangersinColumns() { bool changes = false; int occurrence; int cPos = 0; int rPos = 0; // check by column for ( int c = 1; c < 10; c++ ) { for ( int n = 1; n < 10; n++ ) { occurrence = 0; for ( int r = 1; r < 10; r++ ) { if ( ( actual[c, r] == 0 ) && possible[c, r].Contains( n.ToString() ) ) { occurrence += 1; // if multiple occurrence, not a lone any more if ( occurrence > 1 ) break; cPos = c; rPos = r; } } if ( occurrence == 1 ) { // number is confirmed SetCell( cPos, rPos, n, 1 ); SetToolTip( cPos, rPos, n.ToString() ); // save the move into the stack Moves.Push( cPos.ToString() + rPos.ToString() + n.ToString() ); DisplayActivity( "Look for Lone Ranges in Columns", false ); DisplayActivity( "===================", false ); DisplayActivity( "Inserted value " + n.ToString() + " in (" + cPos + ", " + rPos + ")", false ); Application.DoEvents(); changes = true; // if user clicks the Hint button, exit function if ( HintMode ) return true; } } } return changes; }
8. SolvePuzzle() 함수 수정
위의 순서도를 아래와 같이 구현했다. 수정한다. 현재 이코드는 chapter 5까지의 변경 사항을 적용했다가 이 글을 위해 다시 되돌렸으므로 이 글이 원한는 대로 동작을 하지 않을 수 있다. 참고하여 문제가 있다면 수정한다.
여기까지 구현했으면 쉬운 퍼즐은 풀린다.
// // Steps to solve the puzzle // public bool SolvePuzzle() { bool changes = false; bool ExitLoop = false; // if game is not started, return if ( !GameStarted ) return false; try { do { do { do { do { // perform Col/Row and Minigrid Elimination (CRME) changes = CheckColumsAndRows(); if ( ( HintMode && changes ) || IsPuzzleSolved() ) { ExitLoop = true; break; } } while ( changes ); if ( ExitLoop ) break; // look for lone rangers in minigrids changes = LookForLoneRangersinMinigrids(); if ( ( HintMode && changes ) || IsPuzzleSolved() ) { ExitLoop = true; break; } } while ( changes ); if ( ExitLoop ) break; // look for lone rangers in rows changes = LookForLoneRangersinRows(); if ( ( HintMode && changes ) || IsPuzzleSolved() ) { ExitLoop = true; break; } } while ( changes ); if ( ExitLoop ) break; // look for lone rangers in Columns changes = LookForLoneRangersinColumns(); if ( ( HintMode && changes ) || IsPuzzleSolved() ) { ExitLoop = true; break; } } while ( changes ); } catch { throw new Exception( "Invalid Move" ); } if ( IsPuzzleSolved() ) { timer1.Enabled = false; Console.Beep(); toolStripStatusLabel1.Text = "**** Puzzle Solved ****"; MessageBox.Show( "Puzzle Solved" ); return true; } else return false; }
'Programming > Programming Sudoku' 카테고리의 다른 글
Chapter 3. Basic Sudoku Solving Technique (0) | 2012.10.08 |
---|---|
Chapter 2. Creating the Sudoku Application (4) (0) | 2012.10.04 |
Chapter 2. Creating the Sudoku Application (3) (0) | 2012.09.27 |
Chapter 2. Creating the Sudoku Application (2) (0) | 2012.09.27 |
Chapter 2. Creating the Sudoku Application (1) (0) | 2012.09.27 |