Courses‎ > ‎AP Computer Science 2‎ > ‎konstantinovich‎ > ‎

2018-02-13

posted Feb 13, 2018, 9:54 AM by Konstantinovich Samuel   [ updated Feb 13, 2018, 11:46 AM ]
The time for the Annual NYU trip is upon us. It will be Friday, March 2nd
This is a full day trip to NYU, where you listen to several interesting lectures by NYU CS professors. The topics are interesting, and food will be provided. It is not open to Seniors (sorry...)
Juniors ONLY:
1. Sign up by Thursday. (If you are late, you can't go. So do it early)
2. You will get forms via email. Return those by the Tuesday after break. (If you are late, we will take other people.)
If you sign up and do not show, you are taking a seat from another student, and that is not acceptable. 
If a situation arises where you cannot go: communicate with DW about it so that another student can be moved from the waitlist to the trip.



Your goal is to write a knight's tour solver. This is due the Wednesday after break.
Place it in your git repo:
03Knight/KnightBoard.java


KnightBoard has 3 public methods and a constructor, a private helper is needed as well.

@throws IllegalArgumentException when either parameter is negative.
public KnightBoard(int startingRows,int startingCols)
 
    Initialize the board to the correct size and make them all 0's 


public String toString() 
see format for toString below
blank boards display 0's as underscores 
you get a blank board if you never called solve or 
when there is no solution 

@throws IllegalStateException when the board contains non-zero values.
@throws IllegalArgumentException when either parameter is negative 
 or out of bounds.
public boolean solve(int startingRow, int startingCol)

@throws IllegalStateException when the board contains non-zero values. 
@throws IllegalArgumentException when either parameter is negative 
 or out of bounds.
public int countSolutions(int startingRow, int startingCol)

Suggestion:
private boolean solveH(int row ,int col, int level) 
// level is the # of the knight


*Use the following format for toString: 

(THESE ARE NOT VALID SOLUTIONS, They JUST TO DEMONSTRATE FORMAT)

Single spaces between numbers, but leading spaces on single digit numbers:
 1  2  5
 3  4  6
 7  8  9

Which is equivalant to: " 1  2  5\n 3  4  6\n 7  8  9\n"

When there are two digit numbers (rows*cols >= 10) Put a leading space in front of single digit numbers: 
(spaces replaced with to show the difference)
__2 15 _6
___7 11
_8 _9 10 12
13 14 _5 16

So it looks like this:
 1  2 15  6
 3  4  7 11
 8  9 10 12
13 14  5 16

*I will not be testing boards that have a rows*cols that is >= 100, as the program would take a long time to complete.




-You only have to step on every square exactly once, starting on the 1st square counts as step 1.

-You do not have to come back to where you started. That would be called is a closed tour (it is a loop that is closed) and closed tours take much longer to find (potentially).



From Wikipedia:

Any m × n board with m ≤ n, a closed knight's tour is always possible unless one or more of these three conditions are met:

  1. m and n are both odd
  2. m = 1, 2, or 4
  3. m = 3 and n = 4, 6, or 8.
 
This also means an open tour is certainly possible when none of those are true!!!!! 

Your solve should work on 7x7 easily.
Comments