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: