- package eight_queen;
- import java.awt.AWTEvent;
- import java.awt.AlphaComposite;
- import java.awt.BorderLayout;
- import java.awt.Color;
- import java.awt.Composite;
- import java.awt.EventQueue;
- import java.awt.Frame;
- import java.awt.Graphics;
- import java.awt.Graphics2D;
- import java.awt.Image;
- import java.awt.Toolkit;
- import java.awt.event.ActionEvent;
- import java.awt.event.ActionListener;
- import java.awt.event.WindowEvent;
- import java.lang.reflect.InvocationTargetException;
- import java.util.Random;
- import java.util.Scanner;
- import java.util.concurrent.locks.Lock;
- import java.util.concurrent.locks.ReentrantLock;
- import java.util.logging.Level;
- import java.util.logging.Logger;
- import javax.swing.JButton;
- import javax.swing.JFrame;
- import javax.swing.JOptionPane;
- import javax.swing.JPanel;
- /**
- *
- * @author rooparam
- */
- class Locations {
- public Locations(int size ) {
- at = new int[size];
- top = 0; // next coloumn of a queen
- }
- public int top;
- public int[] at;
- }
-
- MyButton( ) {
- super("continue");
- }
- }
-
- Board ( Locations Q ) {
- queens = Q;
- //setSize(640, 480);
-
- }
- @Override
-
-
- g.drawImage(image, 0, 0, getBounds().width, getBounds().height, this);
- drawBoard ( g );
- drawQueens(g);
- drawRemaining(g);
-
-
- g.drawString(str, getBounds().width - 180, getBounds().height - 10);
- }
- private Locations queens;
-
-
-
- float alpha = 0.8f;
-
-
-
- int width = getBounds( ).width;
- int height = getBounds( ).height;
- int w_Q = width / queens.at.length;
- int h_Q = height / queens.at.length;
- for(int col = queens.top; col < queens.at.length; ++col) {
- for(int row = 0; row < queens.at.length; ++row) {
- if( !Main.isSafe(queens, row, col) )
- g.fill3DRect(col*w_Q, row*h_Q, w_Q, h_Q, true);
- }
- }
- g.setComposite(oldC);
- }
-
- int width = getBounds( ).width;
- int height = getBounds( ).height;
- int w_Q = width / queens.at.length;
- int h_Q = height / queens.at.length;
- for(int col = 0; col < queens.top; ++col) {
- drawQueen(g, col*w_Q, queens.at[col]*h_Q, w_Q, h_Q);
- }
- }
-
-
-
- float alpha = 0.9f;
-
-
-
- int width = getBounds( ).width;
- int height = getBounds( ).height;
- int w_Q = width / queens.at.length;
- int h_Q = height / queens.at.length;
- for(int col = 0; col < queens.at.length; ++col) {
- for(int row = 0; row < queens.at.length; ++row) {
- //g.fillRect(col*w_Q, row*h_Q, w_Q, h_Q);
- g.fill3DRect(col*w_Q, row*h_Q, w_Q, h_Q, true);
-
- }
-
- }
- g.setComposite(oldC);
- }
-
-
- g.setColor(clr);
- else
-
- }
-
-
-
- g.fillArc ( x + width/8, y + 7*height/8, 3*width/4, height/4, 0, 180);
- int lines = 16;
- double xi = x + width/8.0;
- double yi = y + height/2.0;
- double step_x = 3.0*width/(4*lines);
- double step_y = height/(2.0*lines);
- g.drawLine((int)xi, (int)yi, (int)(xi+step_x), (int)( y+height-2) );
- for(int i=0; i < lines/2; ++i) {
- xi += step_x; yi -= step_y;
- g.drawLine((int)xi, (int)yi, (int)xi, (int)(y+height-2.0));
- }
- for(int i=1; i < lines/2; ++i) {
- xi += step_x; yi += step_y;
- g.drawLine((int)xi, (int)yi, (int)xi, (int)(y+height-2.0));
- }
- xi += step_x; yi += step_y;
- g.drawLine((int)xi, (int)yi, (int)(xi-step_x), (int)(y+height-2.0));
- g.setColor(oldPen);
- }
- }
-
- Main( Locations Q ) {
-
- setLocation(100, 100);
- setSize(640, 480);
- setTitle("Eight Queens Problem (DFS using Backtracing)");
- Board canvas = new Board ( Q );
- button = new MyButton( );
-
-
- Main.go(true);
- Main.window.repaint( );
- }
- };
- button.addActionListener(buttonclk);
-
-
-
- setVisible(true);
- }
- @Override
-
-
-
- }
- /**
- * @param args the command line arguments
- */
-
- int size;
-
-
- //System.out.print("N : ");
- //size = in.nextInt( );
- //System.out.println("Wait .... ");
- size = 8;
- Locations queens = new Locations(size); // stores row of queens
- Main.solution = queens;
-
- public void run() {
- Main.window = new Main(Main.solution);
- }
- });
-
- do {
- int initial = dice.nextInt(size);
- queens.at[(queens.top)++] = initial;
- } while ( solve (queens, window) == false );
-
- public void run() {
- Main.button.setText("D O N E");
- Main.button.removeActionListener(buttonclk);
-
-
- JOptionPane.showMessageDialog(null, "THANK YOU. source code at http://rooparam.blogspot.com", "rooparam", JOptionPane.INFORMATION_MESSAGE);
- }
- };
- Main.button.addActionListener(buttonclk);
- }
- });
-
- for ( int i=0; i< queens.at.length; ++i ) {
-
- }
-
- }
-
- if(queens.top >= queens.at.length)
- return true;
- Main.go(false);
- while (!proceed) {
- try {
-
-
- Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex);
- }
- }
- try {
-
- public void run() {
- Main.window.repaint();
- }
- });
-
- Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex);
-
- Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex);
- }
- for(int i=0; i < queens.at.length; ++i) {
- if ( isSafe ( queens, i, queens.top ) ) {
- queens.at[queens.top++] = i;
- if( solve ( queens, window) )
- return true;
- }
- }
- queens.top--;
- return false;
- }
- static boolean isSafe(Locations queens, int check, int col) {
- for( int i=0; i < queens.top; ++i ) {
- int col_i = i;
- int row_i = queens.at[i];
- int col_test = col;
- int row_test = check;
- // checking whether in same coloumn of in same row
- if ( col_i == col_test || row_i == row_test )
- return false;
- // digonal check
- if ( ( col_i + row_i ) == ( col_test + row_test ) )
- return false;
- if ( ( col_i - row_i ) == ( col_test - row_test ) )
- return false;
- }
- return true;
- }
- static boolean proceed = false;
-
- static Locations solution = null;
- public static void go(boolean b){
- myLock.lock( );
- try {
- proceed = b;
- } finally
- {
- myLock.unlock( );
- }
- }
- public static final Lock myLock = new ReentrantLock( );
- static MyButton button;
-
- }
Tuesday, December 1, 2009
Eight Queens Solution with DFS using Backtracking (Step-by-step simulation)
Subscribe to:
Post Comments (Atom)
1 comment:
Good work
http://interviewpuzzle.blogspot.com
Post a Comment