public class Solver {
  //this works for simple games - the algorithm is called a 'naked one' solution. On the question paper there is another
  //solution called a 'hidden one' solution. More sophisticated would be to look for pairs of pencil marks
  // (naked two and hidden two solutions).

  static int[][] game = {
      {0, 6, 0, 3, 0, 0, 8, 0, 4},
      {5, 3, 7, 0, 9, 0, 0, 0, 0},
      {0, 4, 0, 0, 0, 6, 3, 0, 7},
      {0, 9, 0, 0, 5, 1, 2, 3, 8},
      {0, 0, 0, 0, 0, 0, 0, 0, 0},
      {7, 1, 3, 6, 2, 0, 0, 4, 0},
      {3, 0, 6, 4, 0, 0, 0, 1, 0},
      {0, 0, 0, 0, 6, 0, 5, 2, 3},
      {1, 0, 2, 0, 0, 9, 0, 8, 0}
  };

  //a game that is too difficult to solve with this method (it finds the first
  //three numbers before there are no squares with only one pencil mark
  static int[][] game1 = {
      {0, 0, 0, 0, 6, 0, 0, 0, 0},
      {1, 0, 6, 0, 2, 0, 4, 0, 0},
      {0, 0, 2, 3, 1, 0, 9, 7, 0},
      {0, 2, 0, 0, 0, 9, 0, 0, 0},
      {0, 0, 0, 0, 0, 0, 8, 9, 5},
      {0, 0, 8, 0, 0, 0, 7, 0, 0},
      {8, 6, 0, 4, 0, 0, 2, 3, 0},
      {2, 0, 7, 0, 0, 8, 0, 0, 0},
      {0, 9, 1, 0, 0, 0, 0, 4, 0}
  };

  public static void main(String[] args) {
    Grid grid = new Grid(game);
    System.out.println("The given grid is:");
    grid.print();
    while (grid.hasFreeSpace()) {
      //when there is a space there will always be at least one space
      // that has only one pencil mark (as it is an easy sudoku)
      for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
          if (grid.isGoodMove(i, j)) {
            grid.makeMove(i, j);
            grid.removePMarks(i, j);
          }
        }
      }
    }
    System.out.println("The solution is:");
    grid.print();
  }
}