Merge branch 'master' into fixgraph

ShuN6211 · Aug 14, 2020 · efbcaf2 · efbcaf2
2 parents ed5213e + bae4b4c
commit efbcaf2
Show file tree

Hide file tree

Showing 3 changed files with 126 additions and 52 deletions.
diff --git a/CMakeLists.txt b/CMakeLists.txt
@@ -18,7 +18,7 @@ endif(MSVC)
 
 option(USE_OPENMP "flag to use OpenMP for multithreading" ON)
 if(USE_OPENMP)
-    find_package(OpenMP)
+    find_package(OpenMP 3.0 COMPONENTS CXX)
     if (OpenMP_CXX_FOUND)
         message(STATUS "Building with OpenMP Multithreading.")
     else()
@@ -58,6 +58,7 @@ if(DOXYGEN_FOUND)
     set(DOXYGEN_STRIP_CODE_COMMENTS NO)
     set(DOXYGEN_EXT_LINKS_IN_WINDOW YES)
     set(DOXYGEN_BUILTIN_STL_SUPPORT YES)
+    set(DOXYGEN_EXCLUDE_PATTERNS */build/*)
     set(DOXYGEN_ENABLE_PREPROCESSING YES)
     set(DOXYGEN_CLANG_ASSISTED_PARSING YES)
     set(DOXYGEN_FILE_PATTERNS *.cpp *.h *.hpp *.md)

diff --git a/backtracking/n_queens.cpp b/backtracking/n_queens.cpp
@@ -1,63 +1,129 @@
+/**
+ * @file
+ * @brief [Eight Queens](https://en.wikipedia.org/wiki/Eight_queens_puzzle)
+ * puzzle
+ *
+ * @details
+ * The **eight queens puzzle** is the problem of placing eight chess queens on
+ * an 8×8 chessboard so that no two queens threaten each other; thus, a solution
+ * requires that no two queens share the same row, column, or diagonal. The
+ * eight queens puzzle is an example of the more general **n queens problem** of
+ * placing n non-attacking queens on an n×n chessboard, for which solutions
+ * exist for all natural numbers n with the exception of n = 2 and n = 3.
+ *
+ * @author Unknown author
+ * @author [David Leal](https://github.com/Panquesito7)
+ *
+ */
 #include <iostream>
-#define N 4
-using namespace std;
-
-void printSolution(int board[N][N]) {
-    cout << "\n";
-    for (int i = 0; i < N; i++) {
-        for (int j = 0; j < N; j++) cout << "" << board[i][j];
-        cout << "\n";
-    }
-}
-
-bool isSafe(int board[N][N], int row, int col) {
-    int i, j;
+#include <array>
 
-    /* Check this row on left side */
-    for (i = 0; i < col; i++)
-        if (board[row][i])
-            return false;
+/**
+ * @namespace backtracking
+ * @brief Backtracking algorithms
+ */
+namespace backtracking {
+  /**
+   * @namespace n_queens
+   * @brief Functions for [Eight Queens](https://en.wikipedia.org/wiki/Eight_queens_puzzle) puzzle.
+   */
+  namespace n_queens {
+    /**
+    * Utility function to print matrix
+    * @tparam n number of matrix size
+    * @param board matrix where numbers are saved
+    */
+    template <size_t n>
+    void printSolution(const std::array<std::array<int, n>, n> &board) {
+      std::cout << "\n";
+      for (int i = 0; i < n; i++) {
+        for (int j = 0; j < n; j++) {
+          std::cout << "" << board[i][j] << " ";
+        }
+        std::cout << "\n";
+      }
+    }
 
-    /* Check upper diagonal on left side */
-    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
-        if (board[i][j])
-            return false;
+    /**
+    * Check if a queen can be placed on matrix
+    * @tparam n number of matrix size
+    * @param board matrix where numbers are saved
+    * @param row current index in rows
+    * @param col current index in columns
+    * @returns `true` if queen can be placed on matrix
+    * @returns `false` if queen can't be placed on matrix
+    */
+    template <size_t n>
+    bool isSafe(const std::array<std::array<int, n>, n> &board, const int &row,
+                const int &col) {
+      int i = 0, j = 0;
 
-    /* Check lower diagonal on left side */
-    for (i = row, j = col; j >= 0 && i < N; i++, j--)
-        if (board[i][j])
-            return false;
+      // Check this row on left side
+      for (i = 0; i < col; i++) {
+        if (board[row][i]) {
+          return false;
+        }
+      }
 
-    return true;
-}
+      // Check upper diagonal on left side
+      for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
+        if (board[i][j]) {
+          return false;
+        }
+      }
+      // Check lower diagonal on left side
+      for (i = row, j = col; j >= 0 && i < n; i++, j--) {
+        if (board[i][j]) {
+          return false;
+        }
+      }
+      return true;
+    }
 
-void solveNQ(int board[N][N], int col) {
-    if (col >= N) {
-        printSolution(board);
+    /**
+    * Solve n queens problem
+    * @tparam n number of matrix size
+    * @param board matrix where numbers are saved
+    * @param col current index in columns
+    */
+    template <size_t n>
+    void solveNQ(std::array<std::array<int, n>, n> board, const int &col) {
+      if (col >= n) {
+        printSolution<n>(board);
         return;
-    }
+      }
 
-    /* Consider this column and try placing
-       this queen in all rows one by one */
-    for (int i = 0; i < N; i++) {
-        /* Check if queen can be placed on
-          board[i][col] */
-        if (isSafe(board, i, col)) {
-            /* Place this queen in board[i][col] */
-            //            cout<<"\n"<<col<<"can place"<<i;
-            board[i][col] = 1;
+      // Consider this column and try placing
+      // this queen in all rows one by one
+      for (int i = 0; i < n; i++) {
+        // Check if queen can be placed
+        // on board[i][col]
+        if (isSafe<n>(board, i, col)) {
+          // Place this queen in matrix
+          board[i][col] = 1;
 
-            /* recur to place rest of the queens */
-            solveNQ(board, col + 1);
+          // Recursive to place rest of the queens
+          solveNQ<n>(board, col + 1);
 
-            board[i][col] = 0;  // BACKTRACK
+          board[i][col] = 0; // backtrack
         }
+      }
     }
-}
+  } // namespace n_queens
+} // namespace backtracking
 
+/**
+ * Main function
+ */
 int main() {
-    int board[N][N] = {{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}};
+  const int n = 4;
+  std::array<std::array<int, n>, n> board = {
+    std::array<int, n>({0, 0, 0, 0}),
+    std::array<int, n>({0, 0, 0, 0}),
+    std::array<int, n>({0, 0, 0, 0}),
+    std::array<int, n>({0, 0, 0, 0})
+    };
 
-    solveNQ(board, 0);
-    return 0;
+  backtracking::n_queens::solveNQ<n>(board, 0);
+  return 0;
 }
diff --git a/graph/lowest_common_ancestor.cpp b/graph/lowest_common_ancestor.cpp
@@ -40,6 +40,11 @@
 #include <queue>
 #include <cassert>
 
+/**
+ * \namespace graph
+ * \brief Graph algorithms
+ */
+namespace graph {
 /**
  * Class for representing a graph as an adjacency list.
  * Its vertices are indexed 0, 1, ..., N - 1.
@@ -220,11 +225,13 @@ class LowestCommonAncestor {
     }
 };
 
+}  // namespace graph
+
 /**
  * Unit tests
- * @rerturns none
+ * @returns none
  */
-void tests() {
+static void tests() {
     /**
      *             _  3  _
      *          /     |     \
@@ -237,8 +244,8 @@ void tests() {
     std::vector< std::pair<int, int> > edges = {
       {7, 1}, {1, 5}, {1, 3}, {3, 6}, {6, 2}, {2, 9}, {6, 8}, {4, 3}, {0, 4}
     };
-    RootedTree t(edges, 3);
-    LowestCommonAncestor lca(t);
+    graph::RootedTree t(edges, 3);
+    graph::LowestCommonAncestor lca(t);
     assert(lca.lowest_common_ancestor(7, 4) == 3);
     assert(lca.lowest_common_ancestor(9, 6) == 6);
     assert(lca.lowest_common_ancestor(0, 0) == 0);