Tuesday, December 1, 2009

Eight Queens Solution with DFS using Backtracking (Step-by-step simulation)







  1. package eight_queen;



  2. import java.awt.AWTEvent;

  3. import java.awt.AlphaComposite;

  4. import java.awt.BorderLayout;

  5. import java.awt.Color;

  6. import java.awt.Composite;

  7. import java.awt.EventQueue;

  8. import java.awt.Frame;

  9. import java.awt.Graphics;

  10. import java.awt.Graphics2D;

  11. import java.awt.Image;

  12. import java.awt.Toolkit;

  13. import java.awt.event.ActionEvent;

  14. import java.awt.event.ActionListener;

  15. import java.awt.event.WindowEvent;

  16. import java.lang.reflect.InvocationTargetException;

  17. import java.util.Random;

  18. import java.util.Scanner;

  19. import java.util.concurrent.locks.Lock;

  20. import java.util.concurrent.locks.ReentrantLock;

  21. import java.util.logging.Level;

  22. import java.util.logging.Logger;

  23. import javax.swing.JButton;

  24. import javax.swing.JFrame;

  25. import javax.swing.JOptionPane;

  26. import javax.swing.JPanel;



  27. /**

  28.  *

  29.  * @author rooparam

  30.  */



  31. class Locations {

  32.     public Locations(int size ) {

  33.         at = new int[size];

  34.         top = 0;    // next coloumn of a queen

  35.     }

  36.     public int top;

  37.     public int[] at;

  38. }





  39. class MyButton extends JButton {

  40.     MyButton( ) {

  41.         super("continue");

  42.     }

  43. }



  44. class Board extends JPanel {

  45.     Board ( Locations Q ) {

  46.         queens = Q;

  47.         //setSize(640, 480);

  48.         setBackground(Color.WHITE);

  49.     }



  50.     @Override

  51.     public void paint ( Graphics g ) {

  52.         Image image = Toolkit.getDefaultToolkit().getImage("eight_queen/smvdu_logo_1.gif");

  53.         g.drawImage(image, 0, 0, getBounds().width, getBounds().height, this);

  54.         drawBoard ( g );

  55.         drawQueens(g);

  56.         drawRemaining(g);

  57.         g.setColor(Color.RED);

  58.         String str = "Coder : Rooparam Chaudhary";

  59.         g.drawString(str, getBounds().width - 180, getBounds().height - 10);

  60.     }



  61.     private Locations queens;



  62.     private void drawRemaining(Graphics g2) {

  63.         Graphics2D g = (Graphics2D)g2;

  64.         int rule = AlphaComposite.SRC_OVER;

  65.         float alpha = 0.8f;

  66.         Composite oldC = g.getComposite( );

  67.         g.setComposite(AlphaComposite.getInstance(rule, alpha));

  68.         g.setPaint(Color.BLACK);

  69.        

  70.         int width = getBounds( ).width;

  71.         int height = getBounds( ).height;

  72.         int w_Q = width / queens.at.length;

  73.         int h_Q = height / queens.at.length;

  74.         for(int col = queens.top; col < queens.at.length; ++col) {

  75.             for(int row = 0; row < queens.at.length; ++row) {

  76.                 if( !Main.isSafe(queens, row, col) )

  77.                     g.fill3DRect(col*w_Q, row*h_Q, w_Q, h_Q, true);

  78.             }

  79.         }

  80.         g.setComposite(oldC);

  81.     }



  82.     private void drawQueens(Graphics g) {

  83.         int width = getBounds( ).width;

  84.         int height = getBounds( ).height;

  85.         int w_Q = width / queens.at.length;

  86.         int h_Q = height / queens.at.length;

  87.         for(int col = 0; col < queens.top; ++col) {

  88.             drawQueen(g, col*w_Q, queens.at[col]*h_Q, w_Q, h_Q);

  89.         }

  90.     }



  91.     private void drawBoard(Graphics g2) {

  92.         Graphics2D g = (Graphics2D)g2;

  93.         int rule = AlphaComposite.SRC_OVER;

  94.         float alpha = 0.9f;

  95.         Composite oldC = g.getComposite( );

  96.         g.setComposite(AlphaComposite.getInstance(rule, alpha));

  97.         g.setPaint(Color.WHITE);

  98.         int width = getBounds( ).width;

  99.         int height = getBounds( ).height;

  100.         int w_Q = width / queens.at.length;

  101.         int h_Q = height / queens.at.length;

  102.         for(int col = 0; col < queens.at.length; ++col) {

  103.             for(int row = 0; row < queens.at.length; ++row) {

  104.                 //g.fillRect(col*w_Q, row*h_Q, w_Q, h_Q);

  105.                 g.fill3DRect(col*w_Q, row*h_Q, w_Q, h_Q, true);

  106.                 togglePen(g, Color.ORANGE );

  107.             }

  108.             togglePen(g, Color.ORANGE);

  109.         }

  110.         g.setComposite(oldC);

  111.     }



  112.     private void togglePen(Graphics g, Color clr) {

  113.         if( g.getColor( ) == Color.WHITE )

  114.             g.setColor(clr);

  115.         else

  116.             g.setColor(Color.WHITE);

  117.     }



  118.     private void drawQueen(Graphics g, int x, int y, int width, int height) {

  119.         Color oldPen = g.getColor( );

  120.         g.setColor(Color.BLUE);



  121.         g.fillArc ( x + width/8, y + 7*height/8, 3*width/4, height/4, 0, 180);



  122.         int lines = 16;

  123.         double xi = x + width/8.0;

  124.         double yi = y + height/2.0;

  125.         double step_x = 3.0*width/(4*lines);

  126.         double step_y = height/(2.0*lines);



  127.         g.drawLine((int)xi, (int)yi, (int)(xi+step_x), (int)( y+height-2) );

  128.         for(int i=0; i < lines/2; ++i) {

  129.             xi += step_x;   yi -= step_y;

  130.             g.drawLine((int)xi, (int)yi, (int)xi, (int)(y+height-2.0));

  131.         }

  132.         for(int i=1; i < lines/2; ++i) {

  133.             xi += step_x;   yi += step_y;

  134.             g.drawLine((int)xi, (int)yi, (int)xi, (int)(y+height-2.0));

  135.         }

  136.         xi += step_x;   yi += step_y;

  137.         g.drawLine((int)xi, (int)yi, (int)(xi-step_x), (int)(y+height-2.0));



  138.         g.setColor(oldPen);

  139.     }

  140. }

  141. public class Main extends JFrame {

  142.     Main( Locations Q ) {

  143.         enableEvents(AWTEvent.WINDOW_EVENT_MASK);

  144.         setLocation(100, 100);

  145.         setSize(640, 480);

  146.         setTitle("Eight Queens Problem (DFS using Backtracing)");

  147.         Board canvas = new Board ( Q );

  148.         button = new MyButton( );

  149.         buttonclk = new ActionListener() {



  150.             public void actionPerformed(ActionEvent e) {

  151.                     Main.go(true);

  152.                 Main.window.repaint( );

  153.             }

  154.         };

  155.         button.addActionListener(buttonclk);

  156.         setLayout(new BorderLayout( ));

  157.         add(canvas, BorderLayout.CENTER);

  158.         add(button, BorderLayout.SOUTH);



  159.         setVisible(true);

  160.     }



  161.     @Override

  162.     public void processWindowEvent( WindowEvent event ) {

  163.         if ( event.getID( ) == WindowEvent.WINDOW_CLOSING )

  164.             System.exit( 0 );

  165.     }



  166.     /**

  167.      * @param args the command line arguments

  168.      */

  169.     public static void main(String[] args) {

  170.         int size;

  171.         Scanner in = new Scanner(System.in);

  172.         System.out.println("Eight Queen Problem (DFS using Backtracing)");

  173.         //System.out.print("N : ");

  174.         //size = in.nextInt( );

  175.         //System.out.println("Wait .... ");

  176.         size = 8;

  177.         Locations queens = new Locations(size);             // stores row of queens

  178.         Main.solution = queens;

  179.         EventQueue.invokeLater(new Runnable() {



  180.             public void run() {

  181.                 Main.window = new Main(Main.solution);

  182.             }

  183.         });

  184.         Random dice = new Random(System.currentTimeMillis());

  185.         do {

  186.             int initial = dice.nextInt(size);

  187.             queens.at[(queens.top)++] = initial;

  188.         } while ( solve (queens, window) == false );



  189.         EventQueue.invokeLater(new Runnable() {



  190.             public void run() {

  191.                 Main.button.setText("D O N E");

  192.                 Main.button.removeActionListener(buttonclk);

  193.                 buttonclk = new ActionListener() {



  194.                     public void actionPerformed(ActionEvent e) {

  195.                         JOptionPane.showMessageDialog(null, "THANK YOU. source code at http://rooparam.blogspot.com",  "rooparam", JOptionPane.INFORMATION_MESSAGE);

  196.                     }

  197.                 };

  198.                 Main.button.addActionListener(buttonclk);

  199.             }

  200.         });



  201.         System.out.println("Positions of queens in Rows from left to right");

  202.         for ( int i=0; i< queens.at.length; ++i ) {

  203.             System.out.printf("%d  ", queens.at[i]);

  204.         }

  205.         System.out.println( );

  206.     }



  207.     private static boolean solve(Locations queens, Frame window) {

  208.         if(queens.top >= queens.at.length)

  209.             return true;

  210.        

  211.         Main.go(false);

  212.         while (!proceed) {

  213.             try {

  214.                 Thread.sleep(100);

  215.             } catch (InterruptedException ex) {

  216.                 Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex);

  217.             }

  218.         }

  219.         try {

  220.             EventQueue.invokeAndWait(new Runnable() {



  221.                 public void run() {

  222.                     Main.window.repaint();

  223.                 }

  224.             });

  225.         } catch (InterruptedException ex) {

  226.             Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex);

  227.         } catch (InvocationTargetException ex) {

  228.             Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex);

  229.         }



  230.         for(int i=0; i < queens.at.length; ++i) {

  231.             if ( isSafe ( queens, i, queens.top ) ) {

  232.                 queens.at[queens.top++] = i;

  233.                 if( solve ( queens, window) )

  234.                     return true;

  235.             }

  236.         }

  237.         queens.top--;

  238.         return false;

  239.     }



  240.     static boolean isSafe(Locations queens, int check, int col) {

  241.         for( int i=0; i < queens.top; ++i ) {

  242.             int col_i = i;

  243.             int row_i = queens.at[i];

  244.             int col_test = col;

  245.             int row_test = check;

  246.             // checking whether in same coloumn of in same row

  247.             if ( col_i == col_test || row_i == row_test )

  248.                 return false;

  249.             // digonal check

  250.             if ( ( col_i + row_i ) == ( col_test + row_test ) )

  251.                 return false;

  252.             if ( ( col_i - row_i ) == ( col_test - row_test ) )

  253.                 return false;

  254.         }

  255.         return true;

  256.     }



  257.     static boolean proceed = false;

  258.     static Frame window = null;

  259.     static Locations solution = null;



  260.     public static void go(boolean  b){

  261.         myLock.lock( );

  262.         try {

  263.             proceed = b;

  264.         } finally

  265.         {

  266.             myLock.unlock( );

  267.         }

  268.     }



  269.     public static final Lock myLock = new ReentrantLock( );

  270.     static MyButton button;

  271.     static ActionListener buttonclk;

  272. }



1 comment:

Anonymous said...

Good work

http://interviewpuzzle.blogspot.com