Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

2019-02-12 Knights

posted Feb 12, 2019, 6:06 AM by Konstantinovich Samuel   [ updated Feb 13, 2019, 11:34 AM ]
Goal : Solve a knights tour

The time for the Annual NYU trip is upon us!
Friday March 1st will be is a full day trip to NYU, where you listen to several interesting lectures by NYU CS professors. The topics are varied, and food will be provided. It is not open to Seniors (sorry...)

Juniors ONLY:
1. Sign up by Friday morning. (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. 
IMPORTANT: If a situation arises where you cannot go you must communicate with DW about it so that another student can be moved from the waitlist to the trip.

On behalf of the CCC:

Hey folks!
My name is Joan Chirinos, and I'm the president of the Stuy Competitive Computing Club.

"What's the Competitive Computing Club???"

Good question! As upperclassmen, we will teach you how to use your rad CS skills to solve the problems typically found in CS competitions. We will also use this knowledge in a number of fun activities, including mini-competitions! With your immense knowledge, you can even go to PClassic or SJC, larger and more structured CS competitions!

If this sounds interesting to you, please fill out the form below. I will be emailing you shortly about our first meeting!

Knights Tour:

The chess knight can move in the following manner:

A knights tour:

Selecting a series of moves for a knight such that each square is visited exactly once. If the knight ends on a square that is reachable by a knight's move from the beginning square, the tour is closed, otherwise it is open. The image below is an open tour.

We represent this with numbers from 1 to K , where K is the area of the board.
(this is not the same solution as above)

-The board dimensions do not have to be square.
-The starting square counts as visited.
-You do not have to come back to where you started. Closed tours take much longer to find (potentially).

Not all board sizes have solutions. A 2 by N board has no closed or open tour.
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.

It follows that if a closed tour is possible, then an open tour is also possible.

There are about 10^15 open tours on a standard size chessboard.... Counting them would not be possible. Finding one solution should be.

solve(startRow,StartCol) : 
    should work on boards where the number of squares is under 100.

countSolutions(startRow,StartCol) : 
    would only work on smaller boards! The exact sizes will be determined later.

Discussion of how to make this faster:
brute force vs heuristics

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

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

1 Constructor
@throws IllegalArgumentException when either parameter is <= 0.
public KnightBoard(int rows,int cols)
    Initialize the board to the correct size and make them all 0's 

2 toString
-you get a blank board if you never called solve or when there is no solution 
-blank boards display 0's as underscores 
@returns the properly formatted string (see format for toString later in the post)
public String toString() 

3 solve
Modifies the board by labeling the moves from 1 (at startingRow,startingCol) up to the area of the board in proper knight move steps.
@throws IllegalStateException when the board contains non-zero values.
@throws IllegalArgumentException when either parameter is negative 
 or out of bounds.
@returns true when the board is solvable from the specified starting position
public boolean solve(int startingRow, int startingCol)

4 countSolutions
@throws IllegalStateException when the board contains non-zero values. 
@throws IllegalArgumentException when either parameter is negative 
 or out of bounds.
@returns the number of solutions from the starting position specified
public int countSolutions(int startingRow, int startingCol)

private boolean solveH(int row ,int col, int moveNumber) 

*Use the following format for toString: 


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.