Backtracking 8 Queens for JAVA


Buatkan dahulu Package = Aplikasi2,
Class = JRQueens;
Cara berjalan program.
Program akan mencari/menelusuri setiap kolom yang statusnya aman untuk meletakan Queen di posisinya, tanpa tertabrak dengan queen lainya...


package Aplikasi2;

import javax.swing.*; 
import java.awt.*; 
import java.awt.geom.*; 
import java.awt.event.*; 

public class JRQueens extends JFrame implements Runnable 
public ChessSquare [][] squares; 
public boolean [] saferow; // ini baris kosong.. antara true dan false
public boolean [] safeleftdiag; //  ini kirinya.. dari kanan atas ke kiri bawah
//  diagonal unthreatened true or false
public boolean [] saferightdiag; // ini kananya.. dari atas kiri ke kanan  bawah
// diagonal unthreatened? true or false 

private ShapePanel drawPanel; // panel untuk papan yang bisa ditarik - lihat detail
// class dibawah ini adalah kelas defini
private JLabel info; // info label
private JButton runDemo; // tombol untuk mengijinkan interaksi
private Thread runThread; // pergerakan motion
private int delay; // menunda pergerakan
private PauseClass pauser; // kelas untuk mengepause 
// solusi --  melihat rincian dalam definisi di bawah ini
private boolean paused; // eksekusi ditunda? false atau true
private int sol, calls; 

public JRQueens(int delta) 
super("Interactive 8 Queens Problem"); 
delay = delta; 
drawPanel = new ShapePanel(450, 450); 

runDemo = new JButton("See Solutions"); // Mengatur tombol
ButtonHandler bhandler = new ButtonHandler(); 
runDemo.addActionListener(bhandler); 

info = new JLabel("The 8 Queens Problem", (int) CENTER_ALIGNMENT); 

Container c = getContentPane(); // Mengatur tata letak
c.add(drawPanel, BorderLayout.CENTER); 
c.add(info, BorderLayout.NORTH); 
c.add(runDemo, BorderLayout.SOUTH); 

squares = new ChessSquare[8][8]; // menginisialisasi variabel
saferow = new boolean[8]; 
safeleftdiag = new boolean[15]; 
saferightdiag = new boolean[15]; 
int size = 50; 
int offset = 25; 
for (int row = 0; row < 8; row++) 
saferow[row] = true; // Mengatur baris
for (int col = 0; col < 8; col++) 
squares[row][col] = new ChessSquare(offset + col*size, 
offset + row*size, 
size, size); 

for (int i = 0; i < 15; i++) 
{ // menginisialisasi semua diagonal
safeleftdiag[i] = true; 
saferightdiag[i] = true; 
sol = 0; 
calls = 0; 

runThread = null; 

setSize(475, 525); 
setVisible(true); 

//Apakah lokasi saat ini? Kami memeriksa baris dan kedua diagonal.
//Kolom tidak harus diperiksa karena hasil algoritma kami
//cara Kolom ke kolom.
public boolean safe(int row, int col) 
return (saferow[row] && safeleftdiag[row+col] && 
saferightdiag[row-col+7]); 

//Metode rekursif melakukan sebagian besar pekerjaan untuk memecahkan masalah. Catatan
//Yang disebut untuk setiap kolom dieksekusi di papan
//Backtracking, secara keseluruhan akan juga berulang kali . Setiap panggilan adalah dari
//Titik pandang kolom saat ini,
public void trycol(int col) 
calls++; // kenaikan jumlah panggilan yang dibuat
for (int row = 0; row < 8; row++) // mencoba semua baris jika diperlukan
//Tes ini adalah test untuk memotong dari pohon eksekusi-
//Jika lokasinya tidak aman/sesuai kita tidak peduli untuk membuat rekursif
//Panggil dari posisi itu, menyelamatkan ribuan keseluruhan panggilan.
//Lihat catatan dari kelas untuk rincian.
if (safe(row, col)) 
// jika posisi saat ini bebas dari ancaman, letakan ratu
// disana menandai baris dan diags sebagai tidak aman

saferow[row] = false; 
safeleftdiag[row+col] = false; 
saferightdiag[row-col+7] = false; 
(squares[row][col]).occupy(); 
repaint(); 

if (col == 7)//Ratu aman di setiap kolom, informasi
{ // solusi dan pelaksanaan jeda
sol++; 
info.setText("Solution " + sol + " Found After " + calls + " Calls"); 
runDemo.setText("Click to Continue"); 
runDemo.setEnabled(true); 
pauser.pause(); 
else 
//Masih kolom yang tersisa untuk mengisi, sehingga menunda sebentar dan lanjut
//Mencoba kolom berikutnya secara rekursif
try 
Thread.sleep(delay); 
catch (InterruptedException e) 
System.out.println("Thread error B"); 

trycol(col+1); // mencoba untuk menempatkan seorang ratu ke kolom berikutnya

saferow[row] = true; // menghapus ratu
safeleftdiag[row+col] = true; // baris saat ini
saferightdiag[row-col+7] = true; // tidak di set untuk adanya ancaman
(squares[row][col]).remove(); // lingkaran kemudian akan mencoba
// berikutnya baris ke bawah
//Setelah semua baris sudah dicoba, selesai metode, dan pelaksanaan
//Backtracks ke panggilan sebelumnya.
}

//Metode ini dijalankan secara implisit ketika Topik dimulai. Perhatikan bahwa
//Kegiatan utamanya adalah panggilan trycol (0), yang memulai rekursif
//Algoritma dalam perjalanan.
public void run() 
paused = false; 
pauser = new PauseClass(); 
trycol(0); 
repaint(); 
info.setText("Program Completed: " + sol + " Solutions, " 
+ calls + " Calls, " 
+ (8*calls) + " iterations "); 

public static void main(String [] args) 
//Gunakan nilai delay yang dimasukkan oleh pengguna, atau menggunakan 100 jika tidak ada
//Nilai yang dimasukkan.
int delay; 
if (args != null && args.length >= 1) 
delay = Integer.parseInt(args[0]); 
else 
delay = 100; 
JRQueens win = new JRQueens(delay); 

win.addWindowListener( 
new WindowAdapter() 
public void windowClosing(WindowEvent e) 
{ System.exit(0); } 
); 

//Kelas ini digunakan untuk memungkinkan eksekusi untuk jeda antara
//Solusi. Rincian Java dari kelas ini harus dilakukan dengan monitor
//Dan disinkronisasi Threads dan berada di luar lingkup CS 1501
//Tentu saja. Namun, jika Anda tertarik untuk belajar lebih lanjut tentang
//Fitur Java, jangan ragu untuk melihat mereka di Java API.
private class PauseClass 
public synchronized void pause() 
paused = true; 
try 
wait(); 
catch (InterruptedException e) 
System.out.println("Pause Problem"); 

public synchronized void unpause() 
paused = false; 
notify(); 

//Kelas untuk menangani tombol. Untuk lebih lanjut tentang rincian Java,
private class ButtonHandler implements ActionListener 
public void actionPerformed(ActionEvent e) 
if (e.getSource() == runDemo) 
if (!paused) 
runDemo.setEnabled(false); 
info.setText("Searching for Solutions"); 
runThread = new Thread(JRQueens.this); 
runThread.start(); 
else 
runDemo.setEnabled(false); 
info.setText("Searching for Solutions"); 
pauser.unpause(); 
repaint(); 

//Kelas ini untuk mewakili persegi di papan tulis. Kelas ini meluas
//Rectangle2D.Double, yang dapat ditarik oleh grafis menarik () metode
//Dari kelas Graphics2D. Utama terbaru saya buat dalam subclass
//Variabel yang diduduki dan gambar dari Q jika ruang adalah
//Diduduki.
private class ChessSquare extends Rectangle2D.Double 
private boolean occupied; 

public ChessSquare(double x1, double y1, double wid, double hei) 
super(x1, y1, wid, hei); 
occupied = false; 

public void draw(Graphics2D g2d) 
g2d.draw(this); 
int x = (int) this.getX(); 
int y = (int) this.getY(); 
int sz = (int) this.getWidth(); 

if (occupied) 
g2d.setFont(new Font("Serif", Font.BOLD, 36)); 
g2d.drawString("Q", x+10, y+sz-10); 

public void occupy() 
occupied = true; 

public void remove() 
occupied = false; 

public boolean isOccupied() 
return occupied; 

//Kelas yang memungkinkan papan yang akan diberikan dengan cara yang baik.
//Lihat bahwa API Java atau buku yang bagus pada grafis Javaa untuk lebih
//Rincian tentang kelas ini.
private class ShapePanel extends JPanel 
private int prefwid, prefht; 

public ShapePanel (int pwid, int pht) 
prefwid = pwid; 
prefht = pht; 

public Dimension getPreferredSize() 
return new Dimension(prefwid, prefht); 

public void paintComponent (Graphics g) 
super.paintComponent(g); 
Graphics2D g2d = (Graphics2D) g; 
for (int i = 0; i < 8; i++) 
for (int j = 0; j < 8; j++) 
(squares[i][j]).draw(g2d); 
}




Posting Lebih Baru Posting Lama

Leave a Reply

Iklan

Diberdayakan oleh Blogger.

Search this blog