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:
0: Exit directly for testing checkInput function;
1: Output Quadrant of the empty cell;
2 for console output without normalization;
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.

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.

Finish the "TODO" parts:

/*

  The following program solves the L-shape blocks problem

   Given
	  A 2^N x 2^N array (In this assignment, we restrict the value N as 1, 2 and 3 )
	   The location of the empty cell (x,y)
		  The legal (x,y) coordinates of the empty cell:

			  For a 2 x 2 block, the legal range is 0-1
			  For a 4 x 4 block, the legal range is 0-3
			  For a 8 x 8 block, the legal range is 0-7
	   You can assume all the input values are correct

	Output:

	  The empty cell (x,y) remains empty
	  All other cells are filled by non-overlapping L-shape blocks

	Output mode:
	  (0) Console output without normalization
	  (1) Console output with normalization

	   Author: Peter, Brian, Tommy
*/

#include <iostream>
using namespace std;

// Constants in global scope
const int MAX_WIDTH = 8;
const int LOCATEQUADRANT_NOT_IMPLEMENTED = 0;

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

/**
	Given the puzzleMap (2D array from the recursive function),
	Generate the console output
 */
void visualizePuzzleByText(int width, char puzzleMap[][MAX_WIDTH])
{

	cout << "  ";
	for (int x = 0; x < width; x++)
		cout << x << " ";
	cout << endl;

	for (int y = 0; y < width; y++)
	{
		cout << y << ":";
		for (int x = 0; x < width; x++)
			cout << puzzleMap[x][y] << " ";
		cout << endl;
	}
}

/**
 * Initialize the whole puzzleMap using by a space character: ' '
 */
void initializePuzzleMap(int width, char puzzleMap[][MAX_WIDTH])
{
	for (int x = 0; x < width; x++)
		for (int y = 0; y < width; y++)
			puzzleMap[x][y] = ' ';
}

// TODO:
// Normalize the whole puzzleMap. The space character ' ' will not be changed.
//
void normalizePuzzleMap(int width, char puzzleMap[][MAX_WIDTH])
{

	return;
}

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

// TODO:
// function checkInput:
//
// @param width: the width of the square. Valid values: 2, 4, 8
// You can assume inputs are always integers.
// @param emptyXPos: the x-axis of the empty position.
// Valid range: [0, width-1].
// You can assume inputs are always integers.
// @param emptyYPos: the y-axis of the empty position.
// Valid range: [0, width-1].
// You can assume inputs are always integers.
//
//  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;
}

// You are NOT ALLOWED to modify the main function
int main()
{

	int width = 0;
	int emptyXPos = 0;
	int emptyYPos = 0;

	checkInput(width, emptyXPos, emptyYPos);

	// initialized with empty spaces..
	char puzzleMap[MAX_WIDTH][MAX_WIDTH];

	// initialize
	initializePuzzleMap(width, puzzleMap);

	int modeOfOperation = 0;
	do
	{
		cout
			<< "0: Exit directly (for testing checkInput function), 1: Output Quadrant of the empty cell,"
			<< endl
			<< "2: Output without normalization (for student's debug only), 3: Output with normalization"
			<< endl;
		cout << "Enter the output mode: ";
		cin >> modeOfOperation;
	} while (modeOfOperation < 0 || modeOfOperation > 3);

	if (modeOfOperation == 0)
	{
		return 0;
	}
	if (modeOfOperation == 1)
	{
		int quad = locateQuadrant(width, emptyXPos, emptyYPos);
		cout << "Quadrant for the empty cell: " << quad << endl;
		return 0;
	}
	char nextChar = 'A';

	// invoke the recursive call here...
	// Result: puzzleMap will be filled by characters
	fillPuzzleRecursive(width, puzzleMap, 0, 0, emptyXPos, emptyYPos, nextChar);

	int quad = locateQuadrant(width, emptyXPos, emptyYPos);
	cout << "Quadrant for the empty cell: " << quad << endl;
	if (modeOfOperation == 2)
	{
		visualizePuzzleByText(width, puzzleMap);
	}
	else
	{
		normalizePuzzleMap(width, puzzleMap);
		visualizePuzzleByText(width, puzzleMap);
	}
	return 0;
}