announcements‎ > ‎

2016-02-11 Knight's Tour *updated*

posted Feb 11, 2016, 11:23 AM by Samuel Konstantinovich   [ updated Feb 16, 2016, 8:39 AM ]
Your goal is to write a knight's tour solver. This is due the Tuesday after break.
Place it in your git repo:

./03*/KnightBoard.java

1. Assume all boards are square and write a solution as follows.

KnightBoard has 3 public methods that matter:
constrctor and two other methods
KnightBoard(int size) 
boolean solve()
void printSolution() //display a solution in the following format: 

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

Single spaces between numbers:
1 2 5
3 4 6
7 8 9

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

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






IMPORTANT UPDATE!
-You only have to step on every square exactly once, starting on the 1st square counts.
-You do not have to come back to where you started. This is called a closed tour (it is a loop that is closed) and closed tours take much longer to find (potentially).

Your tour should work on 5x5,6x6, and 7x7 easily.

MODIFICATION!
2. Allow for a construction of a rectangular board!

KnightBoard(int cols, int rows)

The other methods should still work correctly.

This means you can find more solutions without giant boards.

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 at least possible when none of those are true!!!!!

Test other sizes now:
3x5
3x7
5x6
etc.
Comments