Create a Sudoku Bruteforcing Script in C++

About a month ago, I found this video on the Internet, which reached over 5.2 million views on TikTok. Now that my exam period is over, I've finally found time to think about how exactly this system works and how it can be replicated.

Quick disclaimer: This blog post will be a bit longer, as I want to explain the topic completely and not just cover it superficially. So lets get started.

1. How does it work?

I guess that the most you are familiar with the sudoku rules. if you are not, here is a quick explanation:

• 9x9 grid, divided into 3x3 subgrids (boxes).
• Fill each cell with numbers 1-9.
• Each number must appear once in each row, column, and 3x3 box.
• Given some pre-filled numbers, the goal is to complete the grid by following these rules.
• The fewer numbers are given, the harder the sudoku is.

2. The algorithm

Now that we know how a Sudoku works, we need to figure out how to create an algorithm to solve it. So the idea is the following:

1. Entering our first number in the first empty field of the board.
2. Checking if the number is valid or not.
3. If it is, we jump over to the next field.
4. If not, we try again.

3. Writing the Code

In this section we will set up the Sudoku backtracking programme step by step and explain each function in detail.

3.1 Board Representation (The Playing Field)

First we have to define the playing field. In our case, it is a 9x9 grid, which we represent as a 2D array:

typedef std::vector<int> row_t, col_t;
using board_t = std::vector<row_t>;

board_t board = {
	{5, 3, 0, 0, 7, 0, 0, 0, 0},
	{6, 0, 0, 1, 9, 5, 0, 0, 0},
	{0, 9, 8, 0, 0, 0, 0, 6, 0},
	{8, 0, 0, 0, 6, 0, 0, 0, 3},
	{4, 0, 0, 8, 0, 3, 0, 0, 1},
	{7, 0, 0, 0, 2, 0, 0, 0, 6},
	{0, 6, 0, 0, 0, 0, 2, 8, 0},
	{0, 0, 0, 4, 1, 9, 0, 0, 5},
	{0, 0, 0, 0, 8, 0, 0, 7, 9}
};

This 2D vector represents the Sudoku puzzle, where 0 stands for an empty field. The numbers from 1 to 9 are the given values. We will try to fill the empty fields later in our algorithm.

3.2 The is_valid function

Before we enter a number in an empty field, we must ensure that this number is valid. A number is only valid if it does not already appear in the same row, the same column or in the same 3x3 block. This check is performed by the is_valid function:

bool is_valid(const board_t& board, int row, int col, int num) {
	for (int i = 0; i < 9; ++i) {
		if (board[row][i] == num || board[i][col] == num) {
			return false;
		}
	}
	
	int startRow = row - row % 3;
	int startCol = col - col % 3;
	
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			if (board[startRow + i][startCol + j] == num) {
				return false;
			}
		}
	}
	
	return true;
}

This function checks whether the number num is valid in the specified row row, column col and in the 3x3 block:

• First, the entire row and the entire column are checked for the presence of num.
• Then the 3x3 block is checked. This is done by calculating the starting point of the block (startRow and startCol) so that we can then run through all the fields of the block.
• If num already exists at one of these points, the function returns false, which means that the number is not valid. Otherwise it returns true.

Now we come to the heart of the algorithm: the solve_sudoku function, which performs the actual backtracking:

bool solve_sudoku(board_t& board) {
	for (int row = 0; row < 9; ++row) {
		for (int col = 0; col < 9; ++col) {
			if (board[row][col] == 0) {
				for (int num = 1; num <= 9; ++num) {
					if (is_valid(board, row, col, num)) {
						board[row][col] = num;
						
						if (solve_sudoku(board)) {
							return true;
						}
						board[row][col] = 0;
					}
				}
				return false;
			}
		}
	}
	return true;
}

This function implements the backtracking algorithm, which works as follows:

• First, the function runs through every row and every column of the grid to find an empty field (with the value 0).
• Once an empty field has been found, the function tries to enter numbers from 1 to 9 and checks whether each number in this field is valid (using the is_valid function).
• If a valid number is found, it is entered in the grid and the function calls itself recursively to solve the next empty field.
• If the recursive call leads to a solution, the function returns true, which means that the Sudoku has been successfully solved.
• If no number is valid for a field, the field is reset to 0 (backtracking) and the next number is tried.
• If all fields are filled in, the function returns true, which means that the Sudoku has been solved.

Finally, we have the main function that sets up the Sudoku puzzle, tries the solution and outputs the result:

int main() {
	board_t board = {
		{5, 3, 0, 0, 7, 0, 0, 0, 0},
		{6, 0, 0, 1, 9, 5, 0, 0, 0},
		{0, 9, 8, 0, 0, 0, 0, 6, 0},
		{8, 0, 0, 0, 6, 0, 0, 0, 3},
		{4, 0, 0, 8, 0, 3, 0, 0, 1},
		{7, 0, 0, 0, 2, 0, 0, 0, 6},
		{0, 6, 0, 0, 0, 0, 2, 8, 0},
		{0, 0, 0, 4, 1, 9, 0, 0, 5},
		{0, 0, 0, 0, 8, 0, 0, 7, 9}
	};
	
	if (solve_sudoku(board)) {
		for (const auto& row : board) {
			for (int num : row) {
				cout << num << " ";
			}
			cout << endl;
		}
	} else {
		cout << "No solution exists." << endl;
	}
	
	return 0;
}

Here, the Sudoku puzzle is initialised as a 9x9 matrix. The solve_sudoku function is then called to solve the puzzle. If a solution is found, the function outputs the solved Sudoku. If no solution exists, it outputs a corresponding message.