Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
backtracking Namespace Reference

Backtracking algorithms. More...

Functions

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)
 

Detailed Description

Backtracking algorithms.

Function Documentation

◆ graphColoring()

template<size_t V>
void backtracking::graphColoring ( const std::array< std::array< int, V >, V > &  graph,
int  m,
std::array< int, V >  color,
int  v 
)

A recursive utility function to solve m coloring problem

Template Parameters
Vnumber of vertices in the graph
Parameters
graphmatrix of graph nonnectivity
mnumber of colors
[in,out]colordescription // used in,out to notify in documentation that this parameter gets modified by the function
vindex of graph vertex to check
69  {
70  // base case:
71  // If all vertices are assigned a color then return true
72  if (v == V) {
73  backtracking::printSolution<V>(color);
74  return;
75  }
76 
77  // Consider this vertex v and try different colors
78  for (int c = 1; c <= m; c++) {
79  // Check if assignment of color c to v is fine
80  if (backtracking::isSafe<V>(v, graph, color, c)) {
81  color[v] = c;
82 
83  // recur to assign colors to rest of the vertices
84  backtracking::graphColoring<V>(graph, m, color, v + 1);
85 
86  // If assigning color c doesn't lead to a solution then remove it
87  color[v] = 0;
88  }
89  }
90  }

◆ 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
Vnumber of vertices in the array
Parameters
matmatrix where numbers are saved
icurrent index in rows
jcurrent index in columns
nonumber to be added in matrix
nnumber 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

36  {
37  /// Row or col nahin hona chahiye
38  for (int x = 0; x < n; x++) {
39  if (mat[x][j] == no || mat[i][x] == no) {
40  return false;
41  }
42  }
43 
44  /// Subgrid mein nahi hona chahiye
45  int sx = (i / 3) * 3;
46  int sy = (j / 3) * 3;
47 
48  for (int x = sx; x < sx + 3; x++) {
49  for (int y = sy; y < sy + 3; y++) {
50  if (mat[x][y] == no) {
51  return false;
52  }
53  }
54  }
55 
56  return true;
57  }

◆ isSafe()

template<size_t V>
bool backtracking::isSafe ( int  v,
const std::array< std::array< int, V >, V > &  graph,
const std::array< int, V > &  color,
int  c 
)

A utility function to check if the current color assignment is safe for vertex v

Template Parameters
Vnumber of vertices in the graph
Parameters
vindex of graph vertex to check
graphmatrix of graph nonnectivity
colorvector of colors assigned to the graph nodes/vertices
ccolor 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
51  {
52  for (int i = 0; i < V; i++) {
53  if (graph[v][i] && c == color[i]) {
54  return false;
55  }
56  }
57  return true;
58  }

◆ issafe()

template<size_t V>
bool backtracking::issafe ( int  x,
int  y,
const std::array< std::array< int, V >, V > &  sol 
)

A utility function to check if i,j are valid indexes for N*N chessboard

Template Parameters
Vnumber of vertices in array
Parameters
xcurrent index in rows
ycurrent index in columns
solmatrix where numbers are saved
Returns
true if ....
false if ....
33  {
34  return (x < V && x >= 0 && y < V && y >= 0 && sol[x][y] == -1);
35  }

◆ 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
depthcurrent depth in game tree
node_indexcurrent index in array
is_maxif current index is the longest number
scoressaved numbers in array
heightmaximum height for game tree
Returns
maximum or minimum number
39  {
40  if (depth == height) {
41  return scores[node_index];
42  }
43 
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);
46 
47  return is_max ? std::max(v1, v2) : std::min(v1, v2);
48 }
Here is the call graph for this function:

◆ printMat()

template<size_t V>
void backtracking::printMat ( const std::array< std::array< int, V >, V > &  mat,
int  n 
)

Utility function to print matrix

Template Parameters
Vnumber of vertices in array
Parameters
matmatrix where numbers are saved
nnumber of times loop will run
Returns
void
66  {
67  for (int i = 0; i < n; i++) {
68  for (int j = 0; j < n; j++) {
69  std::cout << mat[i][j] << " ";
70  if ((j + 1) % 3 == 0) {
71  std::cout << '\t';
72  }
73  }
74  if ((i + 1) % 3 == 0) {
76  }
78  }
79  }
Here is the call graph for this function:

◆ printSolution()

template<size_t V>
void backtracking::printSolution ( const std::array< int, V > &  color)

A utility function to print solution

Template Parameters
Vnumber of vertices in the graph
Parameters
colorarray of colors assigned to the nodes
32  {
33  std::cout << "Following are the assigned colors\n";
34  for (auto &col : color) {
35  std::cout << col;
36  }
37  std::cout << "\n";
38  }

◆ solve()

template<size_t V>
bool backtracking::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 
)

Knight's tour algorithm

Template Parameters
Vnumber of vertices in array
Parameters
xcurrent index in rows
ycurrent index in columns
movmovement to be done
solmatrix where numbers are saved
xmovnext move of knight (x coordinate)
ymovnext move of knight (y coordinate)
Returns
true if solution exists
false if solution does not exist
51  {
52  int k, xnext, ynext;
53 
54  if (mov == V * V) {
55  return true;
56  }
57 
58  for (k = 0; k < V; k++) {
59  xnext = x + xmov[k];
60  ynext = y + ymov[k];
61 
62  if (backtracking::issafe<V>(xnext, ynext, sol)) {
63  sol[xnext][ynext] = mov;
64 
65  if (backtracking::solve<V>(xnext, ynext, mov + 1, sol, xmov, ymov) == true) {
66  return true;
67  }
68  else {
69  sol[xnext][ynext] = -1;
70  }
71  }
72  }
73  return false;
74  }
Here is the call graph for this function:

◆ solveSudoku()

template<size_t V>
bool backtracking::solveSudoku ( std::array< std::array< int, V >, V > &  mat,
int  i,
int  j 
)

Sudoku algorithm

Template Parameters
Vnumber of vertices in array
Parameters
matmatrix where numbers are saved
icurrent index in rows
jcurrent 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

91  {
92  /// Base Case
93  if (i == 9) {
94  /// Solve kr chuke hain for 9 rows already
95  backtracking::printMat<V>(mat, 9);
96  return true;
97  }
98 
99  /// Crossed the last Cell in the row
100  if (j == 9) {
101  return backtracking::solveSudoku<V>(mat, i + 1, 0);
102  }
103 
104  /// Blue Cell - Skip
105  if (mat[i][j] != 0) {
106  return backtracking::solveSudoku<V>(mat, i, j + 1);
107  }
108  /// White Cell
109  /// Try to place every possible no
110  for (int no = 1; no <= 9; no++) {
111  if (backtracking::isPossible<V>(mat, i, j, no, 9)) {
112  /// Place the no - assuming solution aa jayega
113  mat[i][j] = no;
114  bool aageKiSolveHui = backtracking::solveSudoku<V>(mat, i, j + 1);
115  if (aageKiSolveHui) {
116  return true;
117  }
118  /// Nahin solve hui
119  /// loop will place the next no.
120  }
121  }
122  /// Sare no try kr liey, kisi se bhi solve nahi hui
123  mat[i][j] = 0;
124  return false;
125  }
mov
void mov(tower *From, tower *To)
Definition: tower_of_hanoi.cpp:39
std::cout
height
int height(node *root)
Definition: avltree.cpp:31
std::min
T min(T... args)
backtracking::minimax
int minimax(int depth, int node_index, bool is_max, const std::array< int, T > &scores, double height)
Definition: minimax.cpp:38
std::endl
T endl(T... args)
std
STL namespace.
graph
Graph algorithms.
std::max
T max(T... args)