DeScramble – Game Logic
This is the 4th installment about my Scramble solver, DeScramble. You can check out the first 3 parts here, here, and here. In this post I am going to write a little about the game logic and how the program is setup to play the game.
The rules of the game are pretty simple; find words on the game board using a chain of adjacent letters and use each letter only once per word. The brunt of the logic, which isn’t much, is knowing which letters are adjacent to which. Since the game board is a square and the adjacent letters are above and below one another, we have to create a map in the code to tell us which letters are next to which.
 |
Valid Moves |
| 0 => 1, 5, 6 | |
| 1 => 0, 2, 5, 6, 7 | |
| …. | |
| 12 => 6, 7, 8, 11, 13, 16, 17, 18 | |
| …. | |
| 24 => 18, 19, 23 |
We could of course create a static map of which squares are adjacent to which, but this doesn’t allow us the flexibility to solve for different sized boards (Scramble has both 4×4 and 5×5 games). So how do we go about creating this map in a flexible way? Before I show the code to setup the valid character chains I think it will be helpful to go over a few of the basic constructs of the solver.
A game board is made up a many board letters:
Collection<BoardLetter> gameBoard = new Collection<BoardLetter>();
internal class BoardLetter
{
public char Letter;
public sbyte Position;
public BoardLetter(char letter, sbyte position)
{
Letter = letter;
Position = position;
}
}
The dictionary of words is partitioned by first letter so searching goes a little faster:
Dictionary<char, List<string>> dictionary = new Dictionary<char, List<string>>();
The valid character chains are keyed off position and contain a list of BoardLetters adjacent:
Dictionary<sbyte, Collection<BoardLetter>> validCharacterChains = new Dictionary<sbyte, Collection<BoardLetter>>();
Creating the character chains is pretty straight forward. The general formula for finding adjacent positions would be position ± 1 and position ± row ± 1. This formula works for all positions except those on the edge of the game board (top/bottom row and right/left column). Since we know the game boards are always square finding the edge positions to handle the exceptions is simplified. The finished method:
private void LoadCharChains()
{
validCharacterChains.Clear();
for (sbyte i = 0; i < puzzleLength; i++)
{
validCharacterChains.Add(i, new Collection<BoardLetter>());
double col = (i + 1) % square;
if (col != 1) // not left col so there is a char to the left
{
validCharacterChains[i].Add(gameBoard[i - 1]);
}
if (col != 0) // not right col so there is a char to the right
{
validCharacterChains[i].Add(gameBoard[i + 1]);
}
if (i >= square) // not first row so there is a char above
{
validCharacterChains[i].Add(gameBoard[i - square]);
if (col != 1) // not first row not left col so there is a char above left
{
validCharacterChains[i].Add(gameBoard[i - square - 1]);
}
if (col != 0) // not first row not right col so there is a char above right
{
validCharacterChains[i].Add(gameBoard[i - square + 1]);
}
}
if (i < (puzzleLength - square)) // not last row so there is a char below
{
validCharacterChains[i].Add(gameBoard[i + square]);
if (col != 1) // not last row not left col so there is a char below left
{
validCharacterChains[i].Add(gameBoard[i + square - 1]);
}
if (col != 0) // not last row not right col so there is a char below right
{
validCharacterChains[i].Add(gameBoard[i + square + 1]);
}
}
}
}
Now that we have the valid moves mapped out we can just loop though the dictionary of words to see if they can be found on the game board. We use recursion for this keeping track of where we have traversed on the board so we don’t use the same position twice. Not the cleanest code but it works:
private void SolvePuzzle()
{
foreach BoardLetter boardLetter in gameBoard)
{
foreach (string possibleAnswer in dictionary[boardLetter.Letter])
{
if (!answers.Contains(possibleAnswer))
{
foundAnswer = false;
List<sbyte> testedPositions = new List<sbyte>();
testedPositions.Add(boardLetter.Position);
string startWord = boardLetter.Letter.ToString();
if (startWord.Equals("q"))
{
startWord = "qu";
}
CheckBoardForAnswer(boardLetter, startWord, possibleAnswer, testedPositions);
}
}
}
}
private void CheckBoardForAnswer(BoardLetter boardLetter, string workingWord, string possibleAnswer,
List<sbyte> testedPositions)
{
for (sbyte i = 0; i < validCharacterChains[boardLetter.Position].Count; i++)
{
if (!foundAnswer)
{
BoardLetter workingLetter = validCharacterChains[boardLetter.Position][i];
if (!testedPositions.Contains(workingLetter.Position))
{
string testWord = String.Concat(workingWord, workingLetter.Letter);
// if we've added a q then go ahead and add a u
if (testWord.EndsWith("q"))
{
testWord += "u";
}
if (testWord.Equals(possibleAnswer))
{
answers.Add(possibleAnswer);
foundAnswer = true;
}
else if (possibleAnswer.StartsWith(testWord))
{
testedPositions.Add(workingLetter.Position);
CheckBoardForAnswer(workingLetter, testWord, possibleAnswer, testedPositions);
testedPositions.Remove(workingLetter.Position);
}
}
}
}
}
In my next (and most likely last) post I will go over how the screen processing works.
