Repository: TheAlgorithms/Java
Pull request #5591 (2024-10-06 04:39:45)

Add tests, enhance class & function documentation for `KnightsTour.jav…
Also removed `print` and `main` methods.

<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5591?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `50.00000%` with `6 lines` in your changes missing coverage. Please review.
> Project coverage is 54.76%. Comparing base [(`f34fe4d`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/f34fe4d8408ac35cef900cfae022ffadfc007ea3?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`e28136e`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/e28136ed2d758dbefdb06caf75b5080c044ca15c?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5591?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...va/com/thealgorithms/backtracking/KnightsTour.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5591?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fbacktracking%2FKnightsTour.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9iYWNrdHJhY2tpbmcvS25pZ2h0c1RvdXIuamF2YQ==) | 50.00% | [3 Missing and 3 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5591?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5591      +/-   ##
============================================
+ Coverage     54.56%   54.76%   +0.20%     
- Complexity     3413     3426      +13     
============================================
  Files           535      535              
  Lines         15383    15372      -11     
  Branches       2935     2931       -4     
============================================
+ Hits           8393     8418      +25     
+ Misses         6637     6594      -43     
- Partials        353      360       +7     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5591?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 0d34492f..23544efb 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -607,6 +607,7 @@
             * [ArrayCombinationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/ArrayCombinationTest.java)
             * [CombinationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/CombinationTest.java)
             * [FloodFillTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/FloodFillTest.java)
+            * [KnightsTourTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/KnightsTourTest.java)
             * [MazeRecursionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/MazeRecursionTest.java)
             * [MColoringTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/MColoringTest.java)
             * [NQueensTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/backtracking/NQueensTest.java)
diff --git a/src/main/java/com/thealgorithms/backtracking/KnightsTour.java b/src/main/java/com/thealgorithms/backtracking/KnightsTour.java
index 2287b39d..2c2da659 100644
--- a/src/main/java/com/thealgorithms/backtracking/KnightsTour.java
+++ b/src/main/java/com/thealgorithms/backtracking/KnightsTour.java
@@ -4,33 +4,26 @@ import java.util.ArrayList;
 import java.util.Comparator;
 import java.util.List;
 
-/*
-    * Problem Statement: -
-
-    Given a N*N board with the Knight placed on the first block of an empty board. Moving according
-   to the rules of chess knight must visit each square exactly once. Print the order of each cell in
-   which they are visited.
-
-    Example: -
-
-    Input : N = 8
-
-    Output:
-        0  59  38  33  30  17   8  63
-        37  34  31  60   9  62  29  16
-        58   1  36  39  32  27  18   7
-        35  48  41  26  61  10  15  28
-        42  57   2  49  40  23   6  19
-        47  50  45  54  25  20  11  14
-        56  43  52   3  22  13  24   5
-        51  46  55  44  53   4  21  12
-
+/**
+ * The KnightsTour class solves the Knight's Tour problem using backtracking.
+ *
+ * Problem Statement:
+ * Given an N*N board with a knight placed on the first block, the knight must
+ * move according to chess rules and visit each square on the board exactly once.
+ * The class outputs the sequence of moves for the knight.
+ *
+ * Example:
+ * Input: N = 8 (8x8 chess board)
+ * Output: The sequence of numbers representing the order in which the knight visits each square.
  */
 public final class KnightsTour {
     private KnightsTour() {
     }
 
+    // The size of the chess board (12x12 grid, with 2 extra rows/columns as a buffer around a 8x8 area)
     private static final int BASE = 12;
+
+    // Possible moves for a knight in chess
     private static final int[][] MOVES = {
         {1, -2},
         {2, -1},
@@ -40,36 +33,40 @@ public final class KnightsTour {
         {-2, 1},
         {-2, -1},
         {-1, -2},
-    }; // Possible moves by knight on chess
-    private static int[][] grid; // chess grid
-    private static int total; // total squares in chess
+    };
+
+    // Chess grid representing the board
+    static int[][] grid;
+
+    // Total number of cells the knight needs to visit
+    static int total;
 
-    public static void main(String[] args) {
+    /**
+     * Resets the chess board to its initial state.
+     * Initializes the grid with boundary cells marked as -1 and internal cells as 0.
+     * Sets the total number of cells the knight needs to visit.
+     */
+    public static void resetBoard() {
         grid = new int[BASE][BASE];
         total = (BASE - 4) * (BASE - 4);
-
         for (int r = 0; r < BASE; r++) {
             for (int c = 0; c < BASE; c++) {
                 if (r < 2 || r > BASE - 3 || c < 2 || c > BASE - 3) {
-                    grid[r][c] = -1;
+                    grid[r][c] = -1; // Mark boundary cells
                 }
             }
         }
-
-        int row = 2 + (int) (Math.random() * (BASE - 4));
-        int col = 2 + (int) (Math.random() * (BASE - 4));
-
-        grid[row][col] = 1;
-
-        if (solve(row, col, 2)) {
-            printResult();
-        } else {
-            System.out.println("no result");
-        }
     }
 
-    // Return True when solvable
-    private static boolean solve(int row, int column, int count) {
+    /**
+     * Recursive method to solve the Knight's Tour problem.
+     *
+     * @param row   The current row of the knight
+     * @param column The current column of the knight
+     * @param count  The current move number
+     * @return True if a solution is found, False otherwise
+     */
+    static boolean solve(int row, int column, int count) {
         if (count > total) {
             return true;
         }
@@ -80,29 +77,37 @@ public final class KnightsTour {
             return false;
         }
 
+        // Sort neighbors by Warnsdorff's rule (fewest onward moves)
         neighbor.sort(Comparator.comparingInt(a -> a[2]));
 
         for (int[] nb : neighbor) {
-            row = nb[0];
-            column = nb[1];
-            grid[row][column] = count;
-            if (!orphanDetected(count, row, column) && solve(row, column, count + 1)) {
+            int nextRow = nb[0];
+            int nextCol = nb[1];
+            grid[nextRow][nextCol] = count;
+            if (!orphanDetected(count, nextRow, nextCol) && solve(nextRow, nextCol, count + 1)) {
                 return true;
             }
-            grid[row][column] = 0;
+            grid[nextRow][nextCol] = 0; // Backtrack
         }
 
         return false;
     }
 
-    // Returns List of neighbours
-    private static List<int[]> neighbors(int row, int column) {
+    /**
+     * Returns a list of valid neighboring cells where the knight can move.
+     *
+     * @param row   The current row of the knight
+     * @param column The current column of the knight
+     * @return A list of arrays representing valid moves, where each array contains:
+     *         {nextRow, nextCol, numberOfPossibleNextMoves}
+     */
+    static List<int[]> neighbors(int row, int column) {
         List<int[]> neighbour = new ArrayList<>();
 
         for (int[] m : MOVES) {
             int x = m[0];
             int y = m[1];
-            if (grid[row + y][column + x] == 0) {
+            if (row + y >= 0 && row + y < BASE && column + x >= 0 && column + x < BASE && grid[row + y][column + x] == 0) {
                 int num = countNeighbors(row + y, column + x);
                 neighbour.add(new int[] {row + y, column + x, num});
             }
@@ -110,19 +115,34 @@ public final class KnightsTour {
         return neighbour;
     }
 
-    // Returns the total count of neighbors
-    private static int countNeighbors(int row, int column) {
+    /**
+     * Counts the number of possible valid moves for a knight from a given position.
+     *
+     * @param row    The row of the current position
+     * @param column The column of the current position
+     * @return The number of valid neighboring moves
+     */
+    static int countNeighbors(int row, int column) {
         int num = 0;
         for (int[] m : MOVES) {
-            if (grid[row + m[1]][column + m[0]] == 0) {
+            int x = m[0];
+            int y = m[1];
+            if (row + y >= 0 && row + y < BASE && column + x >= 0 && column + x < BASE && grid[row + y][column + x] == 0) {
                 num++;
             }
         }
         return num;
     }
 
-    // Returns true if it is orphan
-    private static boolean orphanDetected(int count, int row, int column) {
+    /**
+     * Detects if moving to a given position will create an orphan (a position with no further valid moves).
+     *
+     * @param count   The current move number
+     * @param row     The row of the current position
+     * @param column  The column of the current position
+     * @return True if an orphan is detected, False otherwise
+     */
+    static boolean orphanDetected(int count, int row, int column) {
         if (count < total - 1) {
             List<int[]> neighbor = neighbors(row, column);
             for (int[] nb : neighbor) {
@@ -133,17 +153,4 @@ public final class KnightsTour {
         }
         return false;
     }
-
-    // Prints the result grid
-    private static void printResult() {
-        for (int[] row : grid) {
-            for (int i : row) {
-                if (i == -1) {
-                    continue;
-                }
-                System.out.printf("%2d ", i);
-            }
-            System.out.println();
-        }
-    }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/backtracking/KnightsTourTest.java b/src/test/java/com/thealgorithms/backtracking/KnightsTourTest.java
new file mode 100644
index 00000000..306dbf4c
--- /dev/null
+++ b/src/test/java/com/thealgorithms/backtracking/KnightsTourTest.java
@@ -0,0 +1,59 @@
+package com.thealgorithms.backtracking;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import java.util.List;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+public class KnightsTourTest {
+
+    @BeforeEach
+    void setUp() {
+        // Call the reset method in the KnightsTour class
+        KnightsTour.resetBoard();
+    }
+
+    @Test
+    void testGridInitialization() {
+        for (int r = 0; r < 12; r++) {
+            for (int c = 0; c < 12; c++) {
+                if (r < 2 || r > 12 - 3 || c < 2 || c > 12 - 3) {
+                    assertEquals(-1, KnightsTour.grid[r][c], "Border cells should be -1");
+                } else {
+                    assertEquals(0, KnightsTour.grid[r][c], "Internal cells should be 0");
+                }
+            }
+        }
+    }
+
+    @Test
+    void testCountNeighbors() {
+        // Manually place a knight at (3, 3) and mark nearby cells to test counting
+        KnightsTour.grid[3][3] = 1; // Knight is here
+        KnightsTour.grid[5][4] = -1; // Block one potential move
+
+        int neighborCount = KnightsTour.countNeighbors(3, 3);
+        assertEquals(3, neighborCount, "Knight at (3, 3) should have 3 neighbors (one blocked)");
+
+        KnightsTour.grid[4][1] = -1; // Block another move
+        neighborCount = KnightsTour.countNeighbors(3, 3);
+        assertEquals(3, neighborCount, "Knight at (3, 3) should have 3 neighbors (two blocked)");
+    }
+
+    @Test
+    void testNeighbors() {
+        // Test the list of valid neighbors for a given cell (3, 3)
+        List<int[]> neighbors = KnightsTour.neighbors(3, 3);
+        assertEquals(4, neighbors.size(), "Knight at (3, 3) should have 8 valid neighbors");
+    }
+
+    @Test
+    void testSolveSuccessful() {
+        // Test if the solve method works for a successful knight's tour
+        KnightsTour.grid[2][2] = 1; // Start the knight at (2, 2)
+        boolean result = KnightsTour.solve(2, 2, 2);
+        assertTrue(result, "solve() should successfully complete a Knight's tour");
+    }
+}