Use this starter code:

SymbolGrid.java

and finish the implementation.

Follow the instructions in the comments -- look for "TO DO". Also, look at the rest of the code, as there are many methods you may find helpful.

There may be more efficient solutions to this problem, but I will give credit only to those solutions that use recursion and backtracking.

import java.util.LinkedList; public class SymbolGrid { private static char[] SYMBOLS = {'~', '!', '@', '#', '$', '^', '&', '*'}; // NOTE: // Do not change this method signature. // This method calls another recursive method, but it should // not call itself. public static void findAllPaths(Grid grid, char[] sequence) {

// TO DO: // Add code to traverse the grid and search for paths // starting at each cell using the findPathsAt() method. // // System.out.println(" --- finished searching"); }

// TO DO: // Implement recursive method with backtracking // // NOTE: // You may change the list of parameters here, but before you do // check out all the helpful helper methods in Grid, Cell and Path // below. private static void findPathsAt(Grid grid, Cell here, Path currentPath, char[] sequence) { } public static void main(String[] args) { // NOTE: // You may modify this to let the user choose grid size. Grid grid = new Grid(7, SYMBOLS); grid.display(); System.out.println(); // NOTE: // You may modify this to let the use choose length of // the sequence and/or to enter the sequence they want // the program to find. char[] seq = randomSymbolSequence(4); System.out.print("sequence: "); System.out.println(seq); System.out.println(" paths:"); findAllPaths(grid, seq); }

/* Helper methods below -- you shouldn't need to alter them but you can add your own. */ private static char[] randomSymbolSequence(int length) { char[] sequence = new char[length]; for(int i = 0; i < length; i++) { sequence[i] = SYMBOLS[(int)(Math.random()*SYMBOLS.length)]; } return sequence; } } /* Represents a cell on a grid -- just a convenient way of * packaging a pair of indices */ class Cell { int r, c; Cell(int r, int c) { this.r = r; this.c = c; } @Override public boolean equals(Object o) { Cell cell = (Cell) o; return this.r == cell.r && this.c == cell.c; } @Override public String toString() { return "(" + r + ", " + c + ")"; } } /* Represents a path of cells on a grid of symbols. */ class Path { private LinkedList cells; private LinkedList symbols; Path() { cells = new LinkedList(); symbols = new LinkedList(); } int getLength() { return cells.size(); } void add(Cell location, char symbol) { cells.addLast(location); symbols.addLast(symbol); } void removeLast() { cells.removeLast(); symbols.removeLast();

} boolean contains(Cell cell) { return cells.contains(cell); } @Override public String toString() { StringBuilder sb = new StringBuilder(); for(int i = 0; i < cells.size(); i++) { sb.append(symbols.get(i)); sb.append(cells.get(i).toString()); sb.append(" "); } return sb.toString(); } void display() { System.out.println(toString()); } } /* Represents a grid of symbols. */ class Grid { private char[][] grid; Grid(int size, char[] symbols) { grid = initGrid(size, symbols); } private char[][] initGrid(int size, char[] symbols) { char[][] symbolGrid = new char[size][size]; for(int row = 0; row < size; row++) { for(int col = 0; col < size; col++) { // picks a random symbol for each cell on the grid symbolGrid[row][col] = symbols[(int)(Math.random() * symbols.length)]; } } return symbolGrid; } int getSize() { return grid.length; } char getSymbolAt(Cell location) { return getSymbolAt(location.r, location.c); } char getSymbolAt(int r, int c) { return grid[r][c]; }

boolean isOutside(Cell location) { return isOutside(location.r, location.c); } boolean isOutside(int r, int c) { return 0 > r || r >= grid.length || 0 > c || c >= grid[r].length; } boolean isOnGrid(Cell location) { return isOnGrid(location.r, location.c); } boolean isOnGrid(int r, int c) { return 0 <= r && r < grid.length && 0 <= c && c < grid[r].length; } void display() { // Display column indices System.out.print(" "); for(int i = 0; i < grid.length; i++) { System.out.print(i + " "); } System.out.println(); // Display grid for(int r = 0; r < grid.length; r++) { // Display row index System.out.print(" " + r + " "); for(int c = 0; c < grid[r].length; c++) { System.out.print(grid[r][c] + " "); } System.out.println(); } } }