Magic Square Palindromes in Java

A magic square palindrome is a sentence whose characters can be divided in a K × K square table with the property that the original sentence can be read from the table in four different ways:

• Start from the (1,1) cell, move right until the end of the line and than proceed to the next line.
• Start from the (1,1) cell, move down until the end of the column and then proceed to the next column.
• Start from the (K,K) cell, move left until the beginning of the line and then proceed to the previous line.
• Start from the (K,K) cell, move up until the beginning of the column and then proceed to the previous column.

“Sator arepo tenet opera rotas” is probably the most famous magic square palindrome. We can arrange it in a K=5 (5×5) table in the following way:

Magic square palindrome: Sator arepo tenet opera rotas

s	a	t	o	r
a	r	e	p	o
t	e	n	e	t
o	p	e	r	a
r	o	t	a	s

Sample Solution

The following sample solution and implementation is based on the problem available on UVa Online Judge.

1. Read in the input string.
2. Remove all whitespace and punctuation from the string.
3. Check to see if the length of the string is a square. If it is, it is possible that the string is a magic square palindrome. If the length is not a perfect square, then the string cannot be a magic square palindrome.
4. Create a NxN character matrix, populating each cell with a character from the string.
5. Check the array to see if the matrix is symmetric. If the matrix is symmetric, the input string is deemed to be a magic square palindrome!

Implementation of Magic Square Palindromes in Java

import java.util.*;

public class MagicSquarePalindrome {

	static Queue<String> strings = new LinkedList<String>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int numTestCases = sc.nextInt();
		sc.nextLine();
		for (int i=0; i < numTestCase; i++) {
			String line = sc.nextLine();
			String formatted = trimAndConcat(line);
			int dimension = (int) Math.sqrt(formatted.length());
			boolean isPerfectSquare = (dimension * dimension) == formatted.length();
			System.out.println("Case #" + (i+1) + ":");
			if(isPerfectSquare) {
				char[][] matrix = createMatrix(formatted, dimension);
				boolean isSymmetric = is SymmetricMatrix(matrix);
				if(isSymmetric) {
					System.out.println(dimension);
				} else {
					System.out.println("No magic :(");
				}
			} else {
				System.out.println("No magic :(");
			}
		}
	}
	
	public static boolean isSymmetricMatrix(char[][] matrix) {
		for(int i=0; i < matrix.length; i++) {
			for(int j=0; j < matrix.length; j++) {
				if(i != j) {
					if(matrix[i][j] != matrix[j][i]) {
						return false;
					}
				}
			}
		}

		return true;
	}
	
	public static String trimAndConcat(String input) {
		String output = "";
		for(int i=0; i < input.length(); i++) {
			if(Character.isLetter(input.charAt(i))) {
				output += input.charAt(i);
			}
		}
		return output;
	}
	
	public static char[][] createMatrix(String input, int dimension) {
		char[][] matrix = new char[dimension][dimension];
		
		for(int i=0; i<dimension; i++) {
			for(int j=0; j<dimension; j++) {
				matrix[i][j] = input.charAt(i + j);
			}
		}
		
		return matrix;
	}
}