questions

kunal-kushwaha · kunal-kushwaha · commit 86cb6004885c · 2021-11-02T15:58:54.000+05:30
diff --git a/lectures/14-recursion/Backtracking - Questions.pdf b/lectures/14-recursion/Backtracking - Questions.pdf
diff --git a/lectures/14-recursion/code/src/com/kunal/backtracking/NKnights.java b/lectures/14-recursion/code/src/com/kunal/backtracking/NKnights.java
@@ -0,0 +1,83 @@
+package com.kunal.backtracking;
+
+public class NKnights {
+    public static void main(String[] args) {
+        int n = 4;
+        boolean[][] board = new boolean[n][n];
+        knight(board, 0, 0, 4);
+    }
+
+    static void knight(boolean[][] board, int row, int col, int knights) {
+        if (knights == 0) {
+            display(board);
+            System.out.println();
+            return;
+        }
+
+        if (row == board.length - 1 && col == board.length) {
+            return;
+        }
+
+        if (col == board.length) {
+            knight(board, row + 1, 0, knights);
+            return;
+        }
+
+        if (isSafe(board, row, col)) {
+            board[row][col] = true;
+            knight(board, row, col + 1, knights - 1);
+            board[row][col] = false;
+        }
+
+        knight(board, row, col + 1, knights);
+    }
+
+    private static boolean isSafe(boolean[][] board, int row, int col) {
+        if (isValid(board, row - 2, col - 1)) {
+            if (board[row - 2][col - 1]) {
+                return false;
+            }
+        }
+
+        if (isValid(board, row - 1, col - 2)) {
+            if (board[row - 1][col - 2]) {
+                return false;
+            }
+        }
+
+        if (isValid(board, row - 2, col + 1)) {
+            if (board[row - 2][col + 1]) {
+                return false;
+            }
+        }
+
+        if (isValid(board, row - 1, col + 2)) {
+            if (board[row - 1][col + 2]) {
+                return false;
+            }
+        }
+
+        return true;
+    }
+
+    // do not repeat yourself, hence created this function
+    static boolean isValid(boolean[][] board, int row, int col) {
+        if (row >= 0 && row < board.length && col >= 0 && col < board.length) {
+            return true;
+        }
+        return false;
+    }
+
+    private static void display(boolean[][] board) {
+        for(boolean[] row : board) {
+            for(boolean element : row) {
+                if (element) {
+                    System.out.print("K ");
+                } else {
+                    System.out.print("X ");
+                }
+            }
+            System.out.println();
+        }
+    }
+}
diff --git a/lectures/14-recursion/code/src/com/kunal/backtracking/NQueens.java b/lectures/14-recursion/code/src/com/kunal/backtracking/NQueens.java
@@ -0,0 +1,71 @@
+package com.kunal.backtracking;
+
+public class NQueens {
+    public static void main(String[] args) {
+        int n = 4;
+        boolean[][] board = new boolean[n][n];
+        System.out.println(queens(board, 0));
+    }
+
+    static int queens(boolean[][] board, int row) {
+        if (row == board.length) {
+            display(board);
+            System.out.println();
+            return 1;
+        }
+
+        int count = 0;
+
+        // placing the queen and checking for every row and col
+        for (int col = 0; col < board.length; col++) {
+            // place the queen if it is safe
+            if(isSafe(board, row, col)) {
+                board[row][col] = true;
+                count += queens(board, row + 1);
+                board[row][col] = false;
+            }
+        }
+
+        return count;
+    }
+
+    private static boolean isSafe(boolean[][] board, int row, int col) {
+        // check vertical row
+        for (int i = 0; i < row; i++) {
+            if (board[i][col]) {
+                return false;
+            }
+        }
+
+        // diagonal left
+        int maxLeft = Math.min(row, col);
+        for (int i = 1; i <= maxLeft; i++) {
+            if(board[row-i][col-i]) {
+                return false;
+            }
+        }
+
+        // diagonal right
+        int maxRight = Math.min(row, board.length - col - 1);
+        for (int i = 1; i <= maxRight; i++) {
+            if(board[row-i][col+i]) {
+                return false;
+            }
+        }
+
+        return true;
+    }
+
+    private static void display(boolean[][] board) {
+        for(boolean[] row : board) {
+            for(boolean element : row) {
+                if (element) {
+                    System.out.print("Q ");
+                } else {
+                    System.out.print("X ");
+                }
+            }
+            System.out.println();
+        }
+    }
+}
diff --git a/lectures/14-recursion/code/src/com/kunal/backtracking/SudokuSolver.java b/lectures/14-recursion/code/src/com/kunal/backtracking/SudokuSolver.java
@@ -0,0 +1,109 @@
+package com.kunal.backtracking;
+
+public class SudokuSolver {
+    public static void main(String[] args) {
+        int[][] board = new int[][]{
+                {3, 0, 6, 5, 0, 8, 4, 0, 0},
+                {5, 2, 0, 0, 0, 0, 0, 0, 0},
+                {0, 8, 7, 0, 0, 0, 0, 3, 1},
+                {0, 0, 3, 0, 1, 0, 0, 8, 0},
+                {9, 0, 0, 8, 6, 3, 0, 0, 5},
+                {0, 5, 0, 0, 9, 0, 6, 0, 0},
+                {1, 3, 0, 0, 0, 0, 2, 5, 0},
+                {0, 0, 0, 0, 0, 0, 0, 7, 4},
+                {0, 0, 5, 2, 0, 6, 3, 0, 0}
+        };
+
+        if (solve(board)) {
+            display(board);
+        } else {
+            System.out.println("Cannot solve");
+        }
+
+    }
+
+    static boolean solve(int[][] board) {
+        int n = board.length;
+        int row = -1;
+        int col = -1;
+
+        boolean emptyLeft = true;
+
+        // this is how we are replacing the r,c from arguments
+        for (int i = 0; i < n; i++) {
+            for (int j = 0; j < n; j++) {
+                if (board[i][j] == 0) {
+                    row = i;
+                    col = j;
+                    emptyLeft = false;
+                    break;
+                }
+            }
+            // if you found some empty element in row, then break
+            if (emptyLeft == false) {
+                break;
+            }
+        }
+
+        if (emptyLeft == true) {
+            return true;
+            // soduko is solved
+        }
+
+        // backtrack
+        for (int number = 1; number <= 9; number++) {
+            if (isSafe(board, row, col, number)) {
+                board[row][col] = number;
+                if (solve(board)) {
+                    // found the answer
+                    return true;
+                } else {
+                    // backtrack
+                    board[row][col] = 0;
+                }
+            }
+        }
+        return false;
+    }
+
+    private static void display(int[][] board) {
+        for(int[] row : board) {
+            for(int num : row) {
+                System.out.print(num + " ");
+            }
+            System.out.println();
+        }
+    }
+
+
+    static boolean isSafe(int[][] board, int row, int col, int num) {
+        // check the row
+        for (int i = 0; i < board.length; i++) {
+            // check if the number is in the row
+            if (board[row][col] == num) {
+                return false;
+            }
+        }
+
+        // check the col
+        for (int[] nums : board) {
+            // check if the number is in the col
+            if (nums[col] == num) {
+                return false;
+            }
+        }
+
+        int sqrt = (int)(Math.sqrt(board.length));
+        int rowStart = row - row % sqrt;
+        int colStart = col - col % sqrt;
+
+        for (int r = rowStart; r < rowStart + sqrt; r++) {
+            for (int c = colStart; c < colStart + sqrt; c++) {
+                if (board[r][c] == num) {
+                    return false;
+                }
+            }
+        }
+        return true;
+    }
+}
