In this puzzle you can bounce between the two 3s but you can

In this puzzle, you can bounce between the two 3’s, but you cannot reach any other squares. Write a function bool Solvable(int start, int[] squares) in Java that takes a starting position of the marker along with the array of squares. The function should return true if it is possible to solve the puzzle from the starting configuration, and false if it is impossible. You may assume all the integers in the array are positive except for the last entry, the goal square, which is always zero.

Q1. A Recursive Puzzle You have been given a puzzle consisting of a row of squares each containing an integer, like this: 3 6 4 1 3 4 2 5 3 0 The circle on the initial square is a marker that can move to other squares along the row. Ateach step in the puzzle, you may move the marker the number of squares indicated by the integer in the square it currently occupies. The marker may move either left or right along the row but may not move past either end. For example, the only legal first move is to move the marker three squares to the right because there is no room to move three spaces to the left. The goal of the puzzle is to move the marker to the 0 at the far end of the row. In this configuration, you can solve the puzzle by making the following set of moves Starting Position: 3 6 4 1 3 4 2 5 3 0 Step 1: (move right) 3 6 4 1 3 4 2 5 3 0 Step 2: (move left) 3 6 4 1 3 4 2 5 3 0 Step 3: (move right) 3 6 4 1 3 4 2 5 3 0 Step 4: (move right) 3 6 4 1 3 4 2 5 0 Step 5: (move left) 3 6 4 1 3 4 2 5 3 0 Step 6: (move right) 3 6 4 1 4 2 5 3 0 Even though this puzzle is solvable-and indeed has more than one solution- puzzles of this form some may be impossible, such as the following one 3 1 2 0

Solution

import java.applet.* ;

import java.awt.* ;

public class SimplifiedSudoku extends Applet implements Runnable

{

   protected int model[][] ;

   protected Button view[][] ;

   protected void createModel()

   {

      model = new int[9][9] ;

      for( int row = 0; row < 9; row++ )

         for( int col = 0; col < 9; col++ )

            model[row][col] = 0 ;

      model[0][0] = 9 ;

      model[0][4] = 2 ;

      model[0][6] = 7 ;

      model[0][7] = 5 ;

      model[1][0] = 6 ;

      model[1][4] = 5 ;

      model[1][7] = 4 ;

      model[2][1] = 2 ;

      model[2][3] = 4 ;

      model[2][7] = 1 ;

      model[3][0] = 2 ;

      model[3][2] = 8 ;

      model[4][1] = 7 ;

      model[4][3] = 5 ;

      model[4][5] = 9 ;

      model[4][7] = 6 ;

      model[5][6] = 4 ;

      model[5][8] = 1 ;

      model[6][1] = 1 ;

      model[6][5] = 5 ;

      model[6][7] = 8 ;

      model[7][1] = 9 ;

      model[7][4] = 7 ;

      model[7][8] = 4 ;

      model[8][1] = 8 ;

      model[8][2] = 2 ;

      model[8][4] = 4 ;

      model[8][8] = 6 ;

   }

   protected void createView()

   {

      setLayout( new GridLayout(9,9) ) ;

      view = new Button[9][9] ;

      for( int row = 0; row < 9; row++ )

         for( int col = 0; col < 9; col++ )

         {

            view[row][col] = new Button() ;

            add( view[row][col] ) ;

         }

   }

   protected void updateView()

   {

      for( int row = 0; row < 9; row++ )

         for( int col = 0; col < 9; col++ )

            if( model[row][col] != 0 )

               view[row][col].setLabel( String.valueOf(model[row][col]) ) ;

            else

               view[row][col].setLabel( \"\" ) ;

   }

   public void init()

   {

      createModel() ;

      createView() ;

      updateView() ;

   }

   protected boolean checkRow( int row, int num )

   {

      for( int col = 0; col < 9; col++ )

         if( model[row][col] == num )

            return false ;

      return true ;

   }

   protected boolean checkCol( int col, int num )

   {

      for( int row = 0; row < 9; row++ )

         if( model[row][col] == num )

            return false ;

      return true ;

   }

   protected boolean checkBox( int row, int col, int num )

   {

      row = (row / 3) * 3 ;

      col = (col / 3) * 3 ;

      for( int r = 0; r < 3; r++ )

         for( int c = 0; c < 3; c++ )

         if( model[row+r][col+c] == num )

            return false ;

      return true ;

   }

   public void start()

   {

      (new Thread(this)).start() ;

   }

   public void run()

   {

      try

      {

         Thread.sleep( 1000 ) ;

         solve( 0, 0 ) ;

      }

      catch( Exception e )

      {

      }

   }

   public void solve( int row, int col ) throws Exception

   {

      if( row > 8 )

         throw new Exception( \"Solution found\" ) ;

      if( model[row][col] != 0 )

         next( row, col ) ;

      else

      {

         for( int num = 1; num < 10; num++ )

         {

            if( checkRow(row,num) && checkCol(col,num) && checkBox(row,col,num) )

            {

               model[row][col] = num ;

               updateView() ;

               Thread.sleep( 1000 ) ;

               next( row, col ) ;

            }

         }

         model[row][col] = 0 ;

         updateView() ;

      }

   }

   public void next( int row, int col ) throws Exception

   {

      if( col < 8 )

         solve( row, col + 1 ) ;

      else

         solve( row + 1, 0 ) ;

   }

}