Repository: TheAlgorithms/Java
Pull request #5746 (2024-10-13 03:10:49)

feat: Add TilingProblem new algorithm with Junit tests
<!--
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/5746?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 `64.00000%` with `9 lines` in your changes missing coverage. Please review.
> Project coverage is 63.92%. Comparing base [(`4a03f42`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/4a03f420616a6773e9a5cdc304b1681e96d945bd?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`00827c8`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/00827c86bc6f2b7f66672ac00fb5c45ff119af47?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/5746?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [.../thealgorithms/divideandconquer/TilingProblem.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5746?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdivideandconquer%2FTilingProblem.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kaXZpZGVhbmRjb25xdWVyL1RpbGluZ1Byb2JsZW0uamF2YQ==) | 64.00% | [5 Missing and 4 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5746?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    #5746      +/-   ##
============================================
+ Coverage     63.91%   63.92%   +0.01%     
- Complexity     4167     4172       +5     
============================================
  Files           582      583       +1     
  Lines         16302    16327      +25     
  Branches       3148     3152       +4     
============================================
+ Hits          10419    10437      +18     
- Misses         5457     5461       +4     
- Partials        426      429       +3     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5746?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 0b34e106..521961c1 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -255,6 +255,7 @@
             * [MedianOfTwoSortedArrays](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/MedianOfTwoSortedArrays.java)
             * [SkylineAlgorithm](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/SkylineAlgorithm.java)
             * [StrassenMatrixMultiplication](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/StrassenMatrixMultiplication.java)
+            * [TilingProblem](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/TilingProblem.java)
           * dynamicprogramming
             * [BoardPath](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/BoardPath.java)
             * [BoundaryFill](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/BoundaryFill.java)
@@ -838,6 +839,7 @@
             * [MedianOfTwoSortedArraysTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/MedianOfTwoSortedArraysTest.java)
             * [SkylineAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/SkylineAlgorithmTest.java)
             * [StrassenMatrixMultiplicationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/StrassenMatrixMultiplicationTest.java)
+            * [TilingProblemTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/TilingProblemTest.java)
           * dynamicprogramming
             * [BoardPathTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/BoardPathTest.java)
             * [BoundaryFillTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/BoundaryFillTest.java)
diff --git a/src/main/java/com/thealgorithms/divideandconquer/TilingProblem.java b/src/main/java/com/thealgorithms/divideandconquer/TilingProblem.java
new file mode 100644
index 00000000..ff2e1678
--- /dev/null
+++ b/src/main/java/com/thealgorithms/divideandconquer/TilingProblem.java
@@ -0,0 +1,99 @@
+package com.thealgorithms.divideandconquer;
+
+/**
+ * This class provides a solution to the Tiling Problem using divide-and-conquer.
+ * <p>
+ * The Tiling Problem involves filling a 2^n x 2^n board with a single missing
+ * square using L-shaped tiles (each tile covers exactly three squares).
+ * The algorithm recursively divides the board into four quadrants, places an
+ * L-shaped tile in the appropriate quadrant, and fills the remaining areas.
+ *
+ * <p>Applications:
+ * - Used in graphics and image processing.
+ * - Helpful in solving puzzles and tiling problems in competitive programming.
+ *
+ * @author Hardvan
+ */
+public final class TilingProblem {
+    private TilingProblem() {
+    }
+
+    /**
+     * A counter used to label the L-shaped tiles placed on the board.
+     */
+    private static int tile = 1;
+
+    /**
+     * A 2D array representing the board to be tiled.
+     */
+    private static int[][] board;
+
+    /**
+     * Solves the tiling problem for a 2^n x 2^n board with one missing square.
+     *
+     * @param size The size of the board (must be a power of 2).
+     * @param missingRow The row index of the missing square.
+     * @param missingCol The column index of the missing square.
+     * @return A 2D array representing the tiled board with L-shaped tiles.
+     */
+    public static int[][] solveTiling(int size, int missingRow, int missingCol) {
+        board = new int[size][size];
+        fillBoard(size, 0, 0, missingRow, missingCol);
+        return board;
+    }
+
+    /**
+     * Recursively fills the board with L-shaped tiles.
+     *
+     * <p>The board is divided into four quadrants. Depending on the location of
+     * the missing square, an L-shaped tile is placed at the center of the board
+     * to cover three of the four quadrants. The process is then repeated for
+     * each quadrant until the entire board is filled.
+     *
+     * @param size The current size of the sub-board.
+     * @param row The starting row index of the current sub-board.
+     * @param col The starting column index of the current sub-board.
+     * @param missingRow The row index of the missing square within the board.
+     * @param missingCol The column index of the missing square within the board.
+     */
+    private static void fillBoard(int size, int row, int col, int missingRow, int missingCol) {
+        if (size == 1) {
+            return;
+        }
+
+        int half = size / 2;
+        int t = tile++;
+
+        // Top-left quadrant
+        if (missingRow < row + half && missingCol < col + half) {
+            fillBoard(half, row, col, missingRow, missingCol);
+        } else {
+            board[row + half - 1][col + half - 1] = t;
+            fillBoard(half, row, col, row + half - 1, col + half - 1);
+        }
+
+        // Top-right quadrant
+        if (missingRow < row + half && missingCol >= col + half) {
+            fillBoard(half, row, col + half, missingRow, missingCol);
+        } else {
+            board[row + half - 1][col + half] = t;
+            fillBoard(half, row, col + half, row + half - 1, col + half);
+        }
+
+        // Bottom-left quadrant
+        if (missingRow >= row + half && missingCol < col + half) {
+            fillBoard(half, row + half, col, missingRow, missingCol);
+        } else {
+            board[row + half][col + half - 1] = t;
+            fillBoard(half, row + half, col, row + half, col + half - 1);
+        }
+
+        // Bottom-right quadrant
+        if (missingRow >= row + half && missingCol >= col + half) {
+            fillBoard(half, row + half, col + half, missingRow, missingCol);
+        } else {
+            board[row + half][col + half] = t;
+            fillBoard(half, row + half, col + half, row + half, col + half);
+        }
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/divideandconquer/TilingProblemTest.java b/src/test/java/com/thealgorithms/divideandconquer/TilingProblemTest.java
new file mode 100644
index 00000000..720e425f
--- /dev/null
+++ b/src/test/java/com/thealgorithms/divideandconquer/TilingProblemTest.java
@@ -0,0 +1,15 @@
+package com.thealgorithms.divideandconquer;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+
+import org.junit.jupiter.api.Test;
+
+public class TilingProblemTest {
+
+    @Test
+    public void testTilingSize2() {
+        int[][] expected = {{1, 1}, {1, 0}};
+        int[][] result = TilingProblem.solveTiling(2, 1, 1);
+        assertArrayEquals(expected, result);
+    }
+}