Friday, April 11, 2008

Magic Square

A 3x3 normal magic square is a 3x3 grid where the numbers on each row, each column, and both diagonals all add up to the same number, and the square contains the numbers 1 to 9 exactly. For example, the following is the Lo Shu magic square:
`4  9  23  5  78  1  6`

Implement a function which, given a two-dimensional 3 by 3 array of ints returns a boolean that tells us if the given square (represented by the array) is a normal 3 by 3 magic square or not.

All we have to do is check all rows, all cols, and diagonals. A bit tedious but straightforward. Is there a solution that uses significantly fewer lines of code? I can't think of one (in Java).

`public class Magic {  public static boolean check(int[][] a){    int sum,s;    sum=0;    for (int col = 0; col< 3; col++) //first set the sum (15 always?)      sum += a[col];    //check the next two rows    s = 0;    for (int row = 1; row < 3; row++){      s = 0;      for (int col = 0; col< 3; col++)         s += a[row][col];      if (s != sum)        return false;    }    //check columns    for (int col = 0; col< 3; col++) {      s = 0;      for (int row = 0; row < 3; row++){        s += a[row][col];      }      if (s != sum)        return false;    }    //check diagonal 1    s =0;    for (int row = 0; row < 3; row++){      s += a[row][row];    }    if (s != sum)      return false;    //check diagonal 2    s =0;    for (int row = 0; row < 3; row++){      s += a[row][2 - row];    }    if (s != sum)      return false;    //check that the numbers 1..9 appear    //We use an array of booleans and mark each one as we find it.    boolean[] appears = new boolean;    for (int i=0; i < 9; i++){      appears[i] = false;    }    //Check each one    for (int col = 0; col< 3; col++) {      for (int row = 0; row < 3; row++){        int num = a[row][col];        if (appears[num-1]) //its easy to forget that -1.          return false; //oops, this number appears twice!        appears[num-1] = true;      }    }    //I could check here that all the values in appears are true but    // since there are 9 positions in both appears and a[][], I know    // that if we get to this point then all the values in appears[]    // must be true!    return true;  }  public static void main (String[] args){    int[][] loshu = {{4,9,2},{3,5,7},{8,1,6}};    System.out.println(Magic.check(loshu));    int[][] no1 = {{4,9,2},{3,7,5},{8,1,6}};    System.out.println(Magic.check(no1));    int[][] no2 = {{4,9,2},{3,3,5},{8,1,6}};    System.out.println(Magic.check(no2));  }  /** From wikipedia: The Lo Shu square (3×3 magic square)Chinese literature dating from as early as 2800 BC tells the legend ofLo Shu or "scroll of the river Lo". In ancient China, there was a hugeflood. The people tried to offer some sacrifice to the river god ofone of the flooding rivers, the Lo river, to calm his anger. Then,there emerged from the water a turtle with a curious figure/pattern onits shell; there were circular dots of numbers that were arranged in athree by three nine-grid pattern such that the sum of the numbers ineach row, column and diagonal was the same: 15. This number is alsoequal to the number of days in each of the 24 cycles of the Chinesesolar year. This pattern, in a certain way, was used by the people incontrolling the river. */} `