Table of Contents:
- Game Development with C++
- Sudoku in C++
- C++ Example of Sudoku
- Real-World User Interaction
- Incorporating Artificial Intelligence
- Time and Space Complexity
Game Development with C++
Game development has always been a passion for developers. It helps explore the basic concepts of a language and enhances the developer’s creativity. Despite having numerous opportunities in developing games in hundreds of languages, there are only a few programming languages frequently used by developers for this purpose. C++ is one of the languages often recommended by game developers for a better experience.
Advantages of using C++ for Game Development
It is one of the most used programming languages for game development. Following are some of the main advantages it provides its users.
- Using a high-level language like c++ for game development enables the real learning of object-oriented programming. The development journey proves helpful in providing a hand on experience with the basic concepts which prove fruitful in the future.
- C++ provides a gateway to build most of the big console and Windows games. Moreover, C languages also accommodate c++ for games and assembly languages to help develop low-level engine modules.
- The knowledge of C++ is crucial when it comes to the development of complex games. The main reasons for its heavy demand are that it is faster than other languages, provides reliable compilers and optimizers, and possesses excellent memory management.
- It provides a profound range of libraries for designing complex graphics. Furthermore, it has become one of the primary components of popular game engines like Unreal, PhyreEngine, and Unity Engine. Moreover, it is easily distributable across various platforms.
Sudoku in C++
Sudoku is one of the most popular classic games. The playing grid of sudoku consists of the 9*9 squares space. The game initially has 9 squares combining rows and columns. Out of these 9 squares, every square is a separate grid of 3*3 square spaces. Every row and column has 9 squares. It can be either one player or a two-player game where the competitors try to fill the boxes faster than their opponents. The game’s primary purpose is to fill boxes in every square with numbers ranging from 1 to 9. The exciting thing about the Sudoku game is that no column, row, or square allows repeating a number.
Moreover, the game initially fills some of the squares with random numbers from 1 to 9. The rest of the boxes or squares are left empty for the player to fill. The number of already filled boxes determines the complexity of the game. Following is a picture of a sample Sudoku game for better visualization.
Requirements and Conditions of the Game
In this Sudoku game, the user wants to develop a game where the player fills empty boxes with remaining numbers according to the game’s conditions. Following are the game requirements and resultant conditions for this Sudoku game:
- The game board should be of 9*9 squares space.
- The game should display the grid with some of the boxes already filled with random numbers ranging from 1 to 9.
- The game should allow the player to fill in empty boxes.
- The game should not allow the player to repeat any number in any row, column, or square.
- If the player fills all the boxes with correct numbers and without any repetition, he wins the game.
C++ Example of Sudoku
Following is a step-by-step example of sudoku code in c++:
1. Display Game Board
In this C++ example, the user pre-defines a board with some initial values and stores them in a 2D array. This two-dimensional array is the game board. The developer can then define the showGame() function to print the sudoku board on the console screen.
2. Checking for Number Repetition
· Checking Columns: Additionally, according to the game’s requirements explained above, the game cannot allow the player to repeat any number in any row, column or square. Therefore, the checkColumn() function takes the column number and the input number or value as its arguments and check if the number already exists in the specified column or not. After it has checked the column for repetitive values, it returns the boolean variables based on its findings.
· Checking Rows: Similarly, the checkRow() function matches the input number with every number in the specified row and returns true or false after verifying its presence.
· Checking Small Squares: Furthermore, another function for checking, the checkBox() function takes the starting number of row and column of a specific square, and the user input to match it with the 3 by 3 square to check if the number exists in the entire square or not.
3. Placing Values in Boxes
As all the above conditions need to be false, to place a number in a specific box, the function canEnter() takes the input and calls these above functions inside its body. It checks the output they return. For example, if all of them are false, it returns “true” to confirm that the user can write the input number in that box.
4. Making Final Decision
Moreover, the findBox() function looks for an empty box on the entire game board to see if the user has completed the game or not. After that, it can make a winning decision based on this analysis. In this example, the user does not give the input, but the game generates the input itself in the function finalSolution(), the game’s primary function. The function first checks whether the board has any empty boxes or not. If yes, it returns true otherwise, it moves on to the “for” loop, which generates the values of numbers from 1 to 9 and calls the above functions to check if it can place these values in the grid or not. Additionally, the findBox() function calls itself recursively until it fills all the positions or else returns false to confirm that no solution exists for that particularly given sudoku board.
5. The Main Function
Finally, in the main() function, the user only calls the finalSolution(), which is the primary function that solves the sudoku game. If this function returns true, the user calls the showGame() function to display the completed game board. Otherwise, it prints that “This game can not be solved” because there may be situations where there is no solution to this board game. In that case, the user needs to change the board’s initial values.
Following is the coding example for solving Sudoku:
#include <iostream>
#include<stdio.h>
using namespace std;
#define N 9 //defining grid dimension, that is 9 by 9
int sudokuboard[N][N] =
{
{0, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 1, 0, 0, 0},
{0, 7, 8, 0, 0, 0, 0, 0, 1},
{0, 0, 4, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 2, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0}
};
bool checkColumn(int c, int value)
{
for (int r = 0; r < N; r++)
if (sudokuboard[r] == value)
return true;
return false;
}
bool checkRow(int r, int value)
{
for (int c = 0; c < N; c++)
if (sudokuboard[r] == value)
return true;
return false;
}
bool checkBox(int initial_row int initial_column, int value)
{
for (int r = 0; r < 3; r++)
for (int c = 0; c < 3; c++)
if (sudokuboard[r+initial_row] == value)
return true;
return false;
}
void showGame()
{
for (int r = 0; r < N; r++){
for (int c = 0; c < N; c++)
{
if(c == 3 || c == 6)
cout << " | ";
cout << sudokuboard[r] <<" ";
}
if(r == 2 || r == 5)
{
cout << endl;
for(int k = 0; k<N; k++)
cout << "---";
}
cout << endl;
}
}
bool findBox(int &r, int &c)
{
for (r = 0; r < N; r++)
for (c = 0; c < N; c++)
if (sudokuboard[r] == 0)
return true;
return false;
}
bool canEnter(int r, int c, int value)
{
return !checkRow(r, value) && !checkColumn(c, value) && !checkBox(r-r%3,c-c%3,value);
}
bool finalSolution(){
int r, c;
if (!findBox(r, c))
return true;
for (int val = 1; val <= 9; val++)
{
if (canEnter(r, c, val))
{
sudokuboard[r] = val;
if (finalSolution())
return true;
sudokuboard[r] = 0;
}
}
return false;
}
int main(){
if (finalSolution() == true)
showGame();
else
cout << "This game can not be solved";
}
Note: The users can choose to give their input values and call the above check() functions to validate them.
In the above algorithm, for every box, there are nine possible options. Therefore, considering that the grid is of 9X9, the worst-case time complexity would be O (9^ (n*n)) = O(9^(9*9)). Also, the algorithm uses a matrix or grid to store the game board. Therefore, the space complexity of the above algorithm with 9×9 would be O( n*n) = O(9*9).
Real-World User Interaction
The users can use the above-explained rules and the coding example to program sudoku for real-world users in which the actual users can input values instead of the computer. This way, the developer can achieve real user interaction instead of automating the whole game. In that scenario, the program can ask for the exact row number, column number, and the input value from the user for every input and use the functions such as checkRow(), checkColumn(), checkBox(), and canEnter() to enter the inputted values. After every input by the user, the program can display the updated grid by using the showGame() function.
Moreover, the program needs to keep taking inputs until the player has inputted the values for all the boxes. The user can implement this by using the findBox() function or tweaking it more efficiently. Also, he can choose to show an alert box or any error message to indicate the wrong input value. Additionally, the user can introduce difficulty levels in the game by allowing only a few wrong attempts and ending after the user crosses that number. Also, the user can use the above code to complete the game in case the player loses and display the final board to the user.
Incorporating Artificial Intelligence
The users can implement artificial intelligence in solving the sudoku game as well. As the above coding game checks for a safe number to place it in the empty boxes and try to solve the game, in some scenarios, there may be more than one safe solution, but the above algorithm checks the number in ascending order from one to nine and places the first safe number it gets, in the box, which can lead to the game ending with no possible solution. However, backtracking algorithms solve the game efficiently with the correct solution after checking all the possible combinations.
Time and Space Complexity
The backtracking algorithm uses early pruning to rule out some obvious, not applicable scenarios. Therefore, the time complexity of this backtracking method is O(9^n*n)) as the early pruning helps in achieving the goal in less time, but the upper bound time complexity remains the same as before. The space complexity of this method is O(n*n) to form a matrix to store the output array.
