Full Board is an interactive one-person puzzle/game by LightForce played on a rectangular grid. You can play the game here.

(Here is tester and required file file: https://drive.google.com/open?id=0B2gb5h869g2aR2V4Zko4VTlBckk )

The game starts with a board of M rows by N columns with some grid squares marked as obstacles (drawn as black dots). The player chooses a starting position to place a ball (marked S in the figure to the right) and chooses a direction to advance (left, right, up, or down). Once a direction is chosen, the ball will advance in that direction until it hits an obstacle, the boundary of the game board, or a square that the ball has already been through. The player then chooses another direction, and the ball will advance in the same manner. The game ends when no legal move can be made. The player wins if and only if the ball has traveled through all the empty grid squares on the board.

Tasks

You are to write a program that finds all of the paths that have a minimum number of steps needed to the game.

The program is similar to Rock and Roll Countdown in that it must have a main() method. When the unit tester is run,

The tester will invoke Main.main().

The tester will send your program the name of a file containing maps via the console.

Here is an example file. Each spot on a map is either an obstacle (, unicode "\u2593") or an empty space. The maxium dimensions of a map is 60 x 60.

Your program must read in the filename, then read the file, then parse and analyze each map. For each map, your program should output the following items (also note the example output listed below):

A line with the word map on it

A line with the minimum number of moves (or No solution, if there is none) required to win the game.

(if there is at least one solution).

A line with the word solution on it

The solved map. This includes an S where the solution starts, arrows that indicate the movement, and an F where the solution finishes. Note that the arrows must be , , , (unicode "\u219x", where x is 0, 1, 2, 3).

A line with the word endsolution on it.

If there is more than one solution, the next solution starts on the line after the previous solution's endsolution. Each solution is enclosed in solution/endsolution lines (see map 8 below).

Note: If there is more than one solution, sort the solutions lexicographically (a.k.a. alphabetically) in ascending order. To do this, you can simply convert each solution's 2D map into a 1D string (row major). Then sort the solutions in the same order as the strings would be sorted.

A line with the word endmap on it.

A line with the word Complete on it.

Formatting is important for the unit tester to function properly - no extra lines or spaces. Punctuation and capitalization matter.

If the filename the tester sends cannot be found, your program must print out:

File not found. Complete

*Before You Start Programming

On windows computers, the block character - -used in maps has to be saved as UTF-8. Solve this by going to: Window -> Preferences -> General -> Workspace : Text file encoding

*Suggestions

One approach to consider is to envision the set of possible board configurations as existing in a game tree, and to use a queue to keep track of configurations that haven't been investigated yet.

Non-Functional Requirements

NOTE: Naming is critical in the tasks and requirements described below. If the names don't match those described below exactly, your project will not compile and can't be graded.

Create a copy of the Java SE Project Template. The project name must follow this pattern: {FLname}_FullBoard_{TERM}, where {FLname} is replaced by the first letter of your first name plus your last name, and {TERM} is the semester and year. E.g. if your name is Maria Marciano and it's Spring of 2015, your project name must be MMarciano_FullBoard_S15.

Create a new package in the src folder called fullboard.

*Main class:

Create a Main class in the fullboard package. It must have a public static void main(String[] args). The unit tester will invoke this function when it tests your code.

*Testing

Create a new package in the src folder called sbccunittest.

Download FullBoardTester.java into the sbccunittest package.

Download edu.sbcc.cs145.fullboardri into lib folder of your project.

Right-click on edu.sbcc.cs145.fullboardri, then select Build Path | Add to Build Path.

*Sample Input and Output down below (input is blue, output is black):

smallmaps.txt map 9 moves solution   S  F   endsolution endmap map 17 moves solution   F   S    endsolution endmap map 10 moves solution   S   F  endsolution endmap map 11 moves solution  F  S    endsolution endmap map No solution                       endmap map 8 moves solution  S  F    endsolution endmap map No solution                endmap map 11 moves solution   F   S   endsolution solution    F S    endsolution endmap map 11 moves solution   S  F   endsolution endmap map 9 moves solution  F S     endsolution endmap map 9 moves solution    F  S  endsolution solution    F  S  endsolution endmap Complete