Go to main page
A journey into the programming realm
The point of no return
Leaping into the unknown
Chapter warning
This chapter will contain some algorithms that are usually learned in school.
It is great if you're able to follow the problem and the solution, but if not, do not discourage yourself!
Algorithms are great for exposing you to different problem-solving techniques. However, you will not use them in your everyday programming, and if you actually do need one, you can always look them up on the internet.
Therefore, it's a good idea to read this chapter, but if you are stuck or simply get bored, feel free to go directly to Chapter 3 and come back later on.
Sudoku is a number placement puzzle, where the objective is to fill a square grid, with numbers between 1 to 9. As constraints, each row, column, and sub-grids should contain empty spaces or unique numbers from 1 to 9.
With backtracking, we try to add the digits one by one. When we find that a digit cannot lead to a solution, we backtrack (remove it) and try the next digit.
Steps:
Let’s only look on the top-left grid first.
| 9 | 3 | |
| 5 | 1 | |
| 2 |
Each square contains all the digits from 1 to 9.
We see that we have 4 empty places, and 4 digits that are not there (4, 6, 7, 8)
One of the constrains is to have unique digits in a sub-grid such as this one, so we have to use those digits to fill the empty spaces.
We start with the first available position, and iterate through all digits.
We write 1 in the empty place, and then we check the constraints:
We fail the constraints, because we already have the digit 1 in the same sub-grid. Therefore, we continue with the next digit
We write 2 in the empty place, and then we check the constraints:
We fail the constraints, because we already have the digit 2 in the same sub-grid. Therefore, we continue with the next digit.
Same goes for 3 (exists in sub-grid), 4 (exists in same row), 5 (exists in sub-grid), 6 (exists in same col).
7 is valid, because it doesn’t break the constraints.
Therefore, we write 7 and check the next empty-space.
1,2,3 are in the same sub-grid, so they fail the constraints, but 4 is ok so we write it and check the next empty-space.
1,2,3,4,5 are in the same sub-grid, but 6 doesn’t break constraints, so we write it and check the next empty space.
8 is the only remaining digit that doesn’t exist in sub-grid. We write 8 in the empty-space, but we see that the constraints are broken (same column).
Because the constraints are broken, we clear the value and continue to the next digit.
Since we don’t have any remaining digit (9 in same sub-grid), we return to the previously written digit and continue to the next available digit.
We write the digit 8, but the constraints are again broken (already exists in the same column), and 9 already is in the same sub-grid, so we set as empty space and go one more step back to the previously written digit and continue to the next available digit.
We continue from the current digit (4):
We set as empty space and go one more step back to the previously written digit and continue to the next available digit.
We continue from the current digit (7):
8 is valid, no constraints are broken
We write 8 and check the next empty space
… and so on.
int UNSET = 0;
int N = 9;
int main() {
int grid[N][N] = {
{ 9, 3, 0, 0, 0, 4, 2, 0, 0 },
{ 5, 0, 1, 6, 2, 0, 0, 8, 0 },
{ 0, 0, 2, 0, 9, 0, 4, 5, 1 },
{ 2, 0, 3, 0, 0, 0, 0, 0, 8 },
{ 0, 1, 0, 0, 0, 0, 0, 3, 0 },
{ 8, 0, 0, 0, 0, 0, 7, 0, 5 },
{ 4, 5, 9, 0, 3, 0, 6, 0, 0 },
{ 0, 8, 0, 0, 4, 6, 5, 0, 2 },
{ 0, 0, 6, 9, 0, 0, 0, 4, 3 }
};
Sudoku sudoku(grid);
if (sudoku.solve() == true)
sudoku.display();
return 0;
}
We have a main() function, we create the matrix, and we call the solve function from the Sudoku class (Line 18).
class Sudoku {
int grid[N][N] = {};
public:
Sudoku(int _grid[N][N]) { /* copy the grid to our class */ }
void display() { /* iterate through grid and display data */ }
bool solve();
private:
bool isLegalMove(int row, int col, int num) {
return grid[row][col] == UNSET &&
false == alreadyInRow(row, num) &&
false == alreadyInCol(col, num) &&
false == alreadyInBox(row - row % 3, col - col % 3, num);
}
bool findNextEmpty(int &row, int &col) {
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (grid[row][col] == UNSET)
return true;
return false;
}
bool alreadyInRow(int row, int num) {
for (int col = 0; col < N; col++)
if (grid[row][col] == num) return true;
return false;
}
bool alreadyInCol(int col, int num) {
for (int row = 0; row < N; row++)
if (grid[row][col] == num) return true;
return false;
}
bool alreadyInBox(int box_row, int box_col, int num) {
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row + box_row][col + box_col] == num)
return true;
return false;
}
};
IsLegalMove() function (Line 8-13) returns true if all the conditions below are met:
FindNextEmpty() function (Line 15-21) returns true if:
There’s still an empty position in the grid.
The location for that position is returned through params, as they are sent as reference.
Now we’re left with the solve function, which is implemented below:
bool Sudoku::solve() {
int row, col;
if (!findNextEmpty(row, col))
return true;
for (int num = 1; num <= 9; num++) {
if (isLegalMove(row, col, num)) {
grid[row][col] = num;
if (solve())
return true;
grid[row][col] = UNSET;
}
}
return false;
}
The solve() function is a recursive function.
In line 2 we declare two variables, row and col, which we’ll pass further as references in line 4.
As usual, in each recursive function, we first declare the exit function.
If the findNextEmpty() function returns false, it means we’re out of unset cells, so the sudoku is solved. Therefore, we return true.
For all numbers from 1 to 9 (Line 7):
If it’s a legal move, or in other words, if we can add a digit in that location without having any failed constraints (Line 8):
If the solve function failed – we unset the value in the grid and go for the next digit.
If we iterated through all digits and failed, it means we’re out of the loop. Therefore, we return false (Line 17).
The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.
In order for two queens not to attack each other, we need the following constraints:
With backtracking, we are adding first queen in the upper-left corner, and since the constraints are not broken, we attempt to add the 2nd queen on the 2nd row. Each time we add a queen on the chess board, we check for constraints, and if they are broken, we backtrack to the next available location, and so forth.
For example, following is a solution for 4 Queen problem.
Let’s use a binary matrix which contains 1 in places where queens are placed.
The output matrix for the solution above is the following:
| 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
We start with the chess board empty (no queen placed)
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
We need to position 4 queens (Q1, Q2, Q3, Q4).
Let’s apply our first constrain: queens cannot be on the same row, or on the same column. (otherwise they’re attacking each other.)
I’ll go with them being on different rows.
| 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
We are currently placing Q1.
We start with the first available position (upper-left corner).
| 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
Since the constraints are not broken, we continue with 2nd queen.
After we placed the 2nd queen, we see that the constraints are broken.
Therefore, we return false from the function and choose the next available position for the 2nd queen.
| 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
After we placed the 2nd queen, we see that the constraints are broken.
Therefore, we return false from the function and choose the next available position for the 2nd queen.
| 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
Since the constraints are not broken, we continue with 3rd queen.
| 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
After we placed the 3rd queen, we see that the constraints are broken.
Therefore, we return false from the function and choose the next available position for the 3rd queen.
| 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
After multiple iterations, we see that the constraints are broken for all remaining positions.
Therefore, we return false from the function and choose the next available position for the 2nd queen.
| 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
No constraints are broken, go for the 3rd queen.
| 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 |
After iterations, we see that we have only a possible location for 3rd queen, and we place it there.
| 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 |
There is no available location for 4th queen (all of them break constraints)
So we return false and move Q3.
We don’t have other possible locations for Q3, as it will be attacking Q2
So we return false and move Q2.
There are no available locations for Q2
So we return false and move Q1
| 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 |
Q1 has been moved to the 2nd column, and now we start moving Q2.
The algorithm continues until all 4 queens have been placed, and no constraints are broken.
int N = 4;
void printSolution(int board[N][N]) { /* function to display the board */ }
bool isSafe(int board[N][N], int row, int col) {
for (int i = 0; i < col; i++)
if (board[row][i])
return false;
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (i = row, j = col; j >= 0 && i<N; i++, j--)
if (board[i][j])
return false;
return true;
}
bool do_solveNQ(int board[N][N], int col) {
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (do_solveNQ(board, col + 1))
return true;
board[i][col] = 0; // backtrack
}
}
return false;
}
bool solveNQ() {
int board[N][N] = {};
if (do_solveNQ(board, 0) == false) {
cout << "There is no solution";
return false;
}
printSolution(board);
return true;
}
int main() {
solveNQ();
return 0;
}
As usual, we start from main(), in line 52, which simply calls the solveNQ() function.
The implementation of this function is found on line 40.
In line 41, we create a matrix of size N (where N is declared on line 1).
Afterwards, we call the do_solveNQ() function, passing it the board and the column we’re working with (we start with 0). We use this delegation because this function is recursive.
In case we find a solution, we print it (Line 48). I’ve skipped this implementation, to fit into the page. The display function simply iterates through the board and displays its values.
Line 5 introduces a helper function (isSafe), which receives the board and a location, This function returns true if we cannot add a queen on that location. This happens if:
If this is not the case, then we are free to use that location to position our queen, so we return true (Line 18).
In Line 21 we start the do_solveNQ function.
As previously said, we receive the board and the column we are on.
First, we add the exit condition (Line 22-23): If we finished placing all queens on the table, we solved the problem.
If not, we try to find a location for the queen, in the current column.
For each possible row location (Line 25):
If we reached line 32, it means the condition on line 29 have failed – so we were unable to place the next queen.
This means that it is impossible to have a solution if our queen is positioned on that location – so we backtrack, removing it from that position (Line 32).
We are inside a for statement, so we will attempt to place this queen on the next row.
If there are no more rows available, we will eventually leave the function from line 36, returning false to the caller -> which will continue from line 32.
This was the case with our previous queen:
If the 1st queen goes through all rows and doesn’t find a proper location, it exits on line 36, returning false to the caller (Line 43) -> So we will not have any solution.
On the happy case, where there’s a solution, we position first queen (Line 27), recursively call the same function for col=1 (Line 29).
This will continue with the 2nd, 3rd , and 4th queen, so when we will call the line 29 to solve the problem for col=5, we will reach line 22-23 and returns true.
Returning true from do_solveNQ will go back to the caller in line 29-30, until we go back to solveNQ function in line 43. The if statement will fail, because the return value of the function is true, not false, so we will print the solution (Line 48).
A maze is given as a N*N matrix where the source is in the upper left (0,0) and the destination is on the lower right (N-1, N-1). In this problem, we have a rat which has to start from the source and he has to reach the destination, and can only move down and to the right.
First of all, we will need to check if we have reached the destination. If not:
The main function will be the following:
The main() function starts at line 1. We create a maze object (Line 9) and pass a matrix that contains the value 1 where the road is clear, and 0 if the road is blocked (Line 2-7).
The line 10 calls the algorithm which finds the maze exit and solution.
We need to keep a matrix which represents our maze.
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
int main() {
int grid[N][N] = {
{ 1, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 0 },
{ 1, 1, 1, 1 }
};
Maze maze(grid);
maze.solve();
return 0;
}
int N = 4;
class Maze {
int maze[N][N] = {};
int sol[N][N] = {};
public:
Maze(int _maze[N][N]) {
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
maze[i][j] = _maze[i][j];
}
void display() {
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
cout << sol[row][col] << " ";
}
cout << std::endl;
}
}
bool solve() {
if (do_solve(0, 0) == false) {
cout << "There is no available solution";
return false;
}
display();
return true;
}
private:
bool do_solve(int x, int y) {
if (x == N - 1 && y == N - 1) {
sol[x][y] = 1;
return true;
}
if (isInsideMaze(x, y) == true) {
// add to the soslution
sol[x][y] = 1;
if (do_solve(x + 1, y))
return true;
if (do_solve(x, y + 1))
return true;
// Backtrack
sol[x][y] = 0;
return false;
}
return false;
}
bool isInsideMaze(int x, int y) {
if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
return true;
return false;
}
};
The solve() function called from main is found on line 22. This function simply calls another function (do_solve), which returns a boolean value (True when a solution has been found). We use this function because we will call it recursively, starting from top-left side (0, 0) and advance it’s location until we reach the bottom-right side.
Let’s talk about the class itself. It receives the maze on the constructor (Line 7), and we copy it to our own matrix (Line 8-10). The display() function simply displays the solution for the maze (Line 13-20).
The function defined in line 55 is a helper function (used to help solving the maze). This function returns true if both x and y coordonates are part of the maze (bigger than 0 and less than the maximum size), and if the value of the maze at that location is 1.
Let’s talk now about the do_solve() function (Line 32).
This function receives two parameters (the current location).
First, we have the exit condition. If the current location is the end location, we mark the location as solution and we exit (Line 33-35).
If we haven’t reached the exit yet – we need to keep moving. Because we know that we always start from top left and we always have to reach bottom down, we are interested in moving down and to the right – and that’s exactly what we’ll do.
If we haven’t reached a blocking point (coordonates are still legal and in the maze, and we have somewhere to go), we add the current location as a solution (Line 40). That is because the isInsideMaze function already checks if the current location is set to 1, so we won’t ignore separately the areas in which we cannot go in.
After we mark the current location as solution, we try to go right. This will happen recursively. If the function returned true, it means the solution was recursively found, and at some point we returned from line 35. That is the only point in the function that returns true – the rest of them are triggered from another recursive call.
If at some point we reach a dead end, we reach back to the function that called. We try to go down instead. The same story applies. Assuming this is a dead end – we enter the function (Line 33), the if statement fails, because we’re not at the end point, the if statement on line 38 fails again, because the value of the maze at that location is 0 – so we return false.
If we haven’t found a solution by going recursively to the right or to the bottom, we reached a dead end and we have to go back. (backtrack). Therefore, we remove the current location as a part of solution (Line 49) and return false to the caller.
Vertex: Node containing data
Edge: The line that connects two vertices
Cycle: Cycles occur when nodes are connected in a way that they forms a closed structure.
Cycle: Cycles occur when nodes are connected in a way that they forms a closed structure.
Self loop: An edge that connects a vertex to itself (source = destination).
Divide et impera (Divide and conquer): Break the problem into sub-problems and solve them each recursively.
Negative weight edge refer to edges with a negative cost.