N Queen Problem : Placing N (natural number) Queens in a NXN chess board such that each queen is safe from the rest of the queens. | Java , Back tracking

Dear Friends,

I am here with you with another problem based upon back tracking. Its the Famous N Queen Problem.

Suppose we have a NXN matrix and we have N Queens. A Queen has a nature of attacking. If She is positioned at any cell then she can attack in all the four directions [Up,Bottom,Left,Right] and also can attack diagonally [Up-Left,Up-Right,Bottom-Left,Bottom-Right]

Friends if we have N Queens then we have solution for all the Natural numbers as values of N except 2 and 3.

Below is my solution to this problem. Code is in Java and its based upon Recursion and Back Tracking.

package com.study.backtracking;
/**
 * 
 * @author Krishna.k
 * 
 * Problem :N queen problem  :  Placing N queens on NXN chess board.
 * 
 * Solution exists for each natural number except for N = 2 and N = 3.
 * 
 * Solution is based on Back Tracking.
 *
 */
public class NQueenSolution {
    public static void main(String[] args) {
        int N = 5; // number of queens and the size of the board
        int[][] board = new int[N][N];
        NQueenSolution solution = new NQueenSolution();
        boolean isSolved = solution.solveNQueen(board, N, 0);
        
        if(isSolved){
            System.out.println("Solution exists");
            for(int i = 0 ; i < N ; i++){
                for(int j = 0; j < N ; j++){
                    System.out.print(board[i][j]+"  ");
                }
                System.out.println();
            }
        }
        else{
            System.out.println("Solution does not exists");
        }
    }
    

    public boolean solveNQueen(int[][] board, int N, int col) {
        if(col == N){
            return true; // all the queens have been placed successfully
        }
        for(int row = 0; row < N; row++){
            if(isSafeFromLeft(board, row, col) && isSafeFromBottomLeft(board, N, row, col) &&  isSafeFromTopLeft(board, row, col)){
                board[row][col] = 1;// this is a safe row and we proceed with next columns
                if(solveNQueen(board, N, col+1)){
                    return true; // returning true during back track with true as return type.
                }else{
                    board[row][col] = 0; // reseting the cell during back track with false as return type.
                }
            }
        }
        return false;
    }

    public boolean isSafeFromTopLeft(int[][] board, int row, int col) {
        int traverseRow = row - 1;
        int traverseCol = col - 1;
        while (traverseRow >= 0 && traverseCol >= 0) {
            if (board[traverseRow][traverseCol] == 1) {
                return false;
            }
            traverseRow = traverseRow - 1;
            traverseCol = traverseCol - 1;
        }
        return true;
    }

    public boolean isSafeFromLeft(int[][] board, int row, int col) {
        int traverseCol = col - 1;
        while (traverseCol >= 0) {
            if (board[row][traverseCol] == 1) {
                return false;
            }
            traverseCol = traverseCol - 1;
        }
        return true;
    }

    public boolean isSafeFromBottomLeft(int[][] board, int N, int row, int col) {
        int traverseRow = row + 1;
        int traverseCol = col - 1;
        while (traverseRow < N && traverseCol >= 0) {
            if (board[traverseRow][traverseCol] == 1) {
                return false;
            }
            traverseRow = traverseRow + 1;
            traverseCol = traverseCol - 1;
        }
        return true;
    }
}

Finding permutations of r elements from total of n elements. | Code in Java

Dear Friends,

I am here with you with another problem based on permutations and combinations.

We need to find all the permutations of R elements out of total N objects. For this we will first find  the combinations of R elements out of N elements and will permute them.

Please find below the code in java for this.

package com.learn.permutation;

import java.util.Arrays;

public class PermutationOfRelementsFromNElements {
    public static void main(String[] args) {
        char[] A = { 'P', 'Q', 'R', 'S' };
        int n = A.length;
        int r = 2;
        char[] T = new char[r];
        combine(A, T, n, r);
    }

    /**
     * To get permutations of r elements from total N eleemnts first we take r
     * combinations from n elements and for each combination we permute the r
     * elements
     * 
     * @param A
     * @param T
     * @param n
     * @param r
     */
    public static void combine(char[] A, char[] T, int n, int r) {
        if (r == 0) {
            permute(T, 0);
        } else if (n >= r) {
            T[r - 1] = A[n - 1];
            combine(A, T, n - 1, r - 1);
            combine(A, T, n - 1, r);
        }
    }

    /**
     * This method permutes the r elements in array T, T is prepared from the
     * combine method. T[] contains the combinations of r elements from N
     * elements
     * 
     * @param T
     * @param swapingPosition
     */
    public static void permute(char[] T, int swapingPosition) {
        if (swapingPosition == T.length) {
            System.out.println(Arrays.toString(T));
        } else {
            for (int i = swapingPosition; i < T.length; i++) {
                swap(T, swapingPosition, i);
                permute(T, swapingPosition + 1);
                swap(T, swapingPosition, i);
            }
        }
    }

    /**
     * This is simple utility method to swap two elements of the array A at
     * given two indices, index1 and index2
     * 
     * @param A
     * @param index1
     * @param index2
     */
    public static void swap(char[] A, int index1, int index2) {
        char temp = A[index1];
        A[index1] = A[index2];
        A[index2] = temp;
    }
}

 

Code in Java for finding Longest Path in Directed Acyclic Graph | Using Topological sorting

Dear Friends,

I am here with you with a problem based on Directed A-cyclic Graph [DAG].

Given a DAG, we are supposed to find the longest path in it.

Friends Please find below the code in java for this problem.

package com.learn.dag.longest.path;

public class LongestPathInDAG {
    public static void main(String[] args) {
        Graph g = new Graph(6);
        g.addEdge(0, 1, 5);
        g.addEdge(0, 2, 3);
        g.addEdge(1, 3, 6);
        g.addEdge(1, 2, 2);
        g.addEdge(2, 4, 4);
        g.addEdge(2, 5, 2);
        g.addEdge(2, 3, 7);
        g.addEdge(3, 5, 1);
        g.addEdge(3, 4, -1);
        g.addEdge(4, 5, -2);
        int s = 1;
        g.findLongestPath(s);
    }

    public static class Graph {
        private int V;
        private int[][] matrix;
        private int[] vertices;
        private boolean[] visited;
        private int[] distances;
        private int[] predecessor;
        private Stack stack;

        public Graph(int V) {
            this.V = V;
            vertices = new int[V];
            visited = new boolean[V];
            predecessor = new int[V];
            distances = new int[V];
            matrix = new int[V][V];
            stack = new Stack(V);
            for (int i = 0; i < V; i++) {
                addVertex(i);
                distances[i] = Integer.MIN_VALUE;
                predecessor[i] = -1;
            }
        }

        private void addVertex(int name) {
            vertices[name] = name;
        }

        public void addEdge(int source, int destination, int weight) {
            matrix[source][destination] = weight;
        }

        public void findLongestPath(int source) {
            invokeTopologicalSort();
            distances[source] = 0; // Initialize source with 0
            updateMaxDistanceForAllAdjVertices(); // for all nodes connected,
                                                    // directly or indirectly,
                                                    // with source will have
                                                    // their distances
                                                    // calculated
            printDistances(source);
            printPath(source);
        }

        private void printDistances(int source) {
            System.out.println("Distances from source " + source + " are as follows: ");
            for (int to = 0; to < V; to++) {
                int distance = distances[to];
                System.out.print("from " + source + " to " + to + ": ");
                if (distance == Integer.MIN_VALUE) {
                    System.out.println(" -Infinity ");
                } else {
                    System.out.println(distance + " ");
                }
            }
            System.out.println();
        }

        private void printPath(int source) {
            System.out.println("Path from source " + source + " to other nodes are as follows: ");
            for (int i = 0; i < V; i++) {
                if (distances[i] == Integer.MIN_VALUE) {
                    System.out.println("No Path from " + source + " to " + i);
                } else if (i != source) {
                    int from = predecessor[i];
                    System.out.print("Path from " + source + " to " + i + ": ");
                    if (from == source) {
                        System.out.print(from + " ");
                    }
                    while (from != source) {
                        System.out.print(from + " ");
                        from = predecessor[from];
                    }
                    System.out.print(i + " ");
                    System.out.println();
                }
            }
        }

        private void updateMaxDistanceForAllAdjVertices() {
            while (!stack.isEmpty()) {
                int from = stack.pop();
                if (distances[from] != Integer.MIN_VALUE) {
                    for (int adjacent = 0; adjacent < V; adjacent++) {
                        if (matrix[from][adjacent] != 0) {
                            if (distances[adjacent] < distances[from] + matrix[from][adjacent]) {
                                predecessor[adjacent] = from;
                                distances[adjacent] = distances[from] + matrix[from][adjacent];
                            }
                        }
                    }
                }
            }
        }

        private void invokeTopologicalSort() {
            for (int i = 0; i < V; i++) {
                if (!visited[i]) {
                    dfs(i);
                }
            }
        }

        private void dfs(int source) {
            visited[source] = true;
            for (int adjacent = 0; adjacent < V; adjacent++) {
                if (matrix[source][adjacent] != 0 && !visited[adjacent]) {
                    dfs(adjacent);
                }
            }
            stack.push(source);
        }

    }

    public static class Stack {
        private int maxSize;
        private int[] stack;
        private int top = -1;
        private int size = 0;

        public Stack(int maxSize) {
            this.maxSize = maxSize;
            stack = new int[maxSize];
        }

        public void push(int item) {
            stack[++top] = item;
            size++;
        }

        public int pop() {
            int item = stack[top--];
            size--;
            return item;
        }

        public boolean isEmpty() {
            return size == 0;
        }
    }
}

Subset Sum problem | Java and Backtracking

Hello Friends,

Today I am here with you with another problem based upon recursion and back tracking.

Suppose we have an array of positive integer elements: 'arr' and a positive number: 'targetSum'.
We need to all the possible subsets of the array elements such that adding the elements of any of the found subsets results in 'targetSum'.

Suppose we have arr= { 2, 3, 4, 5 } and targetSum = 7 then our subsets are {2,5},{3,4}.


Friends I have tried to solve this using Back-tracking, please find the code in java below.

package com.recursion.backtracking;

public class SubSetSum {
    public static void main(String[] args) {
        int[] input = { 2, 3, 4, 5 };
        int targetSum = 7;
        SubSetSum subSetSum = new SubSetSum();
        subSetSum.findSubSets(input, targetSum);
    }

    private int[] set;
    private int[] selectedElements;
    private int targetSum;
    private int numOfElements;

    public void findSubSets(int[] set, int targetSum) {
        this.set = set;
        this.numOfElements = set.length;
        this.targetSum = targetSum;
        selectedElements = new int[numOfElements];
        quicksort(set, 0, numOfElements-1);
        int sumOfAllElements = 0;
        for(int element : set){
            sumOfAllElements += element;
        }
        findSubSets(0, 0, sumOfAllElements);
    }

    private void findSubSets(int sumTillNow, int index, int sumOfRemaining) {
        selectedElements[index] = 1; // selecting element at index : 'index'
        if (targetSum == set[index] + sumTillNow) {
            print();
        }

        // (sum + set[index] + set[index+1] <= targetSum) : this condition
        // ensures selecting
        // the next element is useful and the total sum by including next
        // element will not exceed the target sum.
        if ((index + 1 < numOfElements) && (sumTillNow + set[index] + set[index + 1] <= targetSum)) {
            findSubSets(sumTillNow + set[index], index + 1, sumOfRemaining - set[index]);
        }

        // now exploring the other path: not Selecting the element at index:
        // 'index'
        selectedElements[index] = 0;

        // (sum + set[index+1] <= targetSum) : this condition ensures selecting
        // the next element is useful and the total sum by including next
        // element will not exceed the target sum.

        // (sum + sumOfRemaining - set[index] >= targetSum) ensures the total
        // sum of all the elements by excluding the current element may achieve
        // the target sum, if in case the resultant sum is less than the target
        // sum then exploring this path is of no use
        if ((index + 1 < numOfElements) && (sumTillNow + set[index + 1] <= targetSum)
                && (sumTillNow + sumOfRemaining - set[index] >= targetSum)) {
            findSubSets(sumTillNow, index + 1, sumOfRemaining - set[index]);
        }
    }

    private void print() {
        for (int i = 0; i < numOfElements; i++) {
            if (selectedElements[i] == 1) {
                System.out.print(set[i]+" ");
            }
        }
        System.out.println();
    }

    private void quicksort(int[] arr, int start, int end) {
        if (start < end) {
            swap(arr, (start + (end - start) / 2), end);
            int pIndex = partition(arr, start, end);
            quicksort(arr, start, pIndex - 1);
            quicksort(arr, pIndex + 1, end);
        }
    }

    private int partition(int[] arr, int start, int end) {
        int pIndex = start, pivot = arr[end];
        for (int i = start; i < end; i++) {
            if (arr[i] < pivot) {
                swap(arr,pIndex,i);
                pIndex++;
            }
        }
        swap(arr,pIndex,end);
        return pIndex;
    }

    private void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

Make correct equation to achieve a given RHS. | Java and Backtracking

Hello Friends,

I am with you with another problem based upon back tracking.

If we have an integer array A[] and another integer value K, we need to find is there a sequence of  '+', '-' exists  such that if applied on the elements of A produce K. The operations need to be applied without changing the relative position of the array elements.

Friends I have used recursion with back tracking to solve this problem, please find the code below for the same.

package com.recursion.backtracking;

import java.util.Arrays;

public class MakeValidEquation {
    public static void main(String[] args) {
        int numbers[] = { 2, 3, 4, 5 };
        int RHS = 6;
        
        MakeValidEquation equation = new MakeValidEquation(numbers, RHS);
        boolean isRHSAchievable = equation.makeValidEquation(0, numbers.length);
        if(isRHSAchievable){
            System.out.println("Operations : "+Arrays.toString(equation.operators));
        }else{
            System.out.println("RHS can not be achieved by +, - on the numbers");
        }
    }

    public MakeValidEquation(int[] numbers, int RHS) {
        this.numbers = numbers;
        int n = numbers.length;
        this.RHS = RHS;
        operators = new char[n-1];
    }

    private char[] operators;
    private int[] numbers;
    private int RHS;

    public boolean makeValidEquation(int i, int n) {
        if (i == n - 1) {
            int result = numbers[0];
            for (int j = 0; j <= n - 2; j++) {
                if (operators[j] == '+') {
                    result = result + numbers[j + 1];
                } else if (operators[j] == '-') {
                    result = result - numbers[j + 1];
                }
            }
            return result == RHS;
        }
        operators[i] = '+';
        if(makeValidEquation(i+1, n)){
            return true;
        }else {
            // try next option
            operators[i] = '-';
            if(makeValidEquation(i+1, n)){
                return true;
            }
            else return false;
        }
    }
}