[fix/docs]: Update backtracking folder (TheAlgorithms#916)

* [fix/docs]: Update backtracking/graph_coloring.cpp * Add CMakeLists.txt in backtracking folder * Add backtracking to CMakeLists.txt * fix: Fix build issues * docs: Various documentation fixes * fix: minimax.cpp issues * fix: sudoku_solve.cpp fixes * formatting source-code for 8ffbbb3 * make he code neat and clean without global variables * fix 2 stars in comment * fix MSVC errors by forcing template parameter in function calls Note: This is identical to passing it as a function parameter, and may not be helpful * Update minimax.cpp * docs: minimax.cpp improvements * docs: Add Wikipedia link in minimax.cpp * fix: minimax.cpp vector fix * docs: fix Wikipedia link in minimax.cpp * docs: fix return statement in minimax.cpp * fix: sudoku_solve.cpp fixes * fix: more sudoku_solve.cpp fixes * fix: sudoku_solve.cpp fixes * fix: sudoku_solve.cpp * formatting source-code for 13b5b9b * docs: update graph_coloring.cpp description * fix: use array instead of vector (minimax.cpp) * feat: add namespace (minimax.cpp) * docs: update namespace description (graph_coloring.cpp) * fix: graph_coloring.cpp * fix: sudoku_solve.cpp fixes * fix: graph_coloring.cpp * fix: minimax.cpp * fix: more sudoku_solve.cpp fixes * fix: more graph_coloring.cpp fixes * fix: graph_coloring.cpp fixes * fix: sudoku_solve.cpp fixes * fix: minimax.cpp * fix: sudoku_solve.cpp fixes * fix: too few template arguments (std::array) * fix: too few template arguments (std::array, minimax.cpp) * fix: narrowing conversion from double to int (minimax.cpp) * fix: excess elements in struct initializer (graph_coloring.cpp) * fix: no matching function (graph_coloring.cpp) * fix: graph_coloring.cpp issues/errors * fix: knight_tour.cpp issues/errors * fix: sudoku_solve.cpp issues/errors * [fix/docs]: Various fixes in graph_coloring.cpp * fix: More graph_coloring.cpp fixes * docs: Add initial comment block (sudoku_solve.cpp) * fix: Add return statement (knight_tour.cpp) * fix: array fixes (graph_coloring.cpp) * docs: documentation improvements (sudoku_solve.cpp) * docs: documentation improvements (knight_tour.cpp) * docs: documentation improvements (sudoku_solve.cpp) * docs: documentation improvements (graph_coloring.cpp) * docs: Documentation improvements (graph_coloring.cpp) Thanks, @kvedala! * docs: Documentation improvements (sudoku_solve.cpp) * docs: Document function parameter (sudoku_solve.cpp) * docs: Documentation improvements (knight_tour.cpp) * docs: Add long description (graph_coloring.cpp) * docs: Add long description (minimax.cpp) * docs: Add long description (sudoku_solve.cpp) * docs: Documentation improvements (knight_tour.cpp) * docs: Documentation improvements (sudoku_solve.cpp) * docs: Documentation improvements (minimax.cpp) * docs: More documentation improvements (minimax.cpp) * docs: Documentation improvements (sudoku_solve.cpp) * fix: sudoku_solve.cpp improvements Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com> Co-authored-by: Krishna Vedala <7001608+kvedala@users.noreply.github.com>
ShuN6211 · Aug 7, 2020 · 25b39a3 · 25b39a3
1 parent b36ce9a
commit 25b39a3
Show file tree

Hide file tree

Showing 6 changed files with 381 additions and 179 deletions.
diff --git a/CMakeLists.txt b/CMakeLists.txt
@@ -36,6 +36,7 @@ add_subdirectory(sorting)
 add_subdirectory(geometry)
 add_subdirectory(graphics)
 add_subdirectory(probability)
+add_subdirectory(backtracking)
 add_subdirectory(data_structures)
 add_subdirectory(machine_learning)
 add_subdirectory(numerical_methods)

diff --git a/backtracking/CMakeLists.txt b/backtracking/CMakeLists.txt
@@ -0,0 +1,18 @@
+# If necessary, use the RELATIVE flag, otherwise each source file may be listed
+# with full pathname. RELATIVE may makes it easier to extract an executable name
+# automatically.
+file( GLOB APP_SOURCES RELATIVE ${CMAKE_CURRENT_SOURCE_DIR} *.cpp )
+# file( GLOB APP_SOURCES ${CMAKE_SOURCE_DIR}/*.c )
+# AUX_SOURCE_DIRECTORY(${CMAKE_CURRENT_SOURCE_DIR} APP_SOURCES)
+foreach( testsourcefile ${APP_SOURCES} )
+    # I used a simple string replace, to cut off .cpp.
+    string( REPLACE ".cpp" "" testname ${testsourcefile} )
+    add_executable( ${testname} ${testsourcefile} )
+
+    set_target_properties(${testname} PROPERTIES LINKER_LANGUAGE CXX)
+    if(OpenMP_CXX_FOUND)
+        target_link_libraries(${testname} OpenMP::OpenMP_CXX)
+    endif()
+    install(TARGETS ${testname} DESTINATION "bin/backtracking")
+
+endforeach( testsourcefile ${APP_SOURCES} )
diff --git a/backtracking/graph_coloring.cpp b/backtracking/graph_coloring.cpp
@@ -1,72 +1,117 @@
-#include <stdio.h>
+/**
+ * @file
+ * @brief prints the assigned colors
+ * using [Graph Coloring](https://en.wikipedia.org/wiki/Graph_coloring) algorithm
+ *
+ * @details
+ * In graph theory, graph coloring is a special case of graph labeling; 
+ * it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. 
+ * In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; 
+ * this is called a vertex coloring. Similarly, an edge coloring assigns
+ * a color to each edge so that no two adjacent edges are of the same color,
+ * and a face coloring of a planar graph assigns a color to each face or
+ * region so that no two faces that share a boundary have the same color.
+ *
+ * @author [Anup Kumar Panwar](https://github.com/AnupKumarPanwar)
+ * @author [David Leal](https://github.com/Panquesito7)
+ */
+#include <iostream>
+#include <array>
+#include <vector>
 
-// Number of vertices in the graph
-#define V 4
-
-void printSolution(int color[]);
-
-/* A utility function to check if the current color assignment
-   is safe for vertex v */
-bool isSafe(int v, bool graph[V][V], int color[], int c) {
-    for (int i = 0; i < V; i++)
-        if (graph[v][i] && c == color[i])
-            return false;
-    return true;
-}
+/**
+ * @namespace
+ * @brief Backtracking algorithms
+ */
+namespace backtracking {
+    /** A utility function to print solution
+     * @tparam V number of vertices in the graph
+     * @param color array of colors assigned to the nodes
+     */
+    template <size_t V>
+    void printSolution(const std::array <int, V>& color) {
+        std::cout << "Following are the assigned colors\n";
+        for (auto &col : color) {
+            std::cout << col;
+        }
+        std::cout << "\n";
+    }
 
-/* A recursive utility function to solve m coloring problem */
-void graphColoring(bool graph[V][V], int m, int color[], int v) {
-    /* base case: If all vertices are assigned a color then
-       return true */
-    if (v == V) {
-        printSolution(color);
-        return;
+    /** A utility function to check if the current color assignment is safe for
+     * vertex v
+     * @tparam V number of vertices in the graph
+     * @param v index of graph vertex to check
+     * @param graph matrix of graph nonnectivity
+     * @param color vector of colors assigned to the graph nodes/vertices
+     * @param c color value to check for the node `v`
+     * @returns `true` if the color is safe to be assigned to the node
+     * @returns `false` if the color is not safe to be assigned to the node
+     */
+    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) {
+        for (int i = 0; i < V; i++) {
+            if (graph[v][i] && c == color[i]) {
+                return false;
+            }
+        }
+        return true;
     }
 
-    /* Consider this vertex v and try different colors */
-    for (int c = 1; c <= m; c++) {
-        /* Check if assignment of color c to v is fine*/
-        if (isSafe(v, graph, color, c)) {
-            color[v] = c;
+    /** A recursive utility function to solve m coloring problem
+     * @tparam V number of vertices in the graph
+     * @param graph matrix of graph nonnectivity
+     * @param m number of colors
+     * @param [in,out] color description // used in,out to notify in documentation
+     * that this parameter gets modified by the function
+     * @param v index of graph vertex to check
+     */
+    template <size_t V>
+    void graphColoring(const std::array<std::array <int, V>, V>& graph, int m, std::array <int, V> color, int v) {
+        // base case:
+        // If all vertices are assigned a color then return true
+        if (v == V) {
+            backtracking::printSolution<V>(color);
+            return;
+        }
+
+        // Consider this vertex v and try different colors
+        for (int c = 1; c <= m; c++) {
+            // Check if assignment of color c to v is fine
+            if (backtracking::isSafe<V>(v, graph, color, c)) {
+                color[v] = c;
 
-            /* recur to assign colors to rest of the vertices */
-            graphColoring(graph, m, color, v + 1);
+                // recur to assign colors to rest of the vertices
+                backtracking::graphColoring<V>(graph, m, color, v + 1);
 
-            /* If assigning color c doesn't lead to a solution
-               then remove it */
-            color[v] = 0;
+                // If assigning color c doesn't lead to a solution then remove it
+                color[v] = 0;
+            }
         }
     }
-}
-
-/* A utility function to print solution */
-void printSolution(int color[]) {
-    printf(" Following are the assigned colors \n");
-    for (int i = 0; i < V; i++) printf(" %d ", color[i]);
-    printf("\n");
-}
+}  // namespace backtracking
 
-// driver program to test above function
+/**
+ * Main function
+ */
 int main() {
-    /* Create following graph and test whether it is 3 colorable
-      (3)---(2)
-       |   / |
-       |  /  |
-       | /   |
-      (0)---(1)
-    */
-    bool graph[V][V] = {
-        {0, 1, 1, 1},
-        {1, 0, 1, 0},
-        {1, 1, 0, 1},
-        {1, 0, 1, 0},
-    };
-    int m = 3;  // Number of colors
+    // Create following graph and test whether it is 3 colorable
+    // (3)---(2)
+    // |   / |
+    // |  /  |
+    // | /   |
+    // (0)---(1)
 
-    int color[V];
+    const int V = 4;  // number of vertices in the graph
+    std::array <std::array <int, V>, V> graph = {
+        std::array <int, V>({0, 1, 1, 1}),
+        std::array <int, V>({1, 0, 1, 0}),
+        std::array <int, V>({1, 1, 0, 1}),
+        std::array <int, V>({1, 0, 1, 0})
+    };
 
-    for (int i = 0; i < V; i++) color[i] = 0;
+    int m = 3;  // Number of colors
+    std::array <int, V> color{};
 
-    graphColoring(graph, m, color, 0);
+    backtracking::graphColoring<V>(graph, m, color, 0);
     return 0;
 }
diff --git a/backtracking/knight_tour.cpp b/backtracking/knight_tour.cpp
@@ -1,60 +1,105 @@
+/**
+ * @file
+ * @brief [Knight's tour](https://en.wikipedia.org/wiki/Knight%27s_tour) algorithm
+ *
+ * @details
+ * A knight's tour is a sequence of moves of a knight on a chessboard
+ * such that the knight visits every square only once. If the knight
+ * ends on a square that is one knight's move from the beginning
+ * square (so that it could tour the board again immediately, following
+ * the same path, the tour is closed; otherwise, it is open.
+ *
+ * @author [Nikhil Arora](https://github.com/nikhilarora068)
+ * @author [David Leal](https://github.com/Panquesito7)
+ */
 #include <iostream>
-#define n 8
+#include <array>
 
 /**
-A knight's tour is a sequence of moves of a knight on a chessboard
-such that the knight visits every square only once. If the knight
-ends on a square that is one knight's move from the beginning
-square (so that it could tour the board again immediately, following
-the same path), the tour is closed; otherwise, it is open.
-**/
-
-using std::cin;
-using std::cout;
-
-bool issafe(int x, int y, int sol[n][n]) {
-    return (x < n && x >= 0 && y < n && y >= 0 && sol[x][y] == -1);
-}
-bool solve(int x, int y, int mov, int sol[n][n], int xmov[n], int ymov[n]) {
-    int k, xnext, ynext;
+ * @namespace backtracking
+ * @brief Backtracking algorithms
+ */
+namespace backtracking {
+    /**
+     * A utility function to check if i,j are valid indexes for N*N chessboard
+     * @tparam V number of vertices in array
+     * @param x current index in rows
+     * @param y current index in columns
+     * @param sol matrix where numbers are saved
+     * @returns `true` if ....
+     * @returns `false` if ....
+     */
+    template <size_t V>
+    bool issafe(int x, int y, const std::array <std::array <int, V>, V>& sol) {
+        return (x < V && x >= 0 && y < V && y >= 0 && sol[x][y] == -1);
+    }
 
-    if (mov == n * n)
-        return true;
+    /**
+     * Knight's tour algorithm
+     * @tparam V number of vertices in array
+     * @param x current index in rows
+     * @param y current index in columns
+     * @param mov movement to be done
+     * @param sol matrix where numbers are saved
+     * @param xmov next move of knight (x coordinate)
+     * @param ymov next move of knight (y coordinate)
+     * @returns `true` if solution exists
+     * @returns `false` if solution does not exist
+     */
+    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) {
+        int k, xnext, ynext;
 
-    for (k = 0; k < 8; k++) {
-        xnext = x + xmov[k];
-        ynext = y + ymov[k];
+        if (mov == V * V) {
+            return true;
+        }
+
+        for (k = 0; k < V; k++) {
+            xnext = x + xmov[k];
+            ynext = y + ymov[k];
 
-        if (issafe(xnext, ynext, sol)) {
-            sol[xnext][ynext] = mov;
+            if (backtracking::issafe<V>(xnext, ynext, sol)) {
+                sol[xnext][ynext] = mov;
 
-            if (solve(xnext, ynext, mov + 1, sol, xmov, ymov) == true)
-                return true;
-            else
-                sol[xnext][ynext] = -1;
+                if (backtracking::solve<V>(xnext, ynext, mov + 1, sol, xmov, ymov) == true) {
+                    return true;
+                }
+                else {
+                    sol[xnext][ynext] = -1;
+                }
+            }
         }
+        return false;
     }
-    return false;
-}
+} // namespace backtracking
+
+/**
+ * Main function
+ */
 int main() {
-    // initialize();
+    const int n = 8;
+    std::array <std::array <int, n>, n> sol = { 0 };
 
-    int sol[n][n];
     int i, j;
-    for (i = 0; i < n; i++)
-        for (j = 0; j < n; j++) sol[i][j] = -1;
+    for (i = 0; i < n; i++) {
+        for (j = 0; j < n; j++) { sol[i][j] = -1; }
+    }
+
+    std::array <int, n> xmov = { 2, 1, -1, -2, -2, -1, 1, 2 };
+    std::array <int, n> ymov = { 1, 2, 2, 1, -1, -2, -2, -1 };
 
-    int xmov[8] = {2, 1, -1, -2, -2, -1, 1, 2};
-    int ymov[8] = {1, 2, 2, 1, -1, -2, -2, -1};
     sol[0][0] = 0;
 
-    bool flag = solve(0, 0, 1, sol, xmov, ymov);
-    if (flag == false)
-        cout << "solution doesnot exist \n";
+    bool flag = backtracking::solve<n>(0, 0, 1, sol, xmov, ymov);
+    if (flag == false) {
+        std::cout << "Error: Solution does not exist\n";
+    }
     else {
         for (i = 0; i < n; i++) {
-            for (j = 0; j < n; j++) cout << sol[i][j] << "  ";
-            cout << "\n";
+            for (j = 0; j < n; j++) { std::cout << sol[i][j] << "  "; }
+            std::cout << "\n";
         }
     }
+    return 0;
 }