Magic Square 3x3

While I was practicing my coding with HackerRank, I encounter a JavaScript coding problem, it is Forming a Magic Square. In the post, I will focus on the 3x3 Magic Square. This is the constrain of this coding problem.

Definition

A magic square is an N×N grid of distinct positive numbers (from 1 to n^2) in which the entries in each row, column and main diagonal sum to the same number (equal to N(N^2+1)/2). And this number is called the magic constant.

For example: for a 3x3 magic square, the sum of each row, column and main diagonal is 15. The numbers in this magic square is from 1 to 9, there is no duplicated numbers.

Algorithm to create a Magic Square 3x3

So far, I have found 2 ways to create a 3x3 Magic Square by depeding on where to put 1 as a starting point in the Magic Square.

Place the number 1 at the center cell of top row (row = 0, colum = n/2)

Algorithm:

• Start at the middle of the top row, and with number 1.
• Insert number n into the current grid position.
• If the number is equal to 9 (3x3), this Magic Square is completed and stop. Otherwise increment number n.
• Move diagonally up and right based on one of the following conditions:
  • wrapping to the first column if column of new position equals n, and row sitll within the Magic Square.
  • wrapping to the last row if row of new postion equals to -1, and column still within the Magic Square.
  • the row and column of new position are all out the Magic Square (row = -1, and column = n), insert the next number into the cell under the current number.
  • if the new position is already occupied with number, insert the next number into the cell under the current number.
  • if the new position is empty, insert the next number into this position.

Please refer to the following code:

	let i = 1;
	let currentRow = 0;
	let currentCol = 1;
	while (i <= n*n) {
		if (i == 1) {
			//start to create a magicSquare 3x3
			//this starting number should be placed in the row = 0, column = 1
			magicSquare[currentRow][currentCol] = 1;
		} else {
			let nextRow = currentRow - 1;
			let nextCol = currentCol + 1;

			if (nextRow >= 0) {
				if (nextCol < n) {
					if (magicSquare[nextRow][nextCol] != 0) {
						//next cell is occupied
						currentRow += 1;
					} else {
						currentRow -= 1;
						currentCol += 1;
					}
				} else {
					currentCol = 0;
					currentRow -= 1;
				}
			} else if (nextRow < 0) {
				if (nextCol < n) {
					currentRow = n-1;
					currentCol += 1;
				} else {
					currentRow += 1;
				}
			}
			magicSquare[currentRow][currentCol] = i;
		}
		i += 1;
	}

Place the number 1 at the (n/2, n-1). In 3x3 Magic Square, place the number 1 at (row = 1, col = 2)

Algorithm:

• Start at the position (n/2, n-1), and with number 1.
• Insert number n into the current grid position.
• If the number is equal to 9 (3x3), this Magic Square is completed and stop. Otherwise increment number n.
• Move diagonally up and right based on one of the following conditions:
  • wrapping to the first column if column of new position equals n, and row sitll within the Magic Square.
  • wrapping to the last row if row of new postion equals to -1, and column still within the Magic Square.
  • the row and column of new position are all out the Magic Square (row = -1, and column = n), insert the next number into the cell left side of the current number.
  • if the new position is already occupied with number, insert the next number into the cell lef side of the current number.
  • if the new position is empty, insert the next number into this position.

Please refer to the following code:

	//starting point (number 1) at position (n/2, n-1)
	let currentRow = Math.floor(n/2);
	let currentCol = n-1;
	let i = 1;

	while (i <= n*n) {
		if (i == 1) {
			magicSquare[currentRow][currentCol] = i;
		} else {
			let nextRow = currentRow - 1;
			let nextCol = currentCol + 1;

			if (nextRow >= 0) {
				if (nextCol < n) {
					if (magicSquare[nextRow][nextCol] != 0) {
						currentCol -= 1;
					} else {
						currentRow -= 1;
						currentCol += 1;
					}
				} else {
					currentRow -= 1;
					currentCol = 0;
				}
			} else if (nextRow < 0) {
				if (nextCol < n) {
					currentRow = n - 1;
					currentCol += 1;
				} else {
					currentCol -= 1;
				}
			}
			magicSquare[currentRow][currentCol] = i;
		}
		i += 1;
	}

If you are interested in the history of Magic Square, there is a Wiki Page Magic Squrare with detial information about what is Magic Square and the history of Magic Square. Hopefully, you can enjoy it.

• ← Previous Post
• Next Post →