1. Homepage
  2. Programming
  3. Programming assignment: Recursive L-Shape Square Filling

Programming assignment: Recursive L-Shape Square Filling

Engage in a Conversation
C++RecursiveL-Shape Square Filling

Recursive L-Shape Square Filling CourseNana.COM

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). CourseNana.COM

Introduction CourseNana.COM

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. CourseNana.COM

To solve a recursive problem, it is important to define the following: CourseNana.COM

  • 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. CourseNana.COM

  • 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. CourseNana.COM

  • 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. CourseNana.COM

You may consider splitting filling the whole square into subproblems such as CourseNana.COM

filling subsquares. CourseNana.COM

Upon completing this project assignment, you will achieve the following learning outcomes: CourseNana.COM

Problem Description
Given a square grid (a 2-D array called puzzleMap) of size 2N x 2N (N = 1, 2, 3), CourseNana.COM

you need to fill the grid with L-shaped blocks with the given one empty cell. CourseNana.COM

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. CourseNana.COM

The program accepts the following inputs: CourseNana.COM

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. CourseNana.COM

The normalization process will be explained later. The number of L-shaped blocks: CourseNana.COM

2 x 2 square = 1 L-shapes and 1 empty cell (3 filled cells + 1 empty cell). CourseNana.COM

  • 4 x 4 square = 5 L-shapes and 1 empty cell (15 filled cells + 1 empty cell). CourseNana.COM

  • 8 x 8 square = 21 L-shapes and 1 empty cell (63 filled cells + 1 empty cell). CourseNana.COM

Coordinate CourseNana.COM

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. CourseNana.COM

Here is an example of representations of an empty cell in coordinate system and in the grid (2D-array): CourseNana.COM

Coordinate Grid Grid, Visualized CourseNana.COM

CCDDHHII CBBDHGGI FBEEKKGJ FFEAAKJJ RRS AMNN RQSSMMLN UQQTPLLO UUTTPPOO CourseNana.COM

L-Shape CourseNana.COM

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: CourseNana.COM

Quadrant CourseNana.COM

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). CourseNana.COM

Base Case CourseNana.COM

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. CourseNana.COM

General Case CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

Normalization CourseNana.COM

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: CourseNana.COM

Before normalization:
After normalization:

01 0: A 1:A A CourseNana.COM

01 0: A 1:A A CourseNana.COM

Before normalization: 0123 CourseNana.COM

0:  B C C
1:B B A C
2:E A A D
3:E E D D

After normalization: 0123 CourseNana.COM

0: ABB 1:A A C B 2:D C C E 3:D D E E CourseNana.COM

Before normalization: 0123 CourseNana.COM

0:B B C C
1:B A A C
2:E A D D
3:E E D

After normalization: 0123 CourseNana.COM

0:A A B B
1:A C C B
2:D C E E
3:D D E

Before normalization: 01234567 CourseNana.COM

After normalization: 01234567 CourseNana.COM

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 CourseNana.COM

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 CourseNana.COM

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. CourseNana.COM

Coding Tasks
You only need to complete the following 4 coding tasks: CourseNana.COM

You are not allowed to use global variables in this lab. Task1: Implementing the checkInput function CourseNana.COM

// 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)

{ CourseNana.COM

// 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; CourseNana.COM

return; } CourseNana.COM

Task2: Implementing the locateQuadrant function CourseNana.COM

// TODO:
// function locateQuadrant:
// @param x:  x coordinate of the empty cell
// @param y:  y coordinate of the empty cell

// CourseNana.COM

// 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

// CourseNana.COM

// @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 CourseNana.COM

// TODO:
// [The most important function in this program]
// The recursive function to fill up the character array:

puzzleMap CourseNana.COM

// You need to figure out the parameters of the
fillPuzzleRecursive function by yourself

// CourseNana.COM

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...

} CourseNana.COM

// The general case

// CourseNana.COM

// Key idea: CourseNana.COM

    //  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; } CourseNana.COM

Task4: Implementing the Normalization function CourseNana.COM

// TODO: CourseNana.COM

// Normalize the whole puzzleMap. The space character ' '
will not be changed.

// CourseNana.COM

void normalizePuzzleMap(int width, char
puzzleMap[][MAX_WIDTH])

{ CourseNana.COM

return; } CourseNana.COM

Checking uninitialized variables CourseNana.COM

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.) CourseNana.COM


"Additional" blank lines will be ignored during grading. CourseNana.COM

Test case 1 (the case when all inputs are simply valid) CourseNana.COM

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. CourseNana.COM

The Input is: CourseNana.COM

8 0 3 0 CourseNana.COM

The Output is: CourseNana.COM

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) CourseNana.COM

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" CourseNana.COM

Test case 5 CourseNana.COM

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 CourseNana.COM

Test case 6 CourseNana.COM

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 CourseNana.COM

Sample Input/Output for "Correct output with width 4" CourseNana.COM

Test case 7 CourseNana.COM

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 CourseNana.COM

0:A A B B 1:A C C B 2:DC E 3:D D E E CourseNana.COM

Test case 8 CourseNana.COM

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 CourseNana.COM

Sample Input/Output for "Correct output with width 8" CourseNana.COM

Test case 9 CourseNana.COM

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 CourseNana.COM

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 CourseNana.COM

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 CourseNana.COM


Get in Touch with Our Experts

WeChat (微信) WeChat (微信)
Whatsapp WhatsApp
C++代写,Recursive代写,L-Shape Square Filling代写,C++代编,Recursive代编,L-Shape Square Filling代编,C++代考,Recursive代考,L-Shape Square Filling代考,C++help,Recursivehelp,L-Shape Square Fillinghelp,C++作业代写,Recursive作业代写,L-Shape Square Filling作业代写,C++编程代写,Recursive编程代写,L-Shape Square Filling编程代写,C++programming help,Recursiveprogramming help,L-Shape Square Fillingprogramming help,C++assignment help,Recursiveassignment help,L-Shape Square Fillingassignment help,C++solution,Recursivesolution,L-Shape Square Fillingsolution,