2D Array game assignments
Problem 1:
In this lab, you will be given a table of letters and a set of words to find. Your job is to write a C++ assignment program that reads the table and finds the words in the table. The output should be the location (row, column) and direction of each of the words given to look for, or it should indicate that the word could not be found. Words can come in the table horizontal (left to right), vertical (top, down), or diagonal (top-left to top-right). See example file:
Size 8, 8
Train
Pet
Dog
Cat
Ghost
Output:
Row Colum Direction
Train: 5 0 Horizontal
Pet: 1 4 Diagonal
Dog: Not Found
Cat: 2 0 Diagonal
Ghost: 3 7 Vertical
Things to note: The width and height may be different, so the letter table may be 7 by 9 or 4 by 18. The max size of the letter table is 24 (row or column) and this should be coded in as a const variable (in case it changes). There is however no limit to the amount of words that you may have to search for.
Bonus: In addition to the current output also output the letter table, but this time edit the color (of style) of the font to highlight the words in the table:
Problem 2:
Read in a file of numbers that form a sudoku puzzle. No, we are not filling in the puzzle, this is already done for you. Your job is to output whether or not the puzzle is correctly done or not. A sudoku puzzle is 9 rows by 9 columns. Each row and column has to have the digits 1 through 9 in them. Additionally, Each block of 9 (3 by 3) also has to have all 9 digits in it. Your job again is to read a file like the one given here, and output if it is a correctly solved puzzle:
Again each column and row is 1 through 9. But each block of 3 is as well. Let's look at the top left corner for example:
1 – 9 is correctly assigned here as it is in each block of 3. You will have to break the arrays down into 9 individual blocks of 3 by 3 in order to check that each number is there. Again, the only output for this problem is a yes or no as to whether the puzzle is valid or not.
Bonus: Like before, in addition to the current output also output the table again, but this time edit the color (of style) of the font to highlight any errors in the table. If two numbers are the same on a row or column highlight them to show them as erroneous.
Solution:
1.
#include < iostream>
#include < iomanip>
#include < fstream>
#include < string>
#include < algorithm>
using namespace std;
// Find the location of the word in the table and return the direction
string searchWord(char table[24][24], int numRows, int numCols, const string &word,
int &outRow, int &outCol)
{
int wordSize = (int) word.size();
// Do search
for (int r = 0; r < numRows; r++)
{
for (int c = 0; c < numCols; c++)
{
// Start search when a character on the first letter makes a match
if (word[0] == table[r][c])
{
// Try left to right
int matchedLetters = 0;
for (int i = 0, tempC = c; i < wordSize && tempC < numCols; i++, tempC++)
{
if (word[i] != table[r][tempC])
break;
matchedLetters++;
}
if (matchedLetters == wordSize)
{
outRow = r;
outCol = c;
return "Horizontal";
}
// Try top to bottom
matchedLetters = 0;
for (int i = 0, tempR = r; i < wordSize && tempR < numRows; i++, tempR++)
{
if (word[i] != table[tempR][c])
break;
matchedLetters++;
}
if (matchedLetters == wordSize)
{
outRow = r;
outCol = c;
return "Vertical";
}
// Try diagonal top-right
matchedLetters = 0;
for (int i = 0, tempR = r, tempC = c; i < wordSize && tempR < numRows && tempC < numCols; i++, tempR++, tempC++)
{
if (word[i] != table[tempR][tempC])
break;
matchedLetters++;
}
if (matchedLetters == wordSize)
{
outRow = r;
outCol = c;
return "Diagonal";
}
// Try diagonal top-left
matchedLetters = 0;
for (int i = 0, tempR = r, tempC = c; i < wordSize && tempR < numRows && tempC >= 0; i++, tempR++, tempC--)
{
if (word[i] != table[tempR][tempC])
break;
matchedLetters++;
}
if (matchedLetters == wordSize)
{
outRow = r;
outCol = c;
return "Diagonal";
}
}
}
}
return "Not Found";
}
// Entry point of the program
int main(int argc, char *argv[])
{
// Load the contents of the file and the words to be searched
cout << "Enter input filename: ";
string filename;
getline(cin, filename);
ifstream inFile(filename.c_str());
// Stop if the file cannot be opened
if (!inFile.is_open())
{
cout << "Error: Failed to open file '" << filename << "'" << endl;
return 0;
}
// Read the size of the table (we assume rows and columns won't go beyond 24)
int numRows;
int numCols;
inFile >> numRows >> numCols;
// Read the letters from the table,
char table[24][24];
for (int r = 0; r < numRows; r++)
for (int c = 0; c < numCols; c++)
inFile >> table[r][c];
// Next we read the words and search it on the table
cout << setw(10) << "" << setw(5) << right << "Row" << setw(10) << right << "Column" << setw(15) << "Direction" << endl;
string word;
while (inFile >> word)
{
cout << setw(10) << left << word;
// Put word to uppercase so that comparison is case insensitive
transform(word.begin(), word.end(), word.begin(), ::toupper);
int row, col;
string direction = searchWord(table, numRows, numCols, word, row, col);
if (direction == "Not Found")
cout << direction << endl;
else
cout << setw(5) << right << row << setw(10) << right << col << setw(15) << direction << endl;
}
inFile.close();
return 0;
}
2.
#include < iostream>
#include < fstream>
#include < string>
using namespace std;
// Check each row it has 1 to 9 values
bool validateRows(int board[9][9])
{
for (int r = 0; r < 9; r++)
{
bool isChecked[9];
for (int i = 0; i < 9; i++)
isChecked[i] = false;
for (int c = 0; c < 9; c++)
{
int number = board[r][c];
// Validate the range and duplicate
if (number < 1 || number > 9 || isChecked[number - 1])
return false;
isChecked[number - 1] = true;
}
// Check that all numbers are used
for (int i = 0; i < 9; i++)
if (!isChecked[i])
return false;
}
return true;
}
// Check each column it has 1 to 9 values
bool validateColumns(int board[9][9])
{
for (int c = 0; c < 9; c++)
{
bool isChecked[9];
for (int i = 0; i < 9; i++)
isChecked[i] = false;
for (int r = 0; r < 9; r++)
{
int number = board[r][c];
// Validate the range and duplicate
if (number < 1 || number > 9 || isChecked[number - 1])
return false;
isChecked[number - 1] = true;
}
// Check that all numbers are used
for (int i = 0; i < 9; i++)
if (!isChecked[i])
return false;
}
return true;
}
// Validate the regions
bool validateRegions(int board[9][9])
{
int nextRow = 0;
int nextCol = 0;
int limit = 3;
while (nextRow < 9)
{
bool isChecked[9];
for (int i = 0; i < 9; i++)
isChecked[i] = false;
// Check the region
for (int row = nextRow; row < (nextRow + limit); row++)
{
for (int col = nextCol; col < (nextCol + limit); col++)
{
int number = board[row][col];
// Validate the range and duplicate
if (number < 1 || number > 9 || isChecked[number - 1])
return false;
isChecked[number - 1] = true;
}
}
// Check that all numbers are used
for (int i = 0; i < 9; i++)
if (!isChecked[i])
return false;
// Okay, region is valid move to the next region
nextCol += limit;
if (nextCol >= 9)
{
nextCol = 0;
nextRow += limit;
}
}
return true;
}
// Entry point of the program
int main()
{
int board[9][9];
// Read the file containing the sudoku numbers
cout << "Enter input filename: ";
string filename;
getline(cin, filename);
// Stop if the file cannot be opened
ifstream inFile(filename.c_str());
if (!inFile.is_open())
{
cout << "Failed to open '" << filename << "'" << endl;
return 0;
}
// Read in the values
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
inFile >> board[r][c];
inFile.close();
// Validate the board
if (validateRows(board) && validateColumns(board) && validateRows(board))
cout << "It is a valid solution." << endl;
else
cout << "It is not a valid solution." << endl;
return 0;
}