JAVA program to help jerry find cheese

ALGORITHM:

Jerry is hungry and needs cheese. Bur cheese is in a maze and jerry needs help to find the cheese.
The maze solving is a classic algorithm under backtracking and ai.The problem is to find a path for the rat to food in a maze.
The problem can be solved trying out different paths possible and find the right path,
This logic can be implemented by a simple recursive algorithm. Since the jerryis performed in stack the processes are done in LIFO manner so if we have to print instructions to jerry we will do the process as cheese finds jerry.

1. Start with the target
2. If the cell is not legal (if it is out of maze or the cell is a wall) return false
3. If starting point has reached return true 
4. else make the cell a wall(to avoid coming back to the same path from any other instant) and
5. Take all the cells in  four direction and check whether the path can be reached through any of these cells and print opposite movement if the cell is a part of the path (eg if upper cell is part of path print DOWN)and return true and if not path backtrack and return false.These cells should chosen according to the distance to starting point from the current point.

  

The above maze is:

1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
1 0 0 1 0
1 1 1 1 0

So the jerry should move down four times and right three times and up two times and right and then up two times.

CODE:

import java.util.Scanner;

public class Maze{
   
   
    static Scanner in = new Scanner(System.in);
    static int[][] maze;

    static boolean solveMaze(int x,int y,int tx,int ty,int b,int h){

        if(x>=0 && x<b && y>=0 && y<h && maze[x][y]==1){//Checking if current cell is legal
            maze[x][y]-=1;
            if(x==tx && y==ty)//checking if point has reached
                return true;
            boolean up,down,left,right;
            /*

             Calculating horizontal and vertical distances and moving according to it

            */

            int xDiff=tx-x;
            if(xDiff<0)
                xDiff*=-1;
            int yDiff=ty-y;
            if(yDiff<0)
                yDiff*=-1;
            if(xDiff<yDiff){
                if(tx<x){
                    up=solveMaze(x-1,y,tx,ty,b,h);
                    down=solveMaze(x+1,y,tx,ty,b,h);
                }
                else{
                    down=solveMaze(x+1,y,tx,ty,b,h);
                    up=solveMaze(x-1,y,tx,ty,b,h);
                }
                if(ty<y){
                    left=solveMaze(x,y-1,tx,ty,b,h);
                    right=solveMaze(x,y+1,tx,ty,b,h);
                }
                else{
                    right=solveMaze(x,y+1,tx,ty,b,h);
                    left=solveMaze(x,y-1,tx,ty,b,h);
                }
            }
            else{
                if(ty<y){
                    left=solveMaze(x,y-1,tx,ty,b,h);
                    right=solveMaze(x,y+1,tx,ty,b,h);
                }
                else{
                    right=solveMaze(x,y+1,tx,ty,b,h);
                    left=solveMaze(x,y-1,tx,ty,b,h);
                }
                if(tx<x){
                    up=solveMaze(x-1,y,tx,ty,b,h);
                    down=solveMaze(x+1,y,tx,ty,b,h);
                }
                else{
                    down=solveMaze(x+1,y,tx,ty,b,h);
                    up=solveMaze(x-1,y,tx,ty,b,h);
                }
            }

            //print opposite movement if the cell is a part of the path
            if(up||down||left||right){
                if(up)
                    System.out.println("DOWN");
                if(down)
                    System.out.println("UP");
                if(left)
                    System.out.println("RIGHT");
                if(right)
                    System.out.println("LEFT");
                return true;
            }
            maze[x][y]+=1;//backtrack
            return false;
        }
        return false;
    }
    public static void main(String[] args) {
        System.out.println("enter number of rows and columns ");
        System.out.print("Rows: ");
        int b = in.nextInt();
        System.out.print("Columns: ");
        int h = in.nextInt();
        maze=new int[b][h];
        System.out.println("enter maze 1 for path and 0 for wall");
        for(int i=0;i<b;i++)
            for(int j=0;j<h;j++)
                maze[i][j]=in.nextInt();
        System.out.print("Enter Jerry position\nX: ");
        int begx=in.nextInt();
        System.out.print("Y: ");
        int begy=in.nextInt();
        System.out.print("Enter cheese position\nX: ");
        int tarx=in.nextInt();
        System.out.print("Y: ");
        int tary=in.nextInt();
        if(!solveMaze(tarx,tary,begx,begy,b,h))
        System.out.println("no path");
    }
}

OUTPUT:

enter number of rows and columns
Rows: 5
Columns: 5
enter maze 1 for path and 0 for wall
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
1 0 0 1 0
1 1 1 1 0
Enter Jerry position
X: 0
Y: 0
Enter cheese position
X: 0
Y: 4

DOWN
DOWN
DOWN
DOWN
RIGHT
RIGHT
RIGHT
UP
UP
RIGHT
UP
UP

[Read more]

JAVA program to print all permutations of a string

ALGORITHM:

The permutation of a string is the rearrangement of the string in different orders to form different strings of the same length. A string of length n can have n! permutations.

Source: Mathworld

We will start with each letter of the string and then we found all the possible combinations for the string beginning with that letter. And once we picked a letter in the 2nd position, we then found all the possible combinations that begin with that 2 letter sequence before we changed any of the letters in the first 2 positions. So, basically what we did was choose a letter and then peformed the permutation process starting at the next position to the right before we come back and change the character on the left. 

CODE:

import java.util.Scanner;

public class permutations{
   
    static char[] swap(char[] a,int i,int j){
        char tmp =a[i];
        a[i]=a[j];
        a[j]=tmp;
        return a;
    }
   
    static void printArray(char[] a){
        for (int i=0;i<a.length;i++)
            System.out.print(a[i]);
        System.out.println();
    }

    static void permute(char[] a,int index){
        if(index==a.length){
            printArray(a);
            return;
        }
        for(int i=index;i<a.length;i++){
            a=swap(a,i,index);
            permute(a,index+1);
            a=swap(a,i,index);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("Enter the string: ");
        permute(in.next().toCharArray(),0);
    }
}

OUTPUT:

Enter the string: abc
abc
acb
bac
bca
cba
cab

[Read more]

JAVA program to solve N Queens problem

ALGORITHM:

The N Queens problem is a classic problem which falls under various categories of algorithm design such as backtracking, brute force searching etc.

For further research on this problem use these links:

Wikipedia 

http://www.math.utah.edu/~alfeld/queens/queens.html 

http://mathworld.wolfram.com/QueensProblem.html 

 Okay, now let's comeback to the problem, N queens problem is a classic problem in which we have arrange N queens in a chessboard of dimension N*N, such that no queens should attack each other. 

A perfect solution to this problem have been a headache for mathematicians and programmers around the globe. A simple solution though not so ideal solution is posted here.

The problem is solved by a recursive backtracking algorithm the queens are placed in different optimal positions and checked whether it leads to the solution. if not the current position is backtracked and next possible position is checked.
          We start with the leftmost column and we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes then we backtrack and return false.

1. Start with first column
2. If all queens are placed return true
3. For the column passed to the function check every row position whether the queen can be placed safely(this is checked using a utility function named isSafe) if so the row is marked as a part of solution and recurse the function for next column. return true if it leads to solution otherwise backtrack.
4.  If all rows have been tried return false which triggers backtracking

CODE:

import java.util.Scanner;

class nQueens {
    static int[][] board;
    static int size;
    static boolean solveProblem(int col){
        if (col>size-1)
            return true;
        for (int i=0;i<size;i++){
            if(isSafe(i,col)){
                board[i][col]=1;
                if(solveProblem(col+1))
                    return true;
                board[i][col]=0;
            }
        }
        return false;
    }

    static boolean isSafe(int row,int col){
        int i,j;
        for(i=0;i<col;i++)
            if (board[row][i]==1)
                return false;
        for(i=row,j=col;(i>=0)&&(j>=0);i--,j--)
            if (board[i][j]==1)
                return false;
        for(i=row,j=col;(j>=0)&&(i<size);i++,j--)
            if (board[i][j]==1)
                return false;
        return true;
    }

    static void printBoard(){
        for (int i=0;i<size;i++) {
            System.out.print("\n");
            for (int j=0;j<size;j++) {
                System.out.print(board[i][j]+"\t");
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("Enter n: ");
        size = in.nextInt();
        board = new int[size][size];
        int i,j;
        for(i=0;i<size;i++)
            for(j=0;j<size;j++)
                board[i][j]=0;
        if (solveProblem(0)) {
            printBoard();
        }
        else {
            System.out.println("No soln...");
        }
    }
}

[Read more]