· 5 years ago · Oct 11, 2020, 03:54 AM
1//YOU WILL MODIFY THIS
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 // TO COMPLETE
100 } // end setQueen
101
102
103 /**
104 * Removes a queen at the location indicated by row and column,
105 * and marks in the following columns to denote attack by this
106 * queen.
107 * <li> Precondition: A queen was placed in this position
108 * and it is being removed as part of the backtracking process.
109 * <li> Postcondition: Sets the square on the board in a given row and
110 * column to EMPTY. Also unmark all board positions attacked by
111 * this queen and not by any previous queens.
112 * Should call markBoard with appropriate arguments.
113 * @param row where the queen to be removed is located
114 * @param column where the queen to be removed is located
115 */
116 private void removeQueenAndMarks(int row, int column) {
117 // TO COMPLETE
118 } // end removeQueen
119
120 private void markBoard (int row, int column, int oldMarker, int newMarker){
121 markForward(row,column,1,oldMarker,newMarker);
122 }
123
124 /**
125 * Marks the column number <code>col+distance</code> to denote the
126 * location that can be attacked by the queen being placed. <li>
127 * Precondition: A queen was placed in the position (row, col) and
128 * the (col+distance)th column is being marked as part of the
129 * lookahead process. <li> Postcondition: Marks up to three
130 * squares on the board in column (col+distance). These squares are
131 * the one on the same row and the ones on the diagonals emanating
132 * from the queen placed at (row, col). Marks only those squares
133 * not marked by a previously placed queen.
134 * Calls itself recursively to mark the following columns.
135 * @param row where the new queen is located
136 * @param col where the new queen is located
137 * @param distance identifies the state of the markup process: the
138 * <code>col+distance</code> column will be marked up
139 * @param oldMarker identifies the old marker
140 * @param newMarker identifies the new marker
141 */
142 private void markForward (int row, int col, int distance,
143 int oldMarker, int newMarker) {
144 // TO COMPLETE
145 }
146 /**
147 * Determines whether the square on the board at a given row and
148 * column is under attack by any queens in the columns 1 through
149 * column-1. <li> Precondition: Each column between 1 and
150 * column-1 has a queen placed in a square at a specific row.
151 * None of these queens can be attacked by any other queen.
152 * @param row of the considered square of the board
153 * @param column of the considered square of the board
154 * @return If the designated square is under attack, returns true;
155 * otherwise, returns false.
156 */
157 private boolean isAttacked(int row, int column) {
158 isAttackedCalls ++;
159 if (board[row][column]!= EMPTY)
160 return true;
161 else
162 return false;
163 } // end isAttacked
164
165 public String getStatsInHTML(){
166 return
167 "Statistics for NQueens on a "+BOARD_SIZE+" x "+BOARD_SIZE
168 +" chess board <br>"
169 +"Number of Back Tracks: "+backTracks +"<br>"
170 +"Number of isAttacked() calls : "+isAttackedCalls +"<br>"
171 +"Number of times Queens were placed: "+numPlacedQueens +"<br>";
172 }
173} // end NQueens
174
175/////////////////////////////////////////////////////////////////////////////////////
176
177import java.awt.*;
178import java.awt.event.*;
179import javax.swing.*;
180import javax.swing.event.TableModelListener;
181import javax.swing.table.*;
182
183public class NQueensGUI implements ActionListener{
184 /** class that solves the NQueens problem */
185 NQueens nQueens;
186 /** Main frame that contains everything */
187 JFrame boardFrame;
188 /** Main panek that contains all the widgets */
189 JPanel boardPanel;
190 /** TextField to enter the size <code>N</code> of the chess board */
191 JTextField sizeField;
192 /** Label for the text field */
193 JLabel sizeLabel;
194 /** Button to launch the search of an assignment of the N queens
195 * on the chess board */
196 JButton placeButton;
197 /** model for the board represented by a Table*/
198 BoardModel bModel;
199 /** Jtable representing the chess board */
200 JTable board;
201 /** Label to indicates the status of the search */
202 JLabel statusLabel;
203 /** renderer to color the board */
204 TableCellRenderer renderer;
205 /** label to indicates the statistics of the resolution process */
206 JLabel statsLabel;
207
208 /** Constructor */
209 public NQueensGUI() {
210 JFrame.setDefaultLookAndFeelDecorated(true);
211 // create and set up the window
212 boardFrame = new JFrame("NQueens");
213 boardFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
214 // create and set up the pannel
215 boardPanel = new JPanel();
216 boardPanel.setOpaque(true);
217 // Add the widgets
218 addWidgets();
219 // Add the panel to the window.
220 boardFrame.getContentPane().add(boardPanel, BorderLayout.CENTER);
221 // Set the button to be default button in the frame.
222 boardFrame.getRootPane().setDefaultButton(placeButton);
223 // Display the window.
224 boardFrame.setSize(new Dimension(600, 600));
225 boardFrame.setVisible(true);
226 }
227
228 /** creates and adds all the widgets to the Panel */
229 public void addWidgets() {
230 // textfield to input N
231 sizeField = new JTextField(2);
232 sizeField.setHorizontalAlignment(JTextField.TRAILING);
233 sizeField.setSize(30, 10);
234 sizeLabel = new JLabel("number of queens");
235 // button to launch the resolution
236 placeButton = new JButton("Place queens");
237 placeButton.setSize(30, 20);
238 // status label
239 statusLabel = new JLabel();
240 statusLabel.setSize(40, 10);
241 // board
242 bModel = new BoardModel();
243 board = new JTable(bModel);
244 board.setGridColor(Color.CYAN);
245 board.setShowGrid(true);
246 board.setAutoResizeMode(JTable.AUTO_RESIZE_OFF);
247 JScrollPane scrollpane = new JScrollPane(board);
248 renderer = new CustomTableCellRenderer();
249 // label for the statistics of the resolution
250 statsLabel = new JLabel();
251 statsLabel.setHorizontalTextPosition(4);
252 board.setDefaultRenderer( Object.class, renderer );
253 // Listen to the events from the place queens button
254 placeButton.addActionListener(this);
255 // add the widget to the container
256 boardPanel.add(sizeLabel);
257 boardPanel.add(sizeField);
258 boardPanel.add(placeButton);
259 boardPanel.add(statusLabel);
260 boardPanel.add(scrollpane, BorderLayout.CENTER);
261 boardPanel.add(statsLabel);
262 }
263
264 /** action when the user click on the button to launch the
265 * resolution */
266 public void actionPerformed(ActionEvent event) {
267 // object for the model
268 Object[][] data = null;
269 statusLabel.setText("Computing ...");
270 bModel.update(data);
271 statsLabel.setText( "<html><font face='Verdana' color = 'gray'>"
272 + "<hr> Computing <hr><br>"
273 +"</font></html>");
274 statusLabel.repaint();
275 statsLabel.repaint();
276 board.repaint();
277 int size = Integer.parseInt(sizeField.getText());
278 // create the Queens
279 nQueens = new NQueens(size);
280 // get the current time
281
282 sizeField.setText("");
283 long cputime = 0, finish = 0, start = System.currentTimeMillis();
284 if (nQueens.placeQueens()) {// success!
285 finish = System.currentTimeMillis(); // get the current time
286 statusLabel.setText("<html><font face='Verdana' color = 'gray'>"
287 + "<br><br><br>A solution to "+size+" Queens"
288 +"</font></html>");
289 // statusLabel.setText("Solution Found");
290 data = new Object[size][size];
291 Object[] columnName = new String[size];
292 cputime = finish - start;
293 // prepare the table: leave blank where there is no queen
294 // write Q where there is a queen
295 for (int i = 0; i < size; i++) {
296 columnName[i] = Integer.toString(i);
297 for (int j = 0; j < size; j++)
298 if (nQueens.board[i][j] == NQueens.QUEEN)
299 data[i][j] = "Q";
300 else
301 data[i][j] = "";
302 }
303 }
304 else{ // failure no solution for NQueens was found!
305 data=null;
306 statusLabel.setText("No solution found!");
307 }
308 // update the GUI
309 bModel.update(data);
310 statsLabel.setText( "<html><font face='Verdana' color = 'gray'>"
311 + "CPU time =" +((float) cputime/1000)+ "sec<br>"
312 +nQueens.getStatsInHTML()
313 +"</font></html>");
314 this.board.repaint();
315 }
316
317 /** main */
318 public static void main(String[] args) {
319 JFrame.setDefaultLookAndFeelDecorated(true);
320 new NQueensGUI();
321 }
322
323 /** Model for the board */
324 public class BoardModel extends AbstractTableModel{
325 public Object[][] data;
326 public int getColumnCount(){
327 if (data!=null)
328 return data.length;
329 else
330 return 0;
331 }
332
333 public int getRowCount(){
334 if (data!=null)
335 return data.length;
336 else
337 return 0;
338 }
339
340 public Object getValueAt(int row, int col){
341 return data[row][col];
342 }
343
344 public void update(Object[][] objArray){
345 int oldSize = 0;
346 int newSize=0;
347 if (data != null)
348 oldSize = data.length;
349 if (objArray!=null)
350 newSize=objArray.length;
351 data = objArray;
352 if (newSize < oldSize)
353 fireTableRowsDeleted(newSize, oldSize-1);
354 if (newSize > oldSize)
355 fireTableRowsInserted(oldSize, newSize-1);
356 fireTableStructureChanged();
357 for (int i=0;i<newSize;i++)
358 for (int j=0;j<newSize;j++)
359 fireTableCellUpdated(i, j);
360 TableColumn column =null;
361 for (int i=0;i<newSize;i++){
362 column = board.getColumnModel().getColumn(i);
363 column.setPreferredWidth(10);
364 }
365 }
366 }// end Table Model
367
368 /** Renderer to color the table: cells containing a queen have a
369 * red background, the level of gray of the other cells depends on
370 * the number of queens that can attack the position: it is darker
371 * when more queens can attack the position.
372 *
373 * Warning: use the board of the NQueens class to know how many
374 * queens can attack a given location
375 */
376 public class CustomTableCellRenderer extends DefaultTableCellRenderer{
377 public Component getTableCellRendererComponent(JTable table,
378 Object value,
379 boolean isSelected,
380 boolean hasFocus,
381 int row, int column){
382 // obtain a cell
383 Component cell = super.getTableCellRendererComponent(table, value,
384 isSelected,
385 hasFocus,
386 row, column);
387 // color the cell
388 if (value instanceof String){
389 if (((String) value).equals("Q")) // it is a queen
390 cell.setBackground(Color.RED);
391 else{
392 int amount = nQueens.board[row][column];
393 Color c;
394 if (amount*15 <255)
395 c = new Color(0,0,0,amount*15);
396 else
397 c= Color.black;
398 cell.setBackground(c );
399 }
400 }
401 return cell;
402 }
403 }// end renderer class
404
405
406
407}// end PlaceQueens