/**
 * Write a description of class LatinSquare here.
 *
 * @author (your name)
 * @version (a version number or a date)
 */
public class LatinSquare
{
    // returns true iff n is in the xth row of a
    // e.g. inRow(4, {{3, 5}, {3, 6, 4}, {2}}, 1) = true, 
    // e.g. inRow(4, {{3, 5}, {3, 6, 4}, {2}}, 2) = false
    public static boolean inRow(int n, int[][]a, int x)
    {
        if (0 <= x && x < a.length)
           for (int y : a[x])
               if (y == n) 
                  return true;
        return false;
    }

    // returns true iff n is in the xth column of a
    // e.g. inColumn(4, {{3, 5}, {3, 6, 4}, {2}}, 2) = true, 
    // e.g. inColumn(4, {{3, 5}, {3, 6, 4}, {2}}, 1) = false
    public static boolean inColumn(int n, int[][]a, int x)
    {
        if (0 <= x)
           for (int[] r : a)
               if (x < r.length && r[x] == n) 
                  return true;
        return false;
    }

    // returns true iff a is a Latin Square containing the numbers 1..n 
    // a must be a square of side n, and every row and every column must be a permutation of 1..n
    // http://en.wikipedia.org/wiki/Latin_square
    public static boolean isLatin(int[][] a)
    {
        if (!LabWeek9.isSquare(a)) return false;   // a must be square 
        for (int n = 1; n <= a.length; n++)        // every number in 1..a.length 
            for (int i = 0; i < a.length; i++)     // must be in every row and every column
                if (!inRow(n, a, i) || !inColumn(n, a, i)) 
                   return false;
        return true;
    }

    // CHALLENGE (optional): 
    // returns true iff a is legal, complete Sudoku board 
    // http://en.wikipedia.org/wiki/Sudoku
    public static boolean isSudoku(int[][] a)
    {
        if (a.length != 9) return false; // a must have length 9
        if (!isLatin(a))   return false; // a must be a Latin square 
        int[][] b = new int[1][9];
        for (int i = 0; i < 9; i = i+3)      // for each sub-square of size 3x3
            for (int j = 0; j < 9; j = j+3)
                {for (int x = 0; x < 3; x++) // copy the sub-square into b 
                     for (int y = 0; y < 3; y++)
                         b[0][x * 3 + y] = a[i+x][j+y];
                 for (int k = 1; k <= 9; k++) // check that b contains all numbers 1..9
                     if (!inRow(k, b, 0))
                        return false;
                }
        return true;
    }
}