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 |
