Begin designing a recursive solution to this problem by imagining you are a computer, and so you don't have a birds-eye-view of the grid, like we did with Jumping Grid.

You are using backtracking to explore different paths, searching for ones that contain a particular sequence.

Ask yourself:

How do you know that a path you are on will not yield a solution and needs to be abandoned?

How do you know when you have found a solution that you need to print out?

If you do not have a solution yet but a path you are on may lead to a solution, what do you do?

TASK 2

Use this starter code:

SymbolGrid.java Download 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.

java code:

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(); } } }