Purpose: To understand and build a backtracking algorithm that checks for a path with strictly increasing letters inside a grid of lower$-$case letters, as detailed below.

You will implement the class WordSearchPuzzle, which implements the WordSearchInterface defined in WordSearchInterface.java. The interface has a single method, as specified below.

public interface WordSearchInterface $\{$

$/**$

$*$ Check if a path exists on a word search puzzle grid with strictly increasing adjacent alphabet letters from a start cell to an end cell.

$*$ A Word Search Puzzle is an n$-$by$-$n grid of lower$-$case English letters. Each cell in the grid can be represented by its row

$*$ number and column number. Row and column numbers are $0$ to n$-1$ inclusive, where n is the grid size.

$*$ A cell is adjacent to another if it is next to it along any of

The class header is as follows.

public class WordSearchPuzzle implements WordSearchInterface $\{$

Find a path in the puzzle

A Word Search puzzle is a $2-$dimensional grid of lower$-$case English letters, such as the one below.

blnksreoomhs

eaocytsileot

stgarertrrgt

drltaswesgit

eoasnnogoebt

zsttiitnfser

inrjbioaholo

toquicksorts

risqueuertcl

otxdrchoeuel

mciaacuscrre

aelreprnnish

Each cell in the grid can be represented by its row and column numbers. Row and column numbers are in the range $0$ to n$-1$ inclusive, where n is the grid size, $12$ in the given example. For example, the up$-$left cell of the grid can be represented as $(0,0)$ because it is on the first row and the first column. The down$-$right cell is $(11,11).$

Your goal in this assignment is to check if we can move from one cell to another using adjacent letters without violating the alphabetic order of letters. For example, it is possible to move from $(0,0)$ to $(2,1)$ using adjacent cells and without violating the order of the alphabet as follows.

Start at b at $(0,0)$

$*$B$*$lnksreoomhs

eaocytsileot

stgarertrrgt

drltaswesgit

eoasnnogoebt

zsttiitnfser

inrjbioaholo

toquicksorts

risqueuertcl

otxdrchoeuel

mciaacuscrre

aelreprnnish

Move to l at $(0,1)$

B$*$L$*$nksreoomhs

eaocytsileot

stgarertrrgt

drltaswesgit

eoasnnogoebt

zsttiitnfser

inrjbioaholo

toquicksorts

risqueuertcl

otxdrchoeuel

mciaacuscrre

aelreprnnish

Move to n at $(0,2)$

BL$*$N$*$ksreoomhs

eaocytsileot

stgarertrrgt

drltaswesgit

eoasnnogoebt

zsttiitnfser

inrjbioaholo

toquicksorts

risqueuertcl

otxdrchoeuel

mciaacuscrre

aelreprnnish

Move to o at $(1,2)$

BLNksreoomhs

ea$*$O$*$cytsileot

stgarertrrgt

drltaswesgit

eoasnnogoebt

zsttiitnfser

inrjbioaholo

toquicksorts

risqueuertcl

otxdrchoeuel

mciaacuscrre

aelreprnnish

Move to t at $(2,1)$

BLNksreoomhs

eaOcytsileot

s$*$T$*$garertrrgt

drltaswesgit

eoasnnogoebt

zsttiitnfser

inrjbioaholo

toquicksorts

risqueuertcl

otxdrchoeuel

mciaacuscrre

aelreprnnish

The sequence of the letters we visited on that path is $\text{'}$b$\text{'},\text{'}$l$,\text{'}\text{'}$n$,\text{'}\text{'}$o$\text{'},\text{'}$t$\text{'},$ which represents a strictly increasing sequence of letters; that is$,$ it doesn't violate the order of the alphabet.

BLNksreoomhs

eaOcytsileot

sTgarertrrgt

drltaswesgit

eoasnnogoebt

zsttiitnfser

inrjbioaholo

toquicksorts

risqueuertcl

otxdrchoeuel

mciaacuscrre

aelreprnnish

Note that the letters on the path are shown in upper$-$case for illustration only. Your code shouldn't change the grid. Also, note that each pair of consecutive letters is adjacent along one of the eight directions. The eight directions in clockwise order are right, down$-$right, down, down$-$left, left, up$-$left, up$,$ and up$-$right.

You must implement this search using backtracking.

Hint: define a private recursive helper method to perform backtracking and call it from your implementation of the isIncreasingSequencePossible method. An example helper method is:

private boolean solve$($char$[][]$ grid, int currentRow, int currentCol, int endRow, int endCol$)\{$

Please check the backtracking framework in the lecture notes and its explanation in the lecture videos.