N Queen Problem : Using Backtracking

N Queen problem is one of the common interview questions which is asked in many popular companies. This problem is solved using backtracking.

Problem Statement:

We are given N x N chessboard and N queens. The queens should be placed in such a way that no two queens should lie in the same column, the same row and the same diagonal.

Algorithm:

1. Start from leftmost part ; 2. If got the solution return true; 3. Check for the queen to be placed in the current column. If placed in the current column then     check recursively for the solution and mark row of the current column with "Q". 4. If at any point during recursion solution comes out to be wrong then backtrack and unmark     the marked places. 5. Return false if no solution is found else print the solution.

Solution:

Refer the video tutorial:

Algorithm: Tower of Hanoi

Tower of Hanoi consists of three towers called as pegs with n number of rings. Rings are of different size. 

Conditions to be fulfilled:

The basic conditions which are required to be fulfilled are as follows :

• It is required to move one ring at a time.
• The smaller ring should not lie below the larger ring.

Steps to be performed :

Steps-1: move n-1 ring to the auxiliary tower.

Step-2: move the last ring in the first tower to the tower where the rings are required to be placed. 

Step-3: move n-1 rings from auxiliary tower to the tower where the rings are required to be placed.

Algorithm :

towerOfHanoi ( ringsCount, from tower, to tower, aux tower){         if(ringsCount==1) {         print(from tower , to tower);         return;     }        towerOfHanoi(ringsCount, from tower, aux tower, to tower);        print(from tower , to tower);     towerOfHanoi(ringsCount, aux tower, to tower, from tower); }

Coding In Java:

Refer the video tutorial:

Create Tetris Game Using Java

Application Coding and Game Creation:

Nowadays top companies are looking for talented people who are well in the data structure and application coding. To check application coding the companies may ask to create sample games within a given time frame on their system. So sometimes it becomes useful to have basic ideas of game creation.

Tetris Game:

In this tutorial, a basic game is created using Java. The name of the game is Tetris.
This is the same game which also used to come in the game plays which were quite handy.

Sample code:

The sample code is provided for reference.

  import java.awt.Color;
  import java.awt.Graphics;
  import java.awt.Point;
  import java.awt.event.KeyEvent;
  import java.awt.event.KeyListener;
  import java.util.ArrayList;
  import java.util.Collections;

  import javax.swing.JFrame;
  import javax.swing.JPanel;

  public class MyGame extends JPanel {

public static void main(String[] args) {
JFrame f = new JFrame("MyGame");
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.setSize(12*26+10, 26*23+25);
f.setVisible(true);


final MyGame game = new MyGame();
game.init();
f.add(game);

f.addKeyListener(new KeyListener() {
public void keyTyped(KeyEvent e) {
}

public void keyPressed(KeyEvent e) {
switch (e.getKeyCode()) {
case KeyEvent.VK_UP:
game.rotate(-1);
break;
case KeyEvent.VK_DOWN:
game.rotate(+1);
break;
case KeyEvent.VK_LEFT:
game.move(-1);
break;
case KeyEvent.VK_RIGHT:
game.move(+1);
break;
case KeyEvent.VK_SPACE:
game.dropDown();
game.score += 1;
break;
}
}

public void keyReleased(KeyEvent e) {
}
});
new Thread() {
@Override public void run() {
while (true) {
try {
Thread.sleep(1000);
game.dropDown();
} catch ( InterruptedException e ) {}
}
}
}.start();
}

private final Point[][][] MyShapes = {
// I-Piece
{
{ new Point(0, 1), new Point(1, 1), new Point(2, 1), new Point(3, 1) },
{ new Point(1, 0), new Point(1, 1), new Point(1, 2), new Point(1, 3) },
{ new Point(0, 1), new Point(1, 1), new Point(2, 1), new Point(3, 1) },
{ new Point(1, 0), new Point(1, 1), new Point(1, 2), new Point(1, 3) }
},

// J-Piece
{
{ new Point(0, 1), new Point(1, 1), new Point(2, 1), new Point(2, 0) },
{ new Point(1, 0), new Point(1, 1), new Point(1, 2), new Point(2, 2) },
{ new Point(0, 1), new Point(1, 1), new Point(2, 1), new Point(0, 2) },
{ new Point(1, 0), new Point(1, 1), new Point(1, 2), new Point(0, 0) }
},

// L-Piece
{
{ new Point(0, 1), new Point(1, 1), new Point(2, 1), new Point(2, 2) },
{ new Point(1, 0), new Point(1, 1), new Point(1, 2), new Point(0, 2) },
{ new Point(0, 1), new Point(1, 1), new Point(2, 1), new Point(0, 0) },
{ new Point(1, 0), new Point(1, 1), new Point(1, 2), new Point(2, 0) }
},

// O-Piece
{
{ new Point(0, 0), new Point(0, 1), new Point(1, 0), new Point(1, 1) },
{ new Point(0, 0), new Point(0, 1), new Point(1, 0), new Point(1, 1) },
{ new Point(0, 0), new Point(0, 1), new Point(1, 0), new Point(1, 1) },
{ new Point(0, 0), new Point(0, 1), new Point(1, 0), new Point(1, 1) }
}
};

private final Color[] MyColors = {
Color.cyan, Color.MAGENTA, Color.orange, Color.yellow, Color.black, Color.pink,
               Color.red };

private Point pt;
private int currentPiece;
private int rotation;
private ArrayList<Integer> nextPieces = new ArrayList<Integer>();

private long score;
private Color[][] well;

private void init() {
well = new Color[12][24];
for (int i = 0; i < 12; i++) {
for (int j = 0; j < 23; j++) {
if (i == 0 || i == 11 || j == 22) {
well[i][j] = Color.PINK;
} else {
well[i][j] = Color.black;
}
}
}
newPiece();
}
public void newPiece() {
pt = new Point(5, 2);
rotation = 0;
if (nextPieces.isEmpty()) {
Collections.addAll(nextPieces, 0, 1, 2, 3);
Collections.shuffle(nextPieces);
}
currentPiece = nextPieces.get(0);
nextPieces.remove(0);
}

private boolean collidesAt(int x, int y, int rotation) {
for (Point p : MyShapes[currentPiece][rotation]) {
if (well[p.x + x][p.y + y] != Color.black) {
return true;
}
}
return false;
}

public void rotate(int i) {
int newRotation = (rotation + i) % 4;
if (newRotation < 0) {
newRotation = 3;
}
if (!collidesAt(pt.x, pt.y, newRotation)) {
rotation = newRotation;
}
repaint();
}

public void move(int i) {
if (!collidesAt(pt.x + i, pt.y, rotation)) {
pt.x += i;
}
repaint();
}

public void dropDown() {
if (!collidesAt(pt.x, pt.y + 1, rotation)) {
pt.y += 1;
} else {
fixToWell();
}
repaint();
}
public void fixToWell() {
for (Point p : MyShapes[currentPiece][rotation]) {
well[pt.x + p.x][pt.y + p.y] = MyColors[currentPiece];
}
clearRows();
newPiece();
}

public void deleteRow(int row) {
for (int j = row-1; j > 0; j--) {
for (int i = 1; i < 11; i++) {
well[i][j+1] = well[i][j];
}
}
}

public void clearRows() {
boolean gap;
int numClears = 0;
for (int j = 21; j > 0; j--) {
gap = false;
for (int i = 1; i < 11; i++) {
if (well[i][j] == Color.black) {
gap = true;
break;
}
}
if (!gap) {
deleteRow(j);
j += 1;
numClears += 1;
}
}
switch (numClears) {
case 1: score += 100;break;
case 2: score += 300;break;
case 3: score += 500;break;
case 4: score += 800;break;
}
}
private void drawPiece(Graphics g) {
g.setColor(MyColors[currentPiece]);
for (Point p : MyShapes[currentPiece][rotation]) {
g.fillRect((p.x + pt.x) * 26,
   (p.y + pt.y) * 26,
   25, 25);
}
}

@Override
public void paintComponent(Graphics g)
{
g.fillRect(0, 0, 26*12, 26*23);
for (int i = 0; i < 12; i++) {
for (int j = 0; j < 23; j++) {
g.setColor(well[i][j]);
g.fillRect(26*i, 26*j, 25, 25);
}
}
g.setColor(Color.WHITE);
g.drawString("Score : " + score, 19*12, 25);

drawPiece(g);
}
  }

The game will start as soon as the java application will be started.

Refer the video tutorial.

 ☛ Next >> Algorithm: Tower of Hanoi

                    Tower of Hanoi consists of three towers called as pegs with n number of ... 

Java Multithreading : ExecutorService (Real-Life Example)

In this lesson, we will see how we can use the executor service in a real-life scenario. We will use the worker threads to execute a task and thus reduce the processing time by using a thread pool.

Scenario:

Suppose you have to send emails to all the students of a college with their details.

Let's take some assumptions. Consider that it takes around 30 milliseconds to send mail to one student. Let the number of students be 1000. Considering in mind all these total time for sending mail becomes time multiplied with students count plus some delta time for processing extra code.

Assumptions:

The total number of students: 1000 students.

The time it takes to send mail for one student=30 milliseconds or 0.03 second.

Total time using single thread= 0.03 X 1000 + delta time for processing=30 seconds + delta time for processing.

Using Single Thread:

Let's create a single thread using newSingleThreadExecutor() method of ExecutorService. Create a thread which takes 30 milliseconds to execute its task.

  

class SendMail implements Runnable {       public void run() {               try{                    Thread.sleep(30);               } catch (InterruptedException e) {                    e.printStackTrace();               }       } }

Run the task for 3000 times. For running with single thread the code will be like below.

  

ExecutorService es=Executors.newSingleThreadExecutor();for(int i=0;i<3000;i++){      es.submit(new SendMail()); }

We can print the date to find the time difference between start and end of the code to send mail.

It almost came out 30 seconds + some delta time due to processing.

Using Thread Pool:

Let's create a single thread using newFixedThreadPool(threadCount) method of ExecutorService. Create a thread which takes 30 milliseconds to execute its task.

  

class SendMail implements Runnable {       public void run() {               try{                    Thread.sleep(30);               } catch (InterruptedException e) {                    e.printStackTrace();               }       } }

Run the task for 3000 times. For running with a thread pool of 10 worker threads, the code will be like below.

  

ExecutorService es=Executors.newFixedThreadPool(10); for(int i=0;i<3000;i++){      es.submit(new SendMail()); }

We can print the date to find the time difference between start and end of the code to send mail.

It almost came out 3 seconds using 10 worker threads due to processing.

Conclusion:

When a single thread is used to execute task it took more than 30 seconds. We created a thread pool of 10 worker threads, then it took almost 3 seconds. So we can create multiple threads using executor service and can reduce the time and increase the efficiency of a task in the project which requires a similar task to be done multiple times.

Refer the video tutorial:

Custom Exception In Java

We can create our own custom exception in Java. This can be done by extending the Exception class of java.lang package. In other words, we need to import java.lang.Exception and extend this Exception class in our custom exception class.

Example :

First, create a class. In this case, our class is MyException which is extending the Exception class of java.lang package.

import java.lang.Exception;   /*extend Exception of java.lang package*/      class MyException extends Exception{           public MyException(String excStr){            /*Create a constructor and pass string argument */                            super(excStr);                            /*call the parent class constructor*/             }   }

To apply in the code use throws and pass the string as the perimeter. Here throw new MyException("Caught Sumit!") is used to throw the exception. 

public class MyCustomException{            public static final String DETAILS_OF_LOGGEDIN_USER= " I am Sumit";            public static void main(String[] args){                try{                       if(DETAILS_OF_LOGGEDIN_USER.contains("Sumit")){                             throw new MyException("Caught Sumit");                        }                 }catch(MyException me){                       System.out.println(me.getMessage());                 }               }   }

The caught exception can be read by using getMessage() method of the Exception class.

In this case, the output will be the String passed in the Constructor of MyException class. So getMessage() method will print "Caught Sumit".

Refer the video tutorial:

Java Multithreading: ExecutorService methods Submit() & Execute()

Submit() and execute() are the methods of ExecutorService in Java. One can assign any task in these methods for execution of a particular code block.

The Future interface:

The Future interface is used to get the return data of Callable and Runnable tasks. It has a method called get() so one can pass the result of submit() in the Future instance to track the output result.  

Difference between submit() and execute():

Since both the methods can be used to perform a given task but major difference lies between the return type of both the method. The return type of execute() method is void so it returns null when data is passed in Future object.

So when execute() method is passed in Future then compile time error is shown.

But when submit() method is called no compile-time error is displayed and the code runs successfully.

One can track the execution of a code block in submit() method by getting the return data using get() method of future. But this is not possible in execute() method of ExecutorService as the return type of execute() method is void.

Types methods of submit() method:

There are two types of submit method. One with the Runnable and the other with the Callable interface.

• submit(new Runnable): In which Runnable has the method public void run().
• submit(new Callable): In which Callable has the method public Object call().

Difference between submit(Runnable) and submit(Callable) :

The return type is the main difference between the submit with Runnable and submit with Callable.

As the name suggests the Callable calls the data at the end and provides in the Future object.

As we can see Object is the return type in public Object call(). The object is the return type here and the "Got something in return with callable" got printed in the console.

But in the case of submit with Runnable the return type is void so "null" gets printed in the console

As one can see void is the return type here in public void run() so "null" is passed in the Future.

Refer the video tutorial for more detail:

 ☛ Next >> Java Multithreading : ExecutorService (Real-Life Example)

                    Executor Service is an interface in Java to create a pool of the ... 

Java Multithreading : ExecutorService

Executor Service is an interface in Java to create a pool of threads or worker threads to execute a task asynchronously. The instance of ExecutorService is created and with the help of its instance, a pool of threads are created. The thread pool can have single or multiple threads depending upon the requirement.

Creation of thread pool :

A thread pool can be created with the help of ExecutorService in the below-mentioned way.

• Creation of Single thread by using newSingleThreadExecutor().
• Creation of multiple threads by using newFixedThreadPool(n) where n is the required count of the worker threads.
• Creation of catched thread pool by using newCachedThreadPool().

       

Syntax is mentioned below :

ExecutorService execute=Executors.newSingleThreadExecutor();        /* For single thread creation */ ExecutorService execute=Executors.newFixedThreadPool();       /* For a fixed count of worker threads */ ExecutorService execute=Executors.newCachedThreadPool();        /* For catched thread pool */

 ☛ Next >> Java Multithreading : ExecutorService methods submit() & execute()

                    Submit() and execute() are the methods of ExecutorService in Java. One ... 

Java Multithreading : Volatile Key (Basic Synchronization)

The concepts of the volatile key are often misunderstood and often explained in the wrong way.
Providing the concepts in simple and in an easy to understand way.

What is volatile Key?

Volatile is a keyword which can be applied to a variable to perform basic synchronization.

To make a variable volatile provide volatile in the declaration of the variable.

Uses of volatile key:

• Used to make operation on a variable like reading and writing through main memory.
• It acts as the operations are performed in a synchronized block.
• The value of a variable will never be caught locally.

Example :

To make use of volatile keyword just provide in the declaration only.

Below is the example where int data variable is used along with the volatile keyword.

      

public class MyVolatile {       private volatile int data = 0;          /* other codes along with                            getter & setter */ }

Refer the video tutorial :

 ☛ Next >> Java Multithreading : ExecutorService

                    Executor Service is an interface in Java to create a pool of the ... 

Java Multithreading : Synchronization (Method Level)

In multithreading, synchronization is used to allow only one thread at a time to access the shared resource.

Uses of Synchronization keyword in Java :

• To prevent the other thread to interface with the current thread execution.
• To maintain consistency where multiple threads are accessing the same resource.

Synchronization can be applied in three ways :

• Method level synchronization
• Synchronization block
• Static Synchronization

Method Level Synchronization :

In method level synchronization the method is marked with synchronization keyword.

In this case, the lock is acquired on the object. The lock is released when the execution of the synchronization method is completed.

Example of method level Synchronization :

Below is the program in which inc() method is called simultaneously by the two threads t1 and t2.

The inc method is incrementing the count by 1. The count ++ is being performed in the inc() method. The count++ is nothing but count = count+1. If this process is performed without synchronized keyword then the count is not coming 10000 but it is coming less than that.

Why this is happening?

Here inc() method is performing count++ or in other terms count=count+1. 

Suppose for one thread t1 (let) count be 355 suddenly thread t2 also entered inc() method at the same time t2 also read count as 355 only. At this moment t1 performed count=355+1 and t2 also did the same. The result after inc() method execution for t1 and t2 at this step will be count=356 only. 

But if t1 would have executed first then count would have been 356 and t2 when tried to execute then it would have come out with the result of count as 357.

Let's apply the Synchronized key.

Using the synchronized key on method level the result came correct as 10000.

Refer the video tutorial :

 ☛ Next >> Java Multithreading : Volatile Key (Basic Synchronization)

                    The concepts of the volatile key are often misunderstood and often ... 

Mouse Pointer Random Movement In Java

Nowadays in some office, it is required to stay on your desk and work for office hours.
The employees are being tracked depending upon the login hours on their systems.
Sometimes it also happens that if someone is not on their desk for even 5 minutes then the information goes to the manager.

So to avoid these scenarios it is better to make a utility class in java to make the random movement of the mouse pointer. This will let the admin assume that employee is on the seat.

To make this type of utility we will use the Robot class of java.awt package and we will use the mouseMove(x,y) method of Robot class. x and y are the coordinates.

Below is the program to move the mouse from one corner to another diagonally.

      

import java.awt.Robot; public class MyUtilityToMoveMouse {          public static void main(String... args) throws Exception {                  int x = 0, y = 0;          boolean bool = true;          Robot robot = new Robot();                   while (true) {                           robot.mouseMove(x++, y++);                              Thread.sleep(20);            }      } }

Below is the program to move the mouse in zig-zag fashion like the lifeline.

      

import java.awt.Robot; public class MyUtilityToMoveMouse {          public static void main(String... args) throws Exception {                  int x = 100, y = 400;          boolean bool = true;          Robot robot = new Robot();                   while (true) {                           robot.mouseMove(x, y);                           if (bool) {                            x += 5;y += 5;                    } else {                            x += 5;y -= 5;                    }                          if (y == 420) bool = false;                    else if (y == 380) bool = true;                          if (x==1300)x=100;                          Thread.sleep(20);            }      } }

Refer the video tutorial :

☛ Next >> Custom Exception In Java

                   We can create our own custom exception in Java. This can be done by  ... 

Java Multithreading : Implements Runnable Vs Thread Class

In Java we can create a thread in two ways :

• By extending Thread class.
• By implementing the Runnable interface.

Difference between  Implements Runnable and Thread Class :

Since by extending Thread class we cannot inherit other classes. But in the case of Runnable Interface, we can implement as many interfaces as much as required.

When we create a thread using Thread class each time a new object is created. But in the case of the Runnable interface, it uses the same object for multiple threads.

The Runnable interface is preferred over the Thread class because of the above reasons.

Creating thread using Thread Class :

For creating a thread using Thread class extend the Thread class. Provide the code in run() method. Create the thread using new operator and call the start() method of Thread class.

      

class PlayExt extends Thread{          public void run(){            // code to execute        } } public class MyExtend {       public static void main(String[] args) {                  PlayExt pe = new PlayExt();             // create object using new operator                         pe.start();             // call the start method to run a thread              } }

Creating thread using Runnable Interface :

For creating a thread by implementing the Runnable interface. Provide the code in run() method. Create the thread by providing the class which implements the Runnable interface in the constructor of Thread class and call the start() method of Thread class.

             
      

// can extend other class also class PlayRun implements Runnable{           public void run(){            // code to execute        } } public class MyRunnable {       public static void main(String[] args) {                    Thread pr = new Thread(new PlayRun());              // provide the  in the constructor of Thread class             pr.start();             // call the start mentod to execute thread        } }

Refer the video tutorial :

 ☛ Next >> Java Multithreading : Synchronization (Method Level)

                    In multithreading, synchronization is used to allow only one thread at a time to ...