Backtracking | N Queens Problem using backtracking algorithm | Permutations | The Java Placement Course | Apna College |

Backtracking in Recursion

Java

                                        Backtracking is a popular algorithmic technique used in programming to find a solution to a problem by trying out different combinations of choices and undoing those choices that don't lead to a valid solution.

In backtracking, the algorithm starts by making a choice and exploring a path to see if it leads to a valid solution. If the path leads to a dead end or invalid solution, the algorithm backtracks and tries another path. This process is repeated until a valid solution is found or all possible combinations have been explored.

Backtracking is commonly used in solving problems such as generating all possible permutations or combinations of a given set of elements, solving Sudoku puzzles, solving the N-queens problem, and many others.                  

The N Queens Problem is a classic example of a backtracking algorithm. The problem is to place N queens on an NxN chessboard in such a way that no two queens threaten each other. That is, no two queens are in the same row, column, or diagonal.

Here's a Java implementation of the N Queens Problem using backtracking:

Java

public class NQueens {

    private int[] queens;

    private int numSolutions;

    public NQueens(int n) {

        queens = new int[n];

        numSolutions = 0;

    }

    public void solve() {

        solve(0);

    }

    private void solve(int row) {

        if (row == queens.length) {

            numSolutions++;

            printSolution();

        } else {

            for (int i = 0; i < queens.length; i++) {

                queens[row] = i;

                if (isValid(row)) {

                    solve(row + 1);

                }

            }

        }

    }

    private boolean isValid(int row) {

        for (int i = 0; i < row; i++) {

            if (queens[i] == queens[row] ||

                Math.abs(queens[i] - queens[row]) == row - i) {

                return false;

            }

        }

        return true;

    }

    private void printSolution() {

        System.out.print("Solution #" + numSolutions + ": ");

        for (int i = 0; i < queens.length; i++) {

            System.out.print(queens[i] + " ");

        }

        System.out.println();

    }

}

To use this class, you can create an instance of it and then call the solve() method:

Java

NQueens nQueens = new NQueens(8);

nQueens.solve();

This will solve the problem for an 8x8 chessboard and print out all the solutions.

As for permutations in Java, you can use the java.util.Collections class to generate permutations of a list. Here's an example:

// Java //

import java.util.*;

public class Permutations {

    public static void main(String[] args) {

        List<Integer> list = Arrays.asList(1, 2, 3);

        List<List<Integer>> permutations = new ArrayList<>(permute(list));

        System.out.println(permutations);

    }

    public static <T> Set<List<T>> permute(List<T> list) {

        if (list.size() == 0) {

            Set<List<T>> result = new HashSet<>();

            result.add(new ArrayList<>());

            return result;

        }

        T first = list.get(0);

        List<T> rest = list.subList(1, list.size());

        Set<List<T>> permutations = new HashSet<>();

        for (List<T> permutation : permute(rest)) {

            for (int i = 0; i <= permutation.size(); i++) {

                List<T> temp = new ArrayList<>(permutation);

                temp.add(i, first);

                permutations.add(temp);

            }

        }

        return permutations;

}

}

This code generates all permutations of the list [1, 2, 3] and prints them out. The permute method is a recursive method that generates all permutations of the list by taking the first element, generating all permutations of the rest of the list, and inserting the first element at every possible position in each permutation of the rest of the list. The resulting set of permutations is returned.

-------------------------------------------------------------------------------------------------

Print all Permutations

Time complexity - O(n*n!)

public class Recursion3 {

 

   public static void printPermutation(String str, int idx, String perm) {

       if(str.length() == 0) {

           System.out.println(perm);

           return;

       }

      

       for(int i=0; i<str.length(); i++) {

           char currChar = str.charAt(i);

           String newStr = str.substring(0, i) + str.substring(i+1);

           printPermutation(newStr, idx+1, perm+currChar);

       }

   }

   public static void main(String args[]) {

       String str = "abc";

       printPermutation(str, 0, "");

   }

}

 

N-Queens

Time complexity - O(n^n)

class Solution {

   public boolean isSafe(int row, int col, char[][] board) {

       //horizontal

       for(int j=0; j<board.length; j++) {

           if(board[row][j] == 'Q') {

               return false;

           }

       }

      

       //vertical

       for(int i=0; i<board.length; i++) {

           if(board[i][col] == 'Q') {

               return false;

           }

       }

      

       //upper left

       int r = row;

       for(int c=col; c>=0 && r>=0; c--, r--) {

           if(board[r][c] == 'Q') {

               return false;

           }

       }

      

       //upper right

       r = row;

       for(int c=col; c<board.length && r>=0; r--, c++) {

           if(board[r][c] == 'Q') {

               return false;

           }

       }

      

       //lower left

       r = row;

       for(int c=col; c>=0 && r<board.length; r++, c--) {

           if(board[r][c] == 'Q') {

               return false;

           }

       }

      

       //lower right

       for(int c=col; c<board.length && r<board.length; c++, r++) {

           if(board[r][c] == 'Q') {

               return false;

           }

       }

      

       return true;

   }

  

   public void saveBoard(char[][] board, List<List<String>> allBoards) {

       String row = "";

       List<String> newBoard = new ArrayList<>();

      

       for(int i=0; i<board.length; i++) {

           row = "";

           for(int j=0; j<board[0].length; j++) {

               if(board[i][j] == 'Q')

                   row += 'Q';

               else

                   row += '.';

           }

           newBoard.add(row);

       }

      

       allBoards.add(newBoard);

   }

  

   public void helper(char[][] board, List<List<String>> allBoards, int col) {

       if(col == board.length) {

           saveBoard(board, allBoards);

           return;

       }

      

       for(int row=0; row<board.length; row++) {

           if(isSafe(row, col, board)) {

               board[row][col] = 'Q';

               helper(board, allBoards, col+1);

               board[row][col] = '.';

           }

       }

   }

  

   public List<List<String>> solveNQueens(int n) {

       List<List<String>> allBoards = new ArrayList<>();

       char[][] board = new char[n][n];

      

       helper(board, allBoards, 0);

       return allBoards;

   }

}

Homework Problems

1. https://leetcode.com/problems/permutations/ (Similar to print Permutations)

2. https://www.hackerrank.com/challenges/knightl-on-chessboard/problem (Similar to N-Queens)

3. https://leetcode.com/problems/sudoku-solver/ (Will be discussed in next class)

  READ THIS:-  

1) Write a function to multiply 2 numbers | write a program to multiply two numbers in java

2) String Builder | Reverse a String (using StringBuilder class)| Get A Character from Index| Lecture 13

3) 2D Arrays | Java Complete Placement Course | Lecture 11

4) Bit Manipulation |Get Bit | Set Bit | Update Bit | Lecture 14

5) Top Beginner Patterns in Java: How to Print Star, Number and Character (Lecture 5)

6)Conditional Statements | if, If-else, "if" and "if else", Switch Break | Complete Java Placement Course | Lecture 3

7) Insertion Sort | Insertion sort algorithm | insertion sort time complexity