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.

finish TODO parts in the code (C++):
/*

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

	if (x < width / 2 && y < width / 2)
		return 1;
	else if (x >= width / 2 && y < width / 2)
		return 2;
	else if (x >= width / 2 && y >= width / 2)
		return 3;
	else if (x < width / 2 && y >= width / 2)
		return 4;
	//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])
{
	char nextChar = 'A';
    
    for (int y = 0; y < width; y++)
    {
        for (int x = 0; x < width; x++)
        {
            if (puzzleMap[x][y] != ' ' )
                puzzleMap[x][y] = nextChar;
        }
    }
	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(int width, char puzzleMap[][MAX_WIDTH], int tx,
						 int ty, int x, int y, char &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

	int quad = locateQuadrant(width, x, y);
	if (width == 2)
    {
		for (int i = tx; i < 2; i++)
			for (int j = ty; j < 2; j++)
				if (i == x && j == y)
					puzzleMap[i][j] = ' ';
				else
					puzzleMap[i][j] = nextChar++;
		
		return;

	}

	switch (quad){

		case 1:
			break;
		case 2:
			break;
		case 3:
			break;
		case 4:
			break;
	}

	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:
	width = 0;
	emptyXPos = -1;
	emptyYPos = -1;

	while (true)
	{
		cout << "Enter the width/height of the puzzle (2, 4, 8): ";
		cin >> width;
		cout << endl;
		if (width == 2 || width == 4 || width == 8)
			break;
	}

	while (true)
	{
		cout << "Enter the x-coordinate of the empty cell (0-" << width - 1 << "): ";
		cin >> emptyXPos;
		cout << endl;
		if (emptyXPos < width && emptyXPos >= 0)
			break;
	}
	while (true)
	{
		cout << "Enter the y-coordinate of the empty cell (0-" << width - 1 << "): ";
		cin >> emptyYPos;
		cout << endl;
		if (emptyYPos < width && emptyYPos >= 0)
			break;
	}

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