1. Column, Row, and Minigrid Elimination (CRME)
이번 챕터에서는 Column, Row, and Minigrid Elimination (CRME)을 이용하여 퍼즐을 해결한다. 아마도 난이도가 높은 퍼즐은 단순한 CRME 만 가지고는 해결이 안될터지만, 향후에 해결할 것 같다.
일단 기본 생각은 아래와 같다.
Scan each cell in the grid from left to right, top to bottom For each cell: Set possible values for each cell to 123456789 Scan its column and eliminate the values already present in the column Scan its row and eliminate the values already present in the row Scan its minigrid and eliminate the values already present in the minigrid If there is only one possible value for the cell, the number for the cell is confirmed Until no more cells can be confirmed
2. 예외
- 해결 불가능한 퍼즐
- 플레이어가 입력한 값으로 인해 퍼즐이 해결 불가능해 질 경우
위 두가지 상황에서는 경고를 한다.
3. CRME 구현
아래의 member variable을 Form1 class에 추가한다.
// for CRME technique private String [,] possible = new String[9, 9]; private Boolean HintMode;
possible[,]은 각 셀의 가능한 값들을 저장한다. String 클래스의 Replace() 같은 메쏘드를 이용하는 것이 편리하여 String 타입으로 선언. HintMode는 유저가 힌트를 요구했는지를 보관하는 변수. 만약에 HintMode가 true 이면, CRME 알고리즘은 현재 셀의 값을 찾아 확정하고, 다른 셀의 값을 찾지 않고 콘트롤을 유저에게 넘긴다.
4. SetCell() 수정
아래 코드와 같이 (추가 부분)을 추가한다. 세을 지울경우 possible value 값을 초기화 하는 루틴이다.
//
// set a cell to a given value
//
public void SetCell( int col, int row, int value, int erasable )
{
// locate particular Label control
Control [] lbl = this.Controls.Find( col.ToString() + row.ToString(), true );
Label cellLabel = lbl[0] as Label;
// save the value in the array
actual[col, row] = value;
// if erasing a cell, you need to reset the possible values
// for all cells
// (추가 부분)
if ( value == 0 )
for ( int r = 1; r < 10; r++ )
for ( int c = 1; c < 10; c++ )
if ( actual[c, r] == 0 )
possible[c, r] = String.Empty;
// set the appearance for the Label control
if ( value == 0 ) // erasing the cell
{
cellLabel.Text = String.Empty;
cellLabel.Tag = erasable;
cellLabel.BackColor = DEFAULT_BACKCOLOR;
}
else
{
if ( erasable == 0 )
{
// means default puzzle values
cellLabel.BackColor = FIXED_BACKCOLOR;
cellLabel.ForeColor = FIXED_FORECOLOR;
}
else
{
// means user-set value
cellLabel.BackColor = USER_BACKCOLOR;
cellLabel.ForeColor = USER_FORECOLOR;
}
cellLabel.Text = value.ToString();
cellLabel.Tag = erasable;
}
}
5. ToolTip Control 추가
유저가 퍼즐을 해결하는데 도움을 주기위해 아래 그림과 같이 possible value를 표시해주는 ToolTip Control을 추가한다. 마우스 커서가 해당 셀에 위치할 때 possible value들을 표시한다.
ToolTip Control을 추가하기 위해, ToolBox의 Common Controls -> ToolTip 을 찾아 더블클릭한다.
그리고 아래의 코드를 추가한다.
//
// set the Tooltip for a Label Control
//
public void SetToolTip( int col, int row, String possibleValues )
{
// locate the particular Label Control
Control [] lbl = this.Controls.Find( col.ToString() + row.ToString(), true );
toolTip1.SetToolTip( lbl[0] as Label, possibleValues );
}
그리고 StartNewGame() 함수에 toolTip1.RemoveAll(); 을 아래와 같이 추가한다.
//
// start a new game
//
public void StartNewGame()
{
saveFileName = String.Empty;
txtActivities.Text = String.Empty;
seconds = 0;
ClearBoard();
GameStarted = true;
timer1.Enabled = true;
toolStripStatusLabel1.Text = "New game started";
toolTip1.RemoveAll();
}
6. 셀의 입력 가능한 값 계산
CalculatePossibleValues() 함수를 아래와 같이 작성하고 추가한다. CalculatePossibleValues()는 해당 셀의 입력 가능한 값을 String으로 리턴하며, 만약 Empty면 Exception을 발생한다.
//
// Calculate the possible values for a cell
//
public string CalculatePossibleValues( int col, int row )
{
String str;
if ( possible[col, row] == String.Empty )
str = "123456789";
else
str = possible[col, row];
// step 1. check by column
for ( int r = 1; r < 10; r++ )
if ( actual[col, r] != 0 )
// that means there is an actual value on it
str = str.Replace( actual[col, r].ToString(), String.Empty );
// step 2. check by row
for ( int c = 1; c < 10; c++ )
if ( actual[c, row] != 0 )
// that means there is an actual value on it
str = str.Replace( actual[c, row].ToString(), String.Empty );
// step 3. check by minigrid
int startC = col - ( ( col - 1 ) % 3 );
int startR = row - ( ( row - 1 ) % 3 );
for ( int rr=startR; rr < startR + 3; rr++ )
for ( int cc=startC; cc < startC + 3; cc++ )
if ( actual[cc, rr] != 0 )
// that means there is a actual value on it
str = str.Replace( actual[cc, rr].ToString(), String.Empty );
// if possible value is an empty string then error,
// because of invalid move
if ( str == String.Empty )
throw new Exception( "Invalid Move" );
return str;
}
7. Grid 탐색
CheckColumnsAndRows() 함수는 그리드를 검사하여 각 셀을 검사한다. CalculatePossibleValues()를 호출하고 이를 ToolTip Control과 연계시킨다. 만약에 입력 가능한 값이 한개로 결정되면, 셀의 값으로 저장한다. 만약에 유저가 힌트를 요구했을 경우, 첫번째로 값이 결정된
//
// Calculates the possible values for all the cells
//
public Boolean CheckColumsAndRows()
{
Boolean changes = false;
// check all cells
for(int row = 1; row < 10;row++)
{
for(int col = 1;col < 10;col++)
{
if(actual[col,row] == 0)
{
try
{
possible[col, row] = CalculatePossibleValues(col,row);
}
catch(Exception ex)
{
DisplayActivity("Invalid placement, please undo move", false);
throw new Exception("Invalid Move");
}
// display the possible values in the ToolTip
SetToolTip( col, row, possible[col, row] );
if ( possible[col, row].Length == 1 )
{
// that means a number is confirmed
SetCell( col, row, int.Parse( possible[col, row] ), 1 );
// number is confirmed
actual[col, row] = int.Parse( possible[col, row] );
DisplayActivity( "Col/Row and Minigrid Elimination", false );
DisplayActivity( "=========================", false );
DisplayActivity( "Inserted value " + actual[col, row] + " in"
+ "(" + col + ", " + row + ")", false );
// get the UI of the application to refresh
// with the newly confirmed number
Application.DoEvents();
// saves the move into the stack
Moves.Push( col.ToString() + row.ToString() + possible[col, row] );
// if user only ask for a hint, stop at this point
changes = true;
if ( HintMode )
return true;
}
}
}
}
return changes;
}
8. Hint / Solve Puzzle 기능 구현
Hint 버튼과 Solve Puzzle 버튼의 이벤트 핸들러를 생성하고 아래와 같이 수정한다.
//
// Hint button
//
private void btnHint_Click( object sender, EventArgs e )
{
// show hints one cell at a time
HintMode = true;
try
{
SolvePuzzle();
}
catch
{
MessageBox.Show(
"Please undo your move",
"Invalid Move",
MessageBoxButtons.OK,
MessageBoxIcon.Error );
}
}
//
// Solve Puzzle button
//
private void btnSolvePuzzle_Click( object sender, EventArgs e )
{
// solve the puzzle
HintMode = false;
try
{
SolvePuzzle();
}
catch
{
MessageBox.Show(
"Pleas undo your move",
"Invalid Move",
MessageBoxButtons.OK,
MessageBoxIcon.Error );
}
}
그리고 SolvePuzzle()은 다음과 같이 작성한다.
//
// Steps to solve the puzzle
//
public bool SolvePuzzle()
{
bool changes;
bool ExitLoop = false;
try
{
do
{
// perform Col/Row and Minigrid Elimination
changes = CheckColumsAndRows();
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;
}
테스트한다.
여기까지 과정중에 알게된 문제점은, Game start를 하기전에 Hint 나 Solve Puzzle 버튼을 누르면, exception 이 발생하는 점, 그리고 Hint나 Solve Puzzle 버튼을 눌러 셀 값을 찾는데 있어서, 하나의 셀값도 확정값을 찾지 못할경우 무한루프에 빠지는 점 두가지이다.
SolvePuzzle()에 다음과 같이 내 임의로 수정했다.
//
// Steps to solve the puzzle
//
public bool SolvePuzzle()
{
bool changes;
bool ExitLoop = false;
int loopCounter = 0;
// if game is not started, return
if ( !GameStarted )
return false;
try
{
do
{
// perform Col/Row and Minigrid Elimination
changes = CheckColumsAndRows();
if ( ( HintMode && changes ) || IsPuzzleSolved() )
{
ExitLoop = true;
break;
}
if ( loopCounter++ == 3 )
return false;
} 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;
}
이렇게 수정해도 툴팁 업데이트 로직이 이해가 가질 않는다. hint 나 solve puzzle 버튼이벤트에 의해 값이 찾아지는 셀까지 툴팁 업데이트가 이뤄진다. 이것은 나중에 내가 해결한다.
'Programming > Programming Sudoku' 카테고리의 다른 글
| Chapter 4. Intermediate Techniques (0) | 2012.10.12 |
|---|---|
| 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 |
