import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import com.google.common.annotations.VisibleForTesting;

public class SudokuSolver {

  /**
   * Write a function that takes a list of integers in no particular
   * order and returns true if it has exactly the numbers 1 through 9.
   * <p>
   * If it has a number that is not 1 through 9, it returns false.
   * If it does not have ALL the numbers 1 through 9 it returns false.
   * For example:
   * <p>
   * [ ] -> False
   * None -> False
   * [1, 2] -> False
   * [1, 2, 3, 4, 5, 9, 7, 6, 8] -> True
   * [-1] -> False
   * [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] -> False
   * [1, 1, 1, 1, 1, 1, 1, 1, 1] -> False
   */
  public static void main(String... args) {

  }

  public static boolean isOneThroughNine(List<Integer> input) {
    if (input.size() != 9) {
      return false;
    }

    Collections.sort(input);

    for (int i = 1; i < 10; i++) {
      if (input.get(i - 1) != i) {
        return false;
      }
    }
    return true;
  }

  /**
   * Write a function that takes a list of integers of already chosen
   * numbers 1 through 9
   * (eg. [3, 6]) and a next number to be chosen. Check if this is a
   * valid choice.
   * <p>
   * For example
   * <p>
   * valid_choice(3, [3, 6]) -> False
   * valid_choice(10, [3, 6]) -> False
   * valid_choice(5, [3, 6]) -> True
   */
  public static boolean isValidChoice(int numberToCheck, List<Integer> alreadyUsed) {
    return numberToCheck >= 1 &&
        numberToCheck <= 9 &&
        !alreadyUsed.contains(numberToCheck);
  }

  /**
   * Given a 9 x 9 (2-dimensional array) and validate it.
   * <p>
   * Valid matrix
   * <p>
   * [ [5, 3, 4, 6, 7, 8, 9, 1, 2],
   * [6, 7, 2, 1, 9, 5, 3, 4, 8],
   * [1, 9, 8, 3, 4, 2, 5, 6, 7],
   * <p>
   * [8, 5, 9, 7, 6, 1, 4, 2, 3],
   * [4, 2, 6, 8, 5, 3, 7, 9, 1],
   * [7, 1, 3, 9, 2, 4, 8, 5, 6],
   * <p>
   * [9, 6, 1, 5, 3, 7, 2, 8, 4],
   * [2, 8, 7, 4, 1, 9, 6, 3, 5],
   * [3, 4, 5, 2, 8, 6, 1, 7, 9]]
   */

  public static boolean validSudoku(int[][] input) {

    return validSudokuRowsAndColums(input) &&
        validSudokuGrids(input);
  }

  @VisibleForTesting
  static boolean validSudokuRowsAndColums(int[][] input) {
    for (int i = 0; i < 9; i++) {
      List<Integer> toCheckRow = new ArrayList<>();
      List<Integer> toCheckColumn = new ArrayList<>();
      for (int j = 0; j < 9; j++) {
        toCheckRow.add(input[i][j]);
        toCheckColumn.add(input[j][i]);
      }
      if (!isOneThroughNine(toCheckRow) || !isOneThroughNine(toCheckColumn)) {
        return false;
      }
    }
    return true;
  }

  @VisibleForTesting
  static boolean validSudokuGrids(int[][] input) {
    for (int gridXOrigin = 0; gridXOrigin < 7; gridXOrigin += 3) {
      for (int gridYOrigin = 0; gridYOrigin < 7; gridYOrigin += 3) {
        List<Integer> toCheck = new ArrayList<>();
        for (int x = gridXOrigin; x < gridXOrigin + 3; x++) {
          for (int y = gridYOrigin; y < gridYOrigin + 3; y++) {
            toCheck.add(input[x][y]);
          }
        }
        if (!isOneThroughNine(toCheck)) {
          return false;
        }
      }
    }
    return true;
  }

}