Minimum number of turns required in a maze. | Back tracking , Java

Dear Friends,


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

The problem is as below.

We are given a matrix of NXM size. Each Cell either contains 0 or 1. 1 represents a blockage or a Wall and 0 represents valid path. We need to reach from top left cell to the bottom right cell.
We need to out out the minimum number of turns required to reach the bottom right cell.


Friends Please find the code below.

package com.learn.dfs;

import java.util.Arrays;

public class MinimumTurns {

    public static void main(String[] args) {
        int[][] A = 
            { 
                { 0, 1, 1, 1, 0 }, 
                { 0, 0, 0, 0, 0 }, 
                { 1, 0, 0, 1, 1 }, 
                { 1, 1, 0, 0, 0 }, 
                { 0, 0, 0, 1, 0 },
                { 0, 1, 0, 1, 0 }, 
                { 0, 1, 0, 1, 0 }, 
                { 0, 0, 0, 0, 0 }, 
                { 1, 0, 0, 1, 1 }, 
                { 1, 0, 0, 0, 0 }, 
            };
        int initialDir = findInitialDirUtil(A);
        if (initialDir != -1) {
            findMinTurns(A, 0, 0, A.length, A[0].length, 0, initialDir);
            System.out.println(minTurns);
        } else {
            System.out.println("No path exists");
        }
    }

    static int minTurns = Integer.MAX_VALUE;

    public static int findInitialDirUtil(int[][] A) {
        if (A[0][1] == 0) {
            return 0;
        }
        if (A[1][0] == 0) {
            return 1;
        }
        return -1;
    }

    /**
     * A is the input matrix, with 0s and 1s. 1s represent the wall and 0s
     * represent the moving cells. The problem is to find the minimum number of
     * turns to be taken in order to reach from top left cell to bottom right
     * cell.
     * 
     * The below solution is based upon back tracking.
     * 
     * @param A
     * @param row
     * @param col
     * @param R
     * @param C
     * @param turns
     * @param currDir
     */
    public static void findMinTurns(int[][] A, int row, int col, int R, int C, int turns, int currDir) {
        if(turns >= minTurns){
            return;
        }
        
        if (row == R - 1 && col == C - 1) {
            if (turns < minTurns) {
                minTurns = turns;
            }
            return;
        }
        A[row][col] = turns;
        if (col + 1 < C && A[row][col + 1] == 0) {
            boolean isDirChanged = currDir != 0;
            int updatedDir = currDir;
            int updatedTurns = turns;
            if (isDirChanged) {
                updatedDir = 0;
                updatedTurns++;
            }
            findMinTurns(A, row, col + 1, R, C, updatedTurns, updatedDir);
        }

        if (row + 1 < R && A[row + 1][col] == 0) {
            boolean isDirChanged = currDir != 1;
            int updatedDir = currDir;
            int updatedTurns = turns;
            if (isDirChanged) {
                updatedDir = 1;
                updatedTurns++;
            }
            findMinTurns(A, row + 1, col, R, C, updatedTurns, updatedDir);
            
        }

        if (col - 1 >= 0 && A[row][col - 1] == 0) {
            boolean isDirChanged = currDir != 2;
            int updatedDir = currDir;
            int updatedTurns = turns;
            if (isDirChanged) {
                updatedDir = 2;
                updatedTurns++;
            }
            findMinTurns(A, row, col - 1, R, C, updatedTurns, updatedDir);
        }
        if (row - 1 >= 0 && A[row - 1][col] == 0) {
            boolean isDirChanged = currDir != 3;
            int updatedDir = currDir;
            int updatedTurns = turns;
            if (isDirChanged) {
                updatedDir = 3;
                updatedTurns++;
            }
            findMinTurns(A, row - 1, col, R, C, updatedTurns, updatedDir);
        }

        A[row][col] = 0;
    }
}

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;
    }
}