Recursion Project
COP-3223H

The program will input a maze as a two-dimensional 9x9 character array, e.g.,

 _________ 
|    # ###|
|### #   #|
|  # ### #|
| ##     #|
|  # #####|
|# # ##   |
|# # ## # |
|#      # |
|  ###### |
 ^^^^^^^^^ 

where spaces (' ') represent viable paths and hashes ('#') represent impassable walls. The border characters (|, _, ^) are not part of the character array; they are just to improve visibility of space characters.

The goal is find a path from index (0,0), which is always the starting point, to index (8,8), which is always the end point. You can only move up, down, left, or right, not diagonally.

Draw the path using dots ('.'), e.g,

 _________ 
|....# ###|
|###.#   #|
|  #.### #|
| ##.    #|
|  #.#####|
|# #.##...|
|# #.##.#.|
|#  ....#.|
|  ######.|
 ^^^^^^^^^ 

Again, the border characters (|, _, ^) are not part of the character array; they are just to improve visibility of space characters.

The program will input a text file holding the characters of the 9x9 character array, for instance, maze1.txt. To download the example, you can use the following command on eustis from within your project directory.

wget https://www.cs.ucf.edu/~gazzillo/teaching/cop3223hspring26/files/maze1.txt

Input the program by running it, passing in the maze file like this (once your program is compiled):

./recursion < maze1.txt

The output should be the solved puzzle. You will only be tested on puzzles that have a single path to the goal and empty spaces at (0,0) and (9,9). The last thing printed should be the solved puzzle and the border characters will be filtered out before checking for grading correctness.

 _________ 
|....# ###|
|###.#   #|
|  #.### #|
| ##.    #|
|  #.#####|
|# #.##...|
|# #.##.#.|
|#  ....#.|
|  ######.|
 ^^^^^^^^^ 

The algorithm uses the same strategy as the eight queens puzzle solver.

• Start by placing a dot on (0,0), the starting position.
• Then, for whatever position you are currently on, recursively try all four directions: up, down, left, right.
  • For each position, check whether the position is (1) within the boundary of the maze, (2) is a space (not a hash), and (3) has not yet been traversed with a dot.
  • If successful, then recursively try continuing to places dots along the path
  • Once done trying the paths, remove the dot (replacing it with space), in order to continue searching for a path. This is the backtracking part of the recursion.
• One you have reached (8,8) and placed on dot on this position, print the board.

The following is template code that provides code to process maze input and output. The solve function is where you can implement your solver. Feel free to define other helper functions if you like.

#include <stdio.h>
#include <assert.h>

void draw(char maze[9][9]);

void solve(char maze[9][9], int x, int y);

void draw(char maze[9][9]) {
  putchar(' ');
  for (int i = 0; i < 9; i++) {
    putchar('_');
  }
  putchar(' ');
  putchar('\n');
  for (int i = 0; i < 9; i++) {
    putchar('|');
    for (int j = 0; j < 9; j++) {
      printf("%c", maze[i][j]);
    }
    putchar('|');
    putchar('\n');
  }
  putchar(' ');
  for (int i = 0; i < 9; i++) {
    putchar('^');
  }
  putchar(' ');
  putchar('\n');
}

void solve(char maze[9][9], int x, int y) {
  // TODO: implement recursive backtracking maze solver that places
  // dots ('.') along the path and prints the solved puzzle using draw(maze)
}

int main(int argc, char **argv) {
  // example maze
  char maze[9][9] = { {' ', ' ', ' ', ' ', '#', ' ', '#', '#', '#'},
                      {'#', '#', '#', ' ', '#', ' ', ' ', ' ', '#'},
                      {' ', ' ', '#', ' ', '#', '#', '#', ' ', '#'},
                      {' ', '#', '#', ' ', ' ', ' ', ' ', ' ', '#'},
                      {' ', ' ', '#', ' ', '#', '#', '#', '#', '#'},
                      {'#', ' ', '#', ' ', '#', '#', ' ', ' ', ' '},
                      {'#', ' ', '#', ' ', '#', '#', ' ', '#', ' '},
                      {'#', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' '},
                      {' ', ' ', '#', '#', '#', '#', '#', '#', ' '} };

  // read maze from file (overwrites current maze)
  char c;
  for (int i = 0; i < 9; i++) {
    for (int j = 0; j < 9; j++) {
      scanf("%c", &c);
      maze[i][j] = c;
    }
    scanf("%c", &c);
    assert('\n' == c);
  }

  // draw empty maze
  draw(maze);
  solve(maze, 0, 0);
}

The program must be called recursion.c and must be in the recursion directory, i.e., the full path should be

~/cop3223spring26/assignments/recursion/recursion.c

Compile and run the program whenever you make changes using

cd ~/cop3223spring26/assignments/recursion/
gcc -o recursion recursion.c
./recursion

Be sure there is no other output besides the required output as the grading will be automatic. If you would like to have debugging output, use fprintf(stderr, "...", ...); instead of printf.

Download the example program. This only needs to be done once.

wget https://www.cs.ucf.edu/~gazzillo/teaching/cop3223hspring26/files/maze1.txt

Check the maze file:

cat maze1.txt

    # ###
### #   #
  # ### #
 ##     #
  # #####
# # ##   
# # ## # 
#      # 
  ###### 

Run your program, inputting the maze.

./recursion < maze1.txt

The program template prints the empty maze first. Then, if your program is correctly implemented, it should also print the solved maze.

 _________ 
|    # ###|
|### #   #|
|  # ### #|
| ##     #|
|  # #####|
|# # ##   |
|# # ## # |
|#      # |
|  ###### |
 ^^^^^^^^^ 
 _________ 
|....# ###|
|###.#   #|
|  #.### #|
| ##.    #|
|  #.#####|
|# #.##...|
|# #.##.#.|
|#  ....#.|
|  ######.|
 ^^^^^^^^^ 

Enter

git add recursion.c
git commit recursion.c

Write an appropriate commit message. Remember that you will need to save (Ctrl-x Ctrl-s) then quit (Ctrl-x Ctrl-c) the emacs editor that pops up. If you are having trouble, be sure that you have completed the git project first.

Do not commit the backup file recursion.c~ nor the recursion program. Use a .gitignore file to exclude those from the repository, so they won't show up when you type git status.

Then to synchronize the changes to the remote git repository on the grading server:

git push

If you have already run the self-check, you can remove it like this

rm -rf ~/tmp/assignments_selfcheck

Double-check the path carefully to avoid deleting the wrong directory.

git clone gitolite3@eustis3.eecs.ucf.edu:cop3223/$USER/assignments ~/tmp/assignments_selfcheck

You should see something like

Cloning into '/home/net/NID/tmp/assignments_selfcheck'...

Welcome to eustis.eecs.ucf.edu.

Please use your NID and NID password to log in.

See http://t.cs.ucf.edu/help/eustis  for additional instructions.

remote: Enumerating objects: 16, done.
remote: Counting objects: 100% (16/16), done.
remote: Compressing objects: 100% (12/12), done.
remote: Total 16 (delta 1), reused 0 (delta 0), pack-reused 0
Receiving objects: 100% (16/16), done.
Resolving deltas: 100% (1/1), done.

If you see

fatal: destination path '/home/net/NID/tmp/assignments_selfcheck already exists and is not an empty directory.

then remove the previous self-check.