Backtracking algorithms.
More...
|
template<size_t V> |
void | printSolution (const std::array< int, V > &color) |
|
template<size_t V> |
bool | isSafe (int v, const std::array< std::array< int, V >, V > &graph, const std::array< int, V > &color, int c) |
|
template<size_t V> |
void | graphColoring (const std::array< std::array< int, V >, V > &graph, int m, std::array< int, V > color, int v) |
|
template<size_t V> |
bool | issafe (int x, int y, const std::array< std::array< int, V >, V > &sol) |
|
template<size_t V> |
bool | solve (int x, int y, int mov, std::array< std::array< int, V >, V > &sol, const std::array< int, V > &xmov, std::array< int, V > &ymov) |
|
template<size_t T> |
int | minimax (int depth, int node_index, bool is_max, const std::array< int, T > &scores, double height) |
|
template<size_t V> |
bool | isPossible (const std::array< std::array< int, V >, V > &mat, int i, int j, int no, int n) |
|
template<size_t V> |
void | printMat (const std::array< std::array< int, V >, V > &mat, int n) |
|
template<size_t V> |
bool | solveSudoku (std::array< std::array< int, V >, V > &mat, int i, int j) |
|
◆ graphColoring()
A recursive utility function to solve m coloring problem
- Template Parameters
-
V | number of vertices in the graph |
- Parameters
-
| graph | matrix of graph nonnectivity |
| m | number of colors |
[in,out] | color | description // used in,out to notify in documentation that this parameter gets modified by the function |
| v | index of graph vertex to check |
73 backtracking::printSolution<V>(color);
78 for (
int c = 1; c <= m; c++) {
80 if (backtracking::isSafe<V>(v,
graph, color, c)) {
84 backtracking::graphColoring<V>(
graph, m, color, v + 1);
◆ isPossible()
template<size_t V>
bool backtracking::isPossible |
( |
const std::array< std::array< int, V >, V > & |
mat, |
|
|
int |
i, |
|
|
int |
j, |
|
|
int |
no, |
|
|
int |
n |
|
) |
| |
Checks if it's possible to place a 'no'
- Template Parameters
-
V | number of vertices in the array |
- Parameters
-
mat | matrix where numbers are saved |
i | current index in rows |
j | current index in columns |
no | number to be added in matrix |
n | number of times loop will run |
- Returns
true
if 'mat' is different from 'no'
-
false
if 'mat' equals to 'no'
Row or col nahin hona chahiye
Subgrid mein nahi hona chahiye
38 for (
int x = 0; x < n; x++) {
39 if (mat[x][j] == no || mat[i][x] == no) {
48 for (
int x = sx; x < sx + 3; x++) {
49 for (
int y = sy; y < sy + 3; y++) {
50 if (mat[x][y] == no) {
◆ isSafe()
A utility function to check if the current color assignment is safe for vertex v
- Template Parameters
-
V | number of vertices in the graph |
- Parameters
-
v | index of graph vertex to check |
graph | matrix of graph nonnectivity |
color | vector of colors assigned to the graph nodes/vertices |
c | color value to check for the node v |
- Returns
true
if the color is safe to be assigned to the node
-
false
if the color is not safe to be assigned to the node
52 for (
int i = 0; i < V; i++) {
53 if (
graph[v][i] && c == color[i]) {
◆ issafe()
A utility function to check if i,j are valid indexes for N*N chessboard
- Template Parameters
-
V | number of vertices in array |
- Parameters
-
x | current index in rows |
y | current index in columns |
sol | matrix where numbers are saved |
- Returns
true
if ....
-
false
if ....
34 return (x < V && x >= 0 && y < V && y >= 0 && sol[x][y] == -1);
◆ minimax()
template<size_t T>
int backtracking::minimax |
( |
int |
depth, |
|
|
int |
node_index, |
|
|
bool |
is_max, |
|
|
const std::array< int, T > & |
scores, |
|
|
double |
height |
|
) |
| |
Check which number is the maximum/minimum in the array
- Parameters
-
depth | current depth in game tree |
node_index | current index in array |
is_max | if current index is the longest number |
scores | saved numbers in array |
height | maximum height for game tree |
- Returns
- maximum or minimum number
41 return scores[node_index];
44 int v1 =
minimax(depth + 1, node_index * 2, !is_max, scores,
height);
45 int v2 =
minimax(depth + 1, node_index * 2 + 1, !is_max, scores,
height);
◆ printMat()
Utility function to print matrix
- Template Parameters
-
V | number of vertices in array |
- Parameters
-
mat | matrix where numbers are saved |
n | number of times loop will run |
- Returns
- void
67 for (
int i = 0; i < n; i++) {
68 for (
int j = 0; j < n; j++) {
70 if ((j + 1) % 3 == 0) {
74 if ((i + 1) % 3 == 0) {
◆ printSolution()
template<size_t V>
void backtracking::printSolution |
( |
const std::array< int, V > & |
color | ) |
|
A utility function to print solution
- Template Parameters
-
V | number of vertices in the graph |
- Parameters
-
color | array of colors assigned to the nodes |
33 std::cout <<
"Following are the assigned colors\n";
34 for (
auto &col : color) {
◆ solve()
Knight's tour algorithm
- Template Parameters
-
V | number of vertices in array |
- Parameters
-
x | current index in rows |
y | current index in columns |
mov | movement to be done |
sol | matrix where numbers are saved |
xmov | next move of knight (x coordinate) |
ymov | next move of knight (y coordinate) |
- Returns
true
if solution exists
-
false
if solution does not exist
58 for (k = 0; k < V; k++) {
62 if (backtracking::issafe<V>(xnext, ynext, sol)) {
63 sol[xnext][ynext] =
mov;
65 if (backtracking::solve<V>(xnext, ynext,
mov + 1, sol, xmov, ymov) ==
true) {
69 sol[xnext][ynext] = -1;
◆ solveSudoku()
Sudoku algorithm
- Template Parameters
-
V | number of vertices in array |
- Parameters
-
mat | matrix where numbers are saved |
i | current index in rows |
j | current index in columns |
- Returns
true
if 'no' was placed
-
false
if 'no' was not placed
Base Case
Solve kr chuke hain for 9 rows already
Crossed the last Cell in the row
Blue Cell - Skip
White Cell Try to place every possible no
Place the no - assuming solution aa jayega
Nahin solve hui loop will place the next no.
Sare no try kr liey, kisi se bhi solve nahi hui
95 backtracking::printMat<V>(mat, 9);
101 return backtracking::solveSudoku<V>(mat, i + 1, 0);
105 if (mat[i][j] != 0) {
106 return backtracking::solveSudoku<V>(mat, i, j + 1);
110 for (
int no = 1; no <= 9; no++) {
111 if (backtracking::isPossible<V>(mat, i, j, no, 9)) {
114 bool aageKiSolveHui = backtracking::solveSudoku<V>(mat, i, j + 1);
115 if (aageKiSolveHui) {