Programming assignment: Recursive L-Shape Square Filling
|
Recursive L-Shape Square Filling This programming assignment provides an opportunity to practice writing recursive functions to solve a challenging puzzle. You will implement a C++ program to fill in L-shapes in a square with exactly one hole (empty cell). |
|
Introduction Recursion is a powerful programming technique where a function calls itself. It is well-suited for solving problems that can be broken down into smaller subproblems of the same type. To solve a recursive problem, it is important to define the following: |
-
Base case: a condition in the recursive function that does not lead to further recursive calls. It's a scenario where the problem can be solved without further recursion.
-
General (Recursive) case: the part of the function that includes the recursive call. It should break down the problem into smaller, simpler instances of the same problem.
-
Progress towards the base case: each recursive call should bring you closer to the base case. If it doesn't, the recursion could go on indefinitely and cause a stack overflow.
|
You may consider splitting filling the whole square into subproblems such as |
|
filling subsquares. Upon completing this project assignment, you will achieve the following learning outcomes: |
-
Proficiency in utilizing recursion to solve complex programming problems.
-
Mastery of data structures, such as 2-D arrays, to represent and manipulate
information.
-
Skillful in organizing your program through functions, enhancing its structure
and maintainability.
Problem Description
Given a square grid (a 2-D array called puzzleMap) of size 2N x 2N (N = 1, 2, 3),
you need to fill the grid with L-shaped blocks with the given one empty cell.
Please note that the algorithm works in all positive integers N. We restrict N to 3 because we use 21 letters to represent at most 21 L-shapes in an 8x8 square. It is hard to have meaningful characters if N is larger than 3.
The program accepts the following inputs:
-
The width / height of the grid (either 2, 4, or 8).
-
The x and y coordinates of the empty cell (which should lie within the grid).
-
The output mode:
o 0: Exit directly for testing checkInput function;
o 1: Output Quadrant of the empty cell;
o 2 for console output without normalization;
o 3 for console output with normalization.
The normalization process will be explained later. The number of L-shaped blocks:
• 2 x 2 square = 1 L-shapes and 1 empty cell (3 filled cells + 1 empty cell).
-
4 x 4 square = 5 L-shapes and 1 empty cell (15 filled cells + 1 empty cell).
-
8 x 8 square = 21 L-shapes and 1 empty cell (63 filled cells + 1 empty cell).
Coordinate
A coordinate, (x, y), can be used to represent an element in the 2-D array (e.g., puzzleMap in this assignment). The coordinate system is zero-indexed, meaning it starts from 0. It's worth noting that coordinate (x, y) corresponds to array_2d[x][y]. Please compare carefully the grid and the actual data stored in puzzleMap.
Here is an example of representations of an empty cell in coordinate system and in the grid (2D-array):
Coordinate Grid Grid, Visualized
CCDDHHII CBBDHGGI FBEEKKGJ FFEAAKJJ RRS AMNN RQSSMMLN UQQTPLLO UUTTPPOO
|
L-Shape An L-shaped block, in the context of this problem, is a group of three cells that forms the shape of the Letter "L". There are four different L-shapes: |
|
Quadrant In this problem, a “quadrant” refers to one of four equal parts into which the grid or puzzle map is divided. Given a grid of size 2N x 2N, it can be divided into four smaller grids (or quadrants) each of size 2(N-1) x 2(N-1). |
|
Base Case The base case is the simplest instance of the problem. In this problem, the base case is when the size of the grid is 2x2 (i.e., size == 2). A 2x2 grid is the smallest grid that can be filled with an L-shaped block. |
|
General Case For the general case, the function divides the larger grid into four smaller quadrants. It then identifies in which quadrant the empty cell resides and leaves that quadrant as it is. In the remaining three quadrants, it marks the cell that is diagonally adjacent to the empty cell in the center of the larger grid. This creates a new L-shaped block and four new sub-problems (one for each quadrant), each with one marked cell. The function then recursively calls itself on each of these sub-problems. This process repeats until it reaches the base case, at which point it starts filling the grid with L-shaped blocks. |
Normalization
Because different implementations of the same algorithm may fill the grid with different orders (same shape, but different orders of characters), we need to normalize our results to ensure the shape filling follows alphabetical order from left to right and from top to bottom. To normalize a result, you need to scan each row of the grid from top to bottom. To scan a row, you iterate it from left to right, replacing characters are not in alphabetical order.Here are some normalization examples:
Before normalization:
After normalization:
01 0: A 1:A A
01 0: A 1:A A
Before normalization: 0123
0: B C C
1:B B A C
2:E A A D
3:E E D D
After normalization: 0123
0: ABB 1:A A C B 2:D C C E 3:D D E E
Before normalization: 0123
0:B B C C
1:B A A C
2:E A D D
3:E E D
After normalization: 0123
0:A A B B
1:A C C B
2:D C E E
3:D D E
Before normalization: 01234567
After normalization: 01234567
0:C C D D H H I I 1:C B B D H G G I 2:F B E E K K G J 3:FFE AKJJ 4:R R S A A M N N 5:R Q S S M M L N 6:U Q Q T P L L O 7:U U T T P P O O
0:A A B B C C D D 1:A E E B C F F D 2:G E H H I I F J 3:GGH KIJJ 4:L L M K K N O O 5:L P M M N N Q O 6:R P P S T Q Q U 7:R R S S T T U U
After normalization, we will have a unified result for any given input (grid width, x and y coordinates of the empty cell). The console output mode without normalization is for debugging purpose only, and the all the given test cases require normalized results. If your results are not correctly normalized, you will receive penalties.
Coding Tasks
• You only need to complete the following 4 coding tasks:
|
You are not allowed to use global variables in this lab. Task1: Implementing the checkInput function |
// TODO:
// function checkInput:
//
|
// Note: The pass-by-reference variables will be used in the main function.
// @return: void
// The function returns after getting valid values for
width, emptyXPos and emptyYPos
void checkInput(int &width, int &emptyXPos, int &emptyYPos) { // Some helper lines for you to use:
|
cout << "Enter the width/height of the puzzle (2, 4, 8): "; cout << endl; cout << "Enter the x-coordinate of the empty cell (0- " << width - 1 << "): "; cout << endl; cout << "Enter the y-coordinate of the empty cell (0- " << width - 1 << "): "; |
|
cout << endl; return; } |
|
Task2: Implementing the locateQuadrant function |
// TODO:
// function locateQuadrant:
// @param x: x coordinate of the empty cell
// @param y: y coordinate of the empty cell
|
|
// // If x < half width, y < half width, then return 1
// If x >= half width, y < half width, then return 2
// If x >= half width, y >= half width, then return 3
// If x < half width, y >= half width, then return 4
// // @return: int
// The function returns after getting valid values for
width, emptyXPos and emptyYPos
int locateQuadrant(int width, int x, int y) { // remove this line to start your work
return LOCATEQUADRANT_NOT_IMPLEMENTED; } |
|
Task3: Implementing the fillPuzzleRecursive function |
// TODO:
// [The most important function in this program]
// The recursive function to fill up the character array:
|
|
puzzleMap // You need to figure out the parameters of the
fillPuzzleRecursive function by yourself
// void fillPuzzleRecursive(__ width, __ puzzleMap[][MAX_WIDTH], __ tx, __ ty, __ x, __ y, __ &nextChar) // tx: top Left X coordinate { |
// ty: top Left Y coordinate // x: x coordinate of the empty cell // y: y coordinate of the empty cell if (width == 2) { // The base case...
} // The general case
|
|
// // Key idea: // Because qual must be equal to either 1, 2, 3 or 4
// As a result:
// A L-shape MUST be created at the center of the
bigger rectangle
// Each Quad MUST have exactly 1 empty space
return; } |
|
Task4: Implementing the Normalization function |
|
// TODO: // Normalize the whole puzzleMap. The space character ' '
will not be changed.
// void normalizePuzzleMap(int width, char puzzleMap[][MAX_WIDTH]) { |
|
return; } |
Checking uninitialized variables
Many students forget to initialize the variables before using them. Sometimes, it will cause serious problems. In most of the operating systems (e.g., Linux), variables won't be initialized (i.e., there are garbage values stored if the variables are not initialized and being used.)
|
"Additional" blank lines will be ignored during grading. Test case 1 (the case when all inputs are simply valid) |
Enter the width/height of the puzzle (2, 4, 8): 8
|
Enter the x-coordinate of the empty cell (0-7): 0
Enter the y-coordinate of the empty cell (0-7): 3
0: Exit directly (for testing checkInput function), 1: Output
Quadrant of the empty cell,
2: Output without normalization (for student's debug only), 3:
Output with normalization
Enter the output mode: 0
|
|
We provide a separate view for this case. For other cases, please refer to the files in the skeleton code. The Input is: |
|
8 0 3 0 |
The Output is:
Enter the width/height of the puzzle (2, 4, 8):
Enter the x-coordinate of the empty cell (0-7):
|
Enter the y-coordinate of the empty cell (0-7):
0: Exit directly (for testing checkInput function), 1: Output
Quadrant of the empty cell,
2: Output without normalization (for student's debug only), 3:
Output with normalization
Enter the output mode:
|
|
Test case 2 (the case when any input is invalid, the program will keep asking for input) |
Quadrant of the empty cell,
2: Output without normalization (for student's debug only), 3:
Output with normalization
Enter the output mode: 1
Quadrant for the empty cell: 4
|
|
Sample Input/Output for "Correct output with width 2" Test case 5 |
Enter the width/height of the puzzle (2, 4, 8): 2
|
Enter the x-coordinate of the empty cell (0-1): 0
Enter the y-coordinate of the empty cell (0-1): 1
0: Exit directly (for testing checkInput function), 1: Output
Quadrant of the empty cell,
2: Output without normalization (for student's debug only), 3:
Output with normalization
Enter the output mode: 3
Quadrant for the empty cell: 4
01 0:A A |
|
1: A |
|
Test case 6 |
Enter the width/height of the puzzle (2, 4, 8): 2
Enter the x-coordinate of the empty cell (0-1): 0
Enter the y-coordinate of the empty cell (0-1): 0
0: Exit directly (for testing checkInput function), 1: Output
Quadrant of the empty cell,
2: Output without normalization (for student's debug only), 3:
Output with normalization
Enter the output mode: 3
Quadrant for the empty cell: 1
01 0: A 1:A A |
|
Sample Input/Output for "Correct output with width 4" Test case 7 |
Enter the width/height of the puzzle (2, 4, 8): 4
|
Enter the x-coordinate of the empty cell (0-3): 2
Enter the y-coordinate of the empty cell (0-3): 2
0: Exit directly (for testing checkInput function), 1: Output
Quadrant of the empty cell,
2: Output without normalization (for student's debug only), 3:
Output with normalization
Enter the output mode: 3
Quadrant for the empty cell: 3
0123 |
|
0:A A B B 1:A C C B 2:DC E 3:D D E E |
|
Test case 8 |
Enter the width/height of the puzzle (2, 4, 8): 4
Enter the x-coordinate of the empty cell (0-3): 3
Enter the y-coordinate of the empty cell (0-3): 3
0: Exit directly (for testing checkInput function), 1: Output
|
Quadrant of the empty cell,
2: Output without normalization (for student's debug only), 3:
Output with normalization
Enter the output mode: 3
Quadrant for the empty cell: 3
0123 0:A A B B 1:A C C B 2:D C E E 3:D D E |
|
Sample Input/Output for "Correct output with width 8" Test case 9 |
Enter the width/height of the puzzle (2, 4, 8): 8
Enter the x-coordinate of the empty cell (0-7): 3
Enter the y-coordinate of the empty cell (0-7): 1
0: Exit directly (for testing checkInput function), 1: Output
Quadrant of the empty cell,
2: Output without normalization (for student's debug only), 3:
|
Output with normalization
Enter the output mode: 3
Quadrant for the empty cell: 1
01234567 0:A A B B C C D D 1:AEB CFFD 2:G E E H I I F J 3:G G H H K I J J |
4:L L M K K N O O
5:L P M M N N Q O
6:R P P S T Q Q U
7:R R S S T T U U
|
|
Test case 10 |
Enter the width/height of the puzzle (2, 4, 8): 8
Enter the x-coordinate of the empty cell (0-7): 2
Enter the y-coordinate of the empty cell (0-7): 5
0: Exit directly (for testing checkInput function), 1: Output
|
Quadrant of the empty cell,
2: Output without normalization (for student's debug only), 3:
Output with normalization
Enter the output mode: 3
Quadrant for the empty cell: 4
01234567 0:A A B B C C D D 1:A E E B C F F D 2:G E H H I I F J 3:G G H K K I J J 4:L L M M K N O O 5:LP MNNQO 6:R P P S T Q Q U 7:R R S S T T U U |
