class Solver {
  Minesweeper game;

  /** Constructor, create a new game with 10 bombs on a 10x10 grid. */
  public Solver () {
    game      = new Minesweeper(10,10,10);
  }
  
  /** Solve the game just by asking for hints.
    * 
    * @return number of hints needed to solve game. */
  public int simpleSolver() {
    while (!game.isSolved()) {
     game.hint();
    }
    return game.getNumHints();
  }
  
  /** Determine the number of neighbors of cell (i,j) that have been 
  *  marked as bombs. */
  public int markedNeighbors(int i, int j) {
    int marked = 0;
    for (int k = Math.max(i-game.RADIUS, 0); k <= Math.min(i+game.RADIUS,game.getHeight()-1); k++) {
        for (int l = Math.max(j-game.RADIUS,0); l <= Math.min(j+game.RADIUS,game.getWidth()-1); l++) {
          if (!(k==i && l==j)) { 
           if (game.isMarked(k,l)) { 
              marked++; 
              }
          }
        }
    } 
    return marked;
  }
  
  
  /** Examine all cells of the board using markNeighborsAsBombs and exploreNeighbors in row/column order.
    * @return whether any updates were made to the board. */
  public boolean checkBoard() {
    boolean changed = false;
    for (int i=0; i < game.getHeight(); i++) {
      for (int j=0; j < game.getWidth(); j++) {
        if (markNeighborsAsBombs(i,j) || exploreNeighbors(i,j)) 
          changed = true;
      }
    }
    return changed;
  }
  
  /** Repeatedly check the board until no change. */
  public void makeAllDeductions() {
    boolean keepGoing = true;
    while (keepGoing) {
     keepGoing = checkBoard();
    }
  }
  
  /** Solve the game by simple reasoning, asking for hints when stuck. 
    * 
    * @return the number of hints needed to solve the board. */
  public int solve(){
    while (!game.isSolved()) {
      game.hint();
      makeAllDeductions();
    }
    return game.getNumHints();
  }

  /** Initial version of markedNeighbors */
  public int markedNeighbors1(int i, int j) {
   int marked = 0;
   if (game.isMarked(i-1, j-1))
      marked++;
   if (game.isMarked(i-1, j))
      marked++;
   if (game.isMarked(i-1, j+1)) 
      marked++;
   if (game.isMarked(i, j-1)) 
      marked++;
   // skip (i,j)
   if (game.isMarked(i, j+1)) 
      marked++;
   if (game.isMarked(i+1, j-1)) 
      marked++;
   if (game.isMarked(i+1, j))   
      marked++;
   if (game.isMarked(i+1, j+1)) 
      marked++;
   return marked;
 }
  
  /** Initial version of markedNeighbors */
  public int markedNeighbors2(int i, int j) {
    int marked = 0;
    for (int k = i-1; k <= i+1; k++) {
      for (int l = j-1; l <= j+1; l++) {
        if (! (k==i && l == j)) {
           if (game.isMarked(k,l)){ marked++; }
        }
     }
   }
   return marked;
  }

  /** Initial version of markedNeighbors */
  public int markedNeighbors3(int i, int j) {
   int marked = 0;
   // check the eight neighbors of the square, being careful of the edges.
   if (i>0 && j>0 && game.isMarked(i-1, j-1)) 
      marked++;
   if (i>0 && game.isMarked(i-1, j))
      marked++;
   if (i>0 && j<(game.getWidth()-1) && game.isMarked(i-1, j+1)) 
      marked++;
   if (j>0 && game.isMarked(i,   j-1))
      marked++;
   if (j<(game.getWidth()-1) && game.isMarked(i,   j+1))
      marked++;
   if (i<(game.getHeight()-1) && j > 0 && game.isMarked(i+1, j-1))
      marked++;
   if (i<(game.getHeight()-1) && game.isMarked(i+1, j))
      marked++;
   if (i<(game.getHeight()-1) && (j < game.getWidth()-1) && game.isMarked(i+1, j+1))
      marked++;
   return marked;
  }  
  
  /** Return the number of neighbors of cell (i,j) that have not yet been explored. */
  public int unexploredNeighbors(int i, int j) {
     int unexplored = 0;
     for (int k = Math.max(i-game.RADIUS, 0); k <= Math.min(i+game.RADIUS,game.getHeight()-1); k++) {
     for (int l = Math.max(j-game.RADIUS,0); l <= Math.min(j+game.RADIUS,game.getWidth()-1); l++) {
        if (k!=i || l!=j) {
           if (!game.isExplored(k,l)) unexplored++;
        }
     }
     }
  return unexplored;
  }
  
  /** The neighbors of a cell can be explored if 
   * the cell has been explored and *all* of the nearby bombs have been marked.
   * @return whether any neighbors were explored.
   */
  public boolean exploreNeighbors(int i, int j) {
    boolean changed = false;
    if (game.isExplored(i, j)) {
      if (markedNeighbors(i,j) == game.getNeighboringBombs(i,j)) {
        for (int k=Math.max(i-game.RADIUS, 0); k<=Math.min(i+game.RADIUS,game.getHeight()-1); k++) {
          for (int l = Math.max(j-game.RADIUS,0); l<=Math.min(j+game.RADIUS,game.getWidth()-1); l++) {
            if (!(k==i && l==j)) {
              if (!game.isMarked(k,l) && !game.isExplored(k,l)) {
                changed = true;
                game.explore(k,l); 
              } 
            } 
          }
        }
      }
    }
    return changed;
  }
 
  /** The neighbors of a cell can *all* be marked as bombs if 
   * the cell has been explored and the number of unexplored neigbors is 
   * equal to the number of nearby bombs.
   *
   * @return whether any neighbors were marked as bombs.
   */
 public boolean markNeighborsAsBombs(int i, int j) {
   boolean changed = false;
   if (game.isExplored(i,j) &&
    (unexploredNeighbors(i,j)) == game.getNeighboringBombs(i,j)) {
      for (int k=Math.max(i-game.RADIUS, 0); k<=Math.min(i+game.RADIUS,game.getHeight()-1); k++) {
      for (int l = Math.max(j-game.RADIUS,0); l<=Math.min(j+game.RADIUS,game.getWidth()-1); l++) {
        if (k!=i || l!=j) {
          if (!game.isMarked(k,l) && !game.isExplored(k,l)) {
            changed = true;
            game.mark(k,l); 
          }
        }
      }
    }
  }
  return changed;
  }
  
}