· 5 years ago · Oct 12, 2020, 12:00 AM
1//NQueens.java
2class NQueens {
3 /**squares per row or column */
4 private int BOARD_SIZE;
5 /** indicate an empty square */
6 public static final int EMPTY = 0;
7 /**indicate square contains a queen */
8 public static final int QUEEN = -1;
9 /** Chess Board: each entry <code>board[i][j]</code> of the board
10 * can take the following values:
11 * <li> QUEEN = -1 : indicating the presence of a queen
12 * <li> EMPTY = 0 : indicating an empty cell
13 * <li> <code>i>0</code> : where <code>i</code> number of queens that can
14 * attack the cell <code>(i,j)</code>
15 */
16 public int board[][];
17 /** current number of backtracks */
18 private int backTracks;
19 /** number of locations that have been checked to be under attack
20 * at some point in the search process */
21 private int isAttackedCalls;
22 /** current number of placed queens */
23 private int numPlacedQueens;
24
25
26 /** creates an empty square board */
27 public NQueens(int size) {
28 BOARD_SIZE = size;
29 board = new int[BOARD_SIZE][BOARD_SIZE];
30 backTracks = 0;
31 isAttackedCalls = 0;
32 numPlacedQueens = 0;
33 } // end constructor
34
35
36 /**
37 * Places queens by calling PlaceQueens with the first column.
38 * @return If a solution is found, each column of the board
39 * contains one queen and method returns true; otherwise,
40 * returns false (no solution exists for a queen anywhere
41 * in column specified).
42 */
43 public boolean placeQueens() {
44 return placeQueens(0);
45 }
46
47
48 /**
49 * Places queens in the specified column of the board and
50 * recursvily place the queens on the successive columns when
51 * possible
52 * @param column where the new queen is added. It is assumed that
53 * queens are correctly placed in columns <code>1</code> through
54 * <code>column-1</code>
55 * @return If a solution is found, each column of the board
56 * contains one queen and method returns true; otherwise, returns
57 * false (no solution exists for a queen anywhere in column
58 * specified).
59 */
60 private boolean placeQueens(int column) {
61 if (column == BOARD_SIZE) {
62 return true; // base case
63 }
64 else {
65 boolean queenPlaced = false;
66 int row = 0; // number of square in column
67 while ( !queenPlaced && (row < BOARD_SIZE) ) {
68 // if square can be attacked
69 if (isAttacked(row, column)) {
70 ++row; // consider next row in column
71 } // end if
72 else { // place queen and consider next column
73 setQueenAndMarks(row, column);
74 queenPlaced = placeQueens(column+1);
75 // if no queen can be placed in the next column,
76 if (!queenPlaced) {
77 // backtrack: remove queen placed earlier
78 // and try next row in column
79 removeQueenAndMarks(row, column);
80 ++row;
81 ++backTracks;
82 } // end if
83 } // end else
84 } // end while
85 return queenPlaced;
86 } // end else
87 } // end placeQueens
88
89
90 /**
91 * Sets a queen at the location indicated by the specified row and
92 * column and marks the columns attacked by this queen and no
93 * other queen placed in prior columns.
94 * Should call markBoard with appropriate arguments.
95 * @param row where the new queen is located
96 * @param column where the new queen is located
97 */
98 private void setQueenAndMarks(int row, int column) {
99
100
101 //given row and column where a queen is placed
102 //call upon it when setting queen
103
104 board [row][column] = QUEEN; //setting up the value
105
106
107 markBoard(row, column, EMPTY, column + 1); //call on mark board
108
109 //Using markboard as the collective process.
110
111
112
113
114 } // end setQueen
115
116
117 /**
118 * Removes a queen at the location indicated by row and column,
119 * and marks in the following columns to denote attack by this
120 * queen.
121 * <li> Precondition: A queen was placed in this position
122 * and it is being removed as part of the backtracking process.
123 * <li> Postcondition: Sets the square on the board in a given row and
124 * column to EMPTY. Also unmark all board positions attacked by
125 * this queen and not by any previous queens.
126 * Should call markBoard with appropriate arguments.
127 * @param row where the queen to be removed is located
128 * @param column where the queen to be removed is located
129 */
130 private void removeQueenAndMarks(int row, int column) {
131 // TO COMPLETE 2
132
133 markBoard(row, column, column + 1, EMPTY); //a queen was placed an now we have to remove it
134
135 board [row][column] = EMPTY;
136
137
138 } // end removeQueen
139
140
141
142
143 private void markBoard (int row, int column, int oldMarker, int newMarker){
144 markForward(row,column,1,oldMarker,newMarker);
145 }
146
147 /**
148 * Marks the column number <code>col+distance</code> to denote the
149 * location that can be attacked by the queen being placed. <li>
150 * Precondition: A queen was placed in the position (row, col) and
151 * the (col+distance)th column is being marked as part of the
152 * lookahead process. <li> Postcondition: Marks up to three
153 * squares on the board in column (col+distance). These squares are
154 * the one on the same row and the ones on the diagonals emanating
155 * from the queen placed at (row, col). Marks only those squares
156 * not marked by a previously placed queen.
157 * Calls itself recursively to mark the following columns.
158 * @param row where the new queen is located
159 * @param col where the new queen is located
160 * @param distance identifies the state of the markup process: the
161 * <code>col+distance</code> column will be marked up
162 * @param oldMarker identifies the old marker
163 * @param newMarker identifies the new marker
164 */
165
166
167 //-----------------------------------------------------------------------------------------------
168 private void markForward (int row, int col, int distance, int oldMarker, int newMarker) {
169 // TO COMPLETE MUST BE TAIL-RECURSIVE.
170
171
172
173
174
175
176
177
178
179
180
181
182 //-----------------------------------------------------------------------------------------------
183 }
184 /**
185 * Determines whether the square on the board at a given row and
186 * column is under attack by any queens in the columns 1 through
187 * column-1. <li> Precondition: Each column between 1 and
188 * column-1 has a queen placed in a square at a specific row.
189 * None of these queens can be attacked by any other queen.
190 * @param row of the considered square of the board
191 * @param column of the considered square of the board
192 * @return If the designated square is under attack, returns true;
193 * otherwise, returns false.
194 */
195 private boolean isAttacked(int row, int column) {
196 isAttackedCalls ++;
197 if (board[row][column]!= EMPTY)
198 return true;
199 else
200 return false;
201 } // end isAttacked
202
203 public String getStatsInHTML(){
204 return
205 "Statistics for NQueens on a "+BOARD_SIZE+" x "+BOARD_SIZE
206 +" chess board <br>"
207 +"Number of Back Tracks: "+backTracks +"<br>"
208 +"Number of isAttacked() calls : "+isAttackedCalls +"<br>"
209 +"Number of times Queens were placed: "+numPlacedQueens +"<br>";
210 }
211} // end NQueens
212
213////////////////////////////////////////////////////////////////////////////////////////////////////////////
214//NQueensGUI.java
215
216import java.awt.*;
217import java.awt.event.*;
218import javax.swing.*;
219import javax.swing.event.TableModelListener;
220import javax.swing.table.*;
221
222public class NQueensGUI implements ActionListener{
223 /** class that solves the NQueens problem */
224 NQueens nQueens;
225 /** Main frame that contains everything */
226 JFrame boardFrame;
227 /** Main panek that contains all the widgets */
228 JPanel boardPanel;
229 /** TextField to enter the size <code>N</code> of the chess board */
230 JTextField sizeField;
231 /** Label for the text field */
232 JLabel sizeLabel;
233 /** Button to launch the search of an assignment of the N queens
234 * on the chess board */
235 JButton placeButton;
236 /** model for the board represented by a Table*/
237 BoardModel bModel;
238 /** Jtable representing the chess board */
239 JTable board;
240 /** Label to indicates the status of the search */
241 JLabel statusLabel;
242 /** renderer to color the board */
243 TableCellRenderer renderer;
244 /** label to indicates the statistics of the resolution process */
245 JLabel statsLabel;
246
247 /** Constructor */
248 public NQueensGUI() {
249 JFrame.setDefaultLookAndFeelDecorated(true);
250 // create and set up the window
251 boardFrame = new JFrame("NQueens");
252 boardFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
253 // create and set up the pannel
254 boardPanel = new JPanel();
255 boardPanel.setOpaque(true);
256 // Add the widgets
257 addWidgets();
258 // Add the panel to the window.
259 boardFrame.getContentPane().add(boardPanel, BorderLayout.CENTER);
260 // Set the button to be default button in the frame.
261 boardFrame.getRootPane().setDefaultButton(placeButton);
262 // Display the window.
263 boardFrame.setSize(new Dimension(600, 600));
264 boardFrame.setVisible(true);
265 }
266
267 /** creates and adds all the widgets to the Panel */
268 public void addWidgets() {
269 // textfield to input N
270 sizeField = new JTextField(2);
271 sizeField.setHorizontalAlignment(JTextField.TRAILING);
272 sizeField.setSize(30, 10);
273 sizeLabel = new JLabel("number of queens");
274 // button to launch the resolution
275 placeButton = new JButton("Place queens");
276 placeButton.setSize(30, 20);
277 // status label
278 statusLabel = new JLabel();
279 statusLabel.setSize(40, 10);
280 // board
281 bModel = new BoardModel();
282 board = new JTable(bModel);
283 board.setGridColor(Color.CYAN);
284 board.setShowGrid(true);
285 board.setAutoResizeMode(JTable.AUTO_RESIZE_OFF);
286 JScrollPane scrollpane = new JScrollPane(board);
287 renderer = new CustomTableCellRenderer();
288 // label for the statistics of the resolution
289 statsLabel = new JLabel();
290 statsLabel.setHorizontalTextPosition(4);
291 board.setDefaultRenderer( Object.class, renderer );
292 // Listen to the events from the place queens button
293 placeButton.addActionListener(this);
294 // add the widget to the container
295 boardPanel.add(sizeLabel);
296 boardPanel.add(sizeField);
297 boardPanel.add(placeButton);
298 boardPanel.add(statusLabel);
299 boardPanel.add(scrollpane, BorderLayout.CENTER);
300 boardPanel.add(statsLabel);
301 }
302
303 /** action when the user click on the button to launch the
304 * resolution */
305 public void actionPerformed(ActionEvent event) {
306 // object for the model
307 Object[][] data = null;
308 statusLabel.setText("Computing ...");
309 bModel.update(data);
310 statsLabel.setText( "<html><font face='Verdana' color = 'gray'>"
311 + "<hr> Computing <hr><br>"
312 +"</font></html>");
313 statusLabel.repaint();
314 statsLabel.repaint();
315 board.repaint();
316 int size = Integer.parseInt(sizeField.getText());
317 // create the Queens
318 nQueens = new NQueens(size);
319 // get the current time
320
321 sizeField.setText("");
322 long cputime = 0, finish = 0, start = System.currentTimeMillis();
323 if (nQueens.placeQueens()) {// success!
324 finish = System.currentTimeMillis(); // get the current time
325 statusLabel.setText("<html><font face='Verdana' color = 'gray'>"
326 + "<br><br><br>A solution to "+size+" Queens"
327 +"</font></html>");
328 // statusLabel.setText("Solution Found");
329 data = new Object[size][size];
330 Object[] columnName = new String[size];
331 cputime = finish - start;
332 // prepare the table: leave blank where there is no queen
333 // write Q where there is a queen
334 for (int i = 0; i < size; i++) {
335 columnName[i] = Integer.toString(i);
336 for (int j = 0; j < size; j++)
337 if (nQueens.board[i][j] == NQueens.QUEEN)
338 data[i][j] = "Q";
339 else
340 data[i][j] = "";
341 }
342 }
343 else{ // failure no solution for NQueens was found!
344 data=null;
345 statusLabel.setText("No solution found!");
346 }
347 // update the GUI
348 bModel.update(data);
349 statsLabel.setText( "<html><font face='Verdana' color = 'gray'>"
350 + "CPU time =" +((float) cputime/1000)+ "sec<br>"
351 +nQueens.getStatsInHTML()
352 +"</font></html>");
353 this.board.repaint();
354 }
355
356 /** main */
357 public static void main(String[] args) {
358 JFrame.setDefaultLookAndFeelDecorated(true);
359 new NQueensGUI();
360 }
361
362 /** Model for the board */
363 public class BoardModel extends AbstractTableModel{
364 public Object[][] data;
365 public int getColumnCount(){
366 if (data!=null)
367 return data.length;
368 else
369 return 0;
370 }
371
372 public int getRowCount(){
373 if (data!=null)
374 return data.length;
375 else
376 return 0;
377 }
378
379 public Object getValueAt(int row, int col){
380 return data[row][col];
381 }
382
383 public void update(Object[][] objArray){
384 int oldSize = 0;
385 int newSize=0;
386 if (data != null)
387 oldSize = data.length;
388 if (objArray!=null)
389 newSize=objArray.length;
390 data = objArray;
391 if (newSize < oldSize)
392 fireTableRowsDeleted(newSize, oldSize-1);
393 if (newSize > oldSize)
394 fireTableRowsInserted(oldSize, newSize-1);
395 fireTableStructureChanged();
396 for (int i=0;i<newSize;i++)
397 for (int j=0;j<newSize;j++)
398 fireTableCellUpdated(i, j);
399 TableColumn column =null;
400 for (int i=0;i<newSize;i++){
401 column = board.getColumnModel().getColumn(i);
402 column.setPreferredWidth(10);
403 }
404 }
405 }// end Table Model
406
407 /** Renderer to color the table: cells containing a queen have a
408 * red background, the level of gray of the other cells depends on
409 * the number of queens that can attack the position: it is darker
410 * when more queens can attack the position.
411 *
412 * Warning: use the board of the NQueens class to know how many
413 * queens can attack a given location
414 */
415 public class CustomTableCellRenderer extends DefaultTableCellRenderer{
416 public Component getTableCellRendererComponent(JTable table,
417 Object value,
418 boolean isSelected,
419 boolean hasFocus,
420 int row, int column){
421 // obtain a cell
422 Component cell = super.getTableCellRendererComponent(table, value,
423 isSelected,
424 hasFocus,
425 row, column);
426 // color the cell
427 if (value instanceof String){
428 if (((String) value).equals("Q")) // it is a queen
429 cell.setBackground(Color.RED);
430 else{
431 int amount = nQueens.board[row][column];
432 Color c;
433 if (amount*15 <255)
434 c = new Color(0,0,0,amount*15);
435 else
436 c= Color.black;
437 cell.setBackground(c );
438 }
439 }
440 return cell;
441 }
442 }// end renderer class
443
444
445
446}// end PlaceQueens