Java Magic square program

Question

Here is my improved version of my Magic square program from following this earlier version. I also added a few comments.

Any help for improvements would be really appreciated.

import java.util.HashSet; import java.util.Scanner; public class MagicSquare { private int[] square; private int[] row_sum; private int[] col_sum; private int magicNumber; private int size; private boolean[] usedNumbers; private int solutions=0; private int squareSize; public MagicSquare(int size) { this.size = size; this.usedNumbers = new boolean[size * size + 1]; this.square = new int[size * size]; this.row_sum = new int[size]; this.col_sum = new int[size]; this.magicNumber = ((size * size * size + size) / 2); this.squareSize = size * size; } private boolean solve(int x) { if (x == squareSize && checkDiagonals()) { for (int i = 0; i < size; i++) { if (row_sum[i] != magicNumber || col_sum[i] != magicNumber) { return false; // no solution, backtrack } } solutions++; System.out.println("Solution: "+solutions); printSquare(); return false; // serach for next solution } // the 1d square is mapped to 2d square HashSet<Integer> validNumbers = new HashSet<Integer>(); // all valid Numbers from one position if(x%size == size-1 && magicNumber-row_sum[(x/size)] <= squareSize && usedNumbers[magicNumber-row_sum[x/size]] == false) { validNumbers.add(magicNumber-row_sum[(x/size)]); // All values ​​in a row, except for the last one were set } if(x/size == size-1 && magicNumber-col_sum[(x%size)] <= squareSize && // usedNumbers[magicNumber-col_sum[x%size]] == false) { validNumbers.add(magicNumber-col_sum[x%size]); // // All values ​​in a col, except for the last one were set } if(x%size != size-1 && x/size != size-1) { // for all other positions for(int i=1; i<usedNumbers.length; i++) { if (usedNumbers[i]== false) validNumbers.add(i); } } if(validNumbers.size()==0) { return false; // no valid numbers, backtrack } for (int v : validNumbers) { row_sum[x/size] += v; col_sum[x%size] += v; if (row_sum[x/size] <= magicNumber && col_sum[x%size] <= magicNumber) { square[x] = v; usedNumbers[v] = true; if (solve(x + 1) == true) { return true; } usedNumbers[v] = false; square[x] = 0; } row_sum[x/size] -= v; col_sum[x%size] -= v; } return false; } private boolean checkDiagonals() { int diagonal1 = 0; int diagonal2 = 0; for(int i=0; i<squareSize; i=i+size+1) { diagonal1 = diagonal1 + square[i]; } for(int i=size-1; i<squareSize-size+1; i = i+size-1) { diagonal2 = diagonal2 + square[i]; } return diagonal1==magicNumber && diagonal2==magicNumber; } private void printSquare() { for (int i = 0; i < squareSize; i++) { if(i%size ==0) { System.out.println(); } System.out.print(square[i] + " "); } System.out.println(); } public static void main(String[] args) { try { Scanner sc = new Scanner(System.in); int size = sc.nextInt(); MagicSquare m = new MagicSquare(size); sc.close(); long start = System.currentTimeMillis(); m.solve(0); long duration = System.currentTimeMillis() - start; System.out.println("Runtime in ms : " + duration+" = "+duration/1000 + "sec"); System.out.println("There are "+m.solutions+" solutions with mirroring"); } catch (Exception ex) { ex.printStackTrace(); } } } 

Answer 1

Don't repeat yourself

You use x/size and x%size a lot. You can easily assign them to local variables, and your code becomes much better readable. x is not the best name for an index, consider using i.

 int x = i % size; int y = i / size; if(x == size-1 && magicNumber-row_sum[y] <= squareSize && usedNumbers[magicNumber - row_sum[y]] == false) { validNumbers.add(magicNumber - row_sum[y]); // All values ​​in a row, except for the last one were set } if(y == size-1 && magicNumber - col_sum[x] <= squareSize && // usedNumbers[magicNumber - col_sum[x]] == false) { validNumbers.add(magicNumber - col_sum[x]); // // All values ​​in a col, except for the last one were set } .... 

Answer 2

It looks like you have incorporated much of the feedback from AJNeufeld's answer to your previous question and the code looks better. The indentation is a little inconsistent though - for example, some lines are indented with two spaces, some four (or one tab), and then in some spots eight spaces/two tabs (e.g. the 10th line of solve()). Make the indentation consistent for the sake of anyone reading your code (including yourself in the future).

I tried running the code on on onlinegdb.com. In order to run the code there, I had to put the class definition for MagicSquare in a separate file (i.e. MagicSquare.java). Then in the main method, the code calls the solve method, which is a private method, like all methods except for the constructor. In order for a non-abstract class to be useful, usually it will need to have at least one method other than the constructor. The same is true for the member/instance variable/property solutions - it is referenced from the main method.

Perhaps you are simply running the code in a single file but in larger projects you will likely need to use multiple files.

---

The following block can be simplified:

for(int i=0; i<squareSize; i=i+size+1) { diagonal1 = diagonal1 + square[i]; } 

Instead of assigning the value to diagonal1 + square[i], use the compound operator +=_{(just as it was used in the last for loop of the solve() method for row_sum and col_sum)}:

for(int i=0; i<squareSize; i+=size+1) { diagonal1 += square[i]; } 

The same is true for the for loop after that to add to diagonal2.

---

One last comment about the UI: Your original post doesn't appear to contain any formal requirements but it might be wise to print explanatory text to prompt the user to enter the number to be used for the magic number.

Answer 3

You aren’t using try-with-resources, so you are having to A) manually close the Scanner yourself, and B) catch an exception just to print the stack-trace, which would happen automatically if you didn’t explicitly catch any exceptions. Additionally, you aren’t closing the scanner if an exception happens before you manually close the scanner, since execution directly jumps to your catch statement. You’d need a finally clause to close the scanner no matter how the try block is exited, and then you’d have to be worried about a possible exception in the finally clause, but all this is exactly what try-with-resources is designed for.

You should write your main function like:

public static void main(String[] args) throws Exception { try (Scanner sc = new Scanner(System.in)) { int size = sc.nextInt(); MagicSquare m = new MagicSquare(size); m.solve(0); } } 

Note you don’t need to call sc.close(), nor do you need a catch () clause. Of course, you should add your timing and print statements to the above; they were omitted for brevity.

---

Algorithm

You’re original code tried 16 different values for the first cell, then 15 for the next cell, 14 for the next, 13 for the next, and so on, down to the last cell where one number remained. This gave 16! possible squares to check for “magicness”.

This new algorithm tries 16 different values for the first cell, 15 for the second, 14 for the third, and computes the value for the fourth cell. On the next row, it repeats this with 12 values for the fifth cell, 11 for the next, 10 for the next, and computes the value for the eighth cell. Ditto for the 3rd row, and finally the last row is computed. This gives:

16*15*14 * 12*11*10 * 8*7*6 = 1,490,227,200 possible squares 

which is an improvement of 14,040 times over 16! possible squares. We can further improve this. After exploring the row 0 solution space, instead of exploring the row 1 solution space (where you again have 4 unknowns and must pick 3 values and compute the fourth), explore the column 0 solution space. Here, we already have 1 known value (from row 0), so only need to explore 3 unknowns by picking 2 and computing the 3rd. After that, you continue with row 1, followed by column 1, then row 2 and column 2, and so on alternating between rows and columns. In the case of a 4x4 magic square, these are the number of possibilities you end up with each cell (1 cells being directly computed):

16 15 14 1 12 9 8 1 11 6 4 1 1 1 1 1 

Total possibilities = 16*15*14 * 12*11 * 9*8 * 6 * 4 = 766,402,560 which is half as many possibilities, so can run in approximately half the time!

We can do even better, at the expense of determining a more complicated exploration path. After exploring row 0 and column 0, you have 2 knowns on one of the diagonals. This means if you can explore the diagonal next, with only 2 remaining unknowns, by picking 1 value for one diagonal cell (say, row 2, col 1), and computing the other (row 1, col 2). Then continue exploration of the rows and columns, alternating between rows and columns as you go. The 4x4 magic square exploration possibility space becomes:

16 15 14 1 12 7 1 1 11 9 4 1 1 1 1 1 

Total possibilities = 16*15*14 * 12*11 * 9 * 7 * 4 = 111,767,040, which is approximately 1/13th of your current solution’s exploration space, and so could run in just 8% of your current time.