Courses‎ > ‎AP Computer Science 2‎ > ‎Konstantinovich‎ > ‎

2017-02-08 HW02

posted Feb 8, 2017, 6:33 AM by Samuel Konstantinovich   [ updated Feb 14, 2017, 6:23 AM ]
HW02 on github: (due Tuesday!!!!! 8am)
02NQueens/QueenBoard.java

You should not write any code until you:
 - write pseudo-code written to outline your solving method. (the recursive helper not the wrapper) 
 - have 2 of your classmates read over your pseudo-code

public class QueenBoard{
    private int[][]board;
    private int solutionCount;

}

Discussion on what you need to have working

requirements: *see below*

Optional: Animation of nqueen solver (do this after you get the homework!)

You need a few public methods:
public void solve()  - find the 1st solution it can and stop, this updates the board to be displayed in toString()
public void countSolutions() - look for all solutions, and update the instance variable solutionCount to reflect the number found. 
public int getSolutionCount() - return the instance variable solutionCount, which should be -1 if the countSolutions was never run.
public String toString() - when solve was run, this shows you the solution, otherwise a blank board.

Constructor:
QueenBoard(int size)

Private methods you will want to test before writing other parts of the code:
addQueen(r,c)
removeQueen(r,c)

public class QueenBoard{
    private int[][]board;
    private int solutionCount;
    public QueenBoard(int size){
	board = new int[size][size];
    }

    /**
     *precondition: board is filled with 0's only.
     *@return false when the board is not solveable. true otherwise.
     *postcondition: 
     *if false: board is still filled with 0's
     *if true: board is filled with the 
     *final configuration of the board after adding 
     *all n queens. Uses solveH
     */
    public boolean solve()
    {
	return solveH(0);
    }

    private boolean solveH(int col){
	return false;
    }

    /**
     *@return the number of solutions found, or -1 if the board was never solved.
     *The board should be reset after this is run.    
     */
public int getSolutionCount(){ return -1; }
    /**toString
     *and all nunbers that represent queens are replaced with 'Q' 
     *all others are displayed as underscores '_'
     */
    public String toString(){
    	return "";
    }
}


 N queens number of solutions:
1 (N)1 (num solutions)
20
30
42
510
64
7 840 92
9352
10724

"Adequate"

Set moveCount to 1
FOR each row on the board {
    FOR each column on the board {
        IF gameBoard position (row, column) is occupied THEN {
            CALL findAdjacentTiles with row, column
            INCREMENT moveCount 
        }
    }
}

(Note: the logic is restructured to omit the "do nothing" clause) 


"Not So Good"

FOR all the number at the back of the array 
    SET Temp equal the addition of each number 
    IF > 9 THEN 
        get the remainder of the number divided by 10 to that index 
        and carry the "1" 
    Decrement one 
Do it again for numbers before the decimal 
 

Comments