Exercises - Using Stacks II

  1. Below is a method which uses a stack of integers with typical push and pop operations:

    public static int foo(int x, int y) {
       if (x <= 0 || y <= 0)
          return 0;
       stack.push(y);
       return foo(x - 1, y-1) + stack.pop();
    }
    

    Assuming the stack is initially empty, draw a snapshot of the stack after every push and pop statement for each recursive call for foo(3,4). Label each stack snapshot with the recursive call, and the push or pop statement. For example, the following shows the first two snapshots of the stack after the push statement for the call foo(3,4) and after the push statement for the call foo(2,3).

     4
    ---
    foo(3,4) - push
    
     3
     4
    ---
    foo(2,3) - push
    

    To what integer value does foo(3,4) evaluate when invoked?

    
                           2
                  3        3        3
       4          4        4        4       4
    ========  ========  ======== ======= ======= =======
    foo(3,4)  foo(2,3)  foo(1,2)   pop     pop     pop
      push     push       push
    
    foo(3,4) = foo(2,3) + pop
    foo(2,3) = foo(1,2) + pop
    foo(1,2) = foo(0,1) + pop
    foo(0,1) = 0
    
    So,
    
    foo(1,2) = 0 + 2 = 2
    foo(2,3) = 2 + 3 = 5
    foo(3,4) = 5 + 4 = 9  <-- final answer = 9
    

  2. In using the shunting yard algorithm to convert A - (B ^ C ^ D * E) + F / G from partially parenthesized infix form to postfix form, list the elements that are popped from the operator stack in the order they are popped.

    ^ ^ * ( - / +

  3. Write a class ShuntingYard that prompts the user to enter an expression in infix form (possibly only partially parenthesized), and then prints an equivalent expression in fully parenthesized postfix form -- where operators come after their operands.

    You may assume that the user input will separate operands, operators, and parentheses with spaces, and the operators include only "+", "-", "*", "/", and "^".

    $ java ShuntingYard↵
    Enter an infix expression to convert to postfix form:
    ( A ^ B ^ C * ( D - E ) )↵
    A B C ^ ^ D E - *
    
  4. Expand the class ShuntingYard by adding a method named toPreFix(String s) and changing the main(String[] args) method so that it prompts the user to enter an expression in infix form (possibly only partially parenthesized), and then prints an equivalent expression in fully parenthesized prefix form -- where operators come before their operands, and every operator and its operands appear in parentheses. A sample run is shown below.

    You may assume that the user input will separate operand and operator tokens with spaces, and the operators include only "+", "-", "*", "/", and "^".

    $ java ShuntingYard↵
    Enter an infix expression to convert to prefix form:
    A + B * C ^ D - E↵
    ( - ( + A ( * B ( ^ C D ) ) ) E )
    
  5. One can solve the N-Queens problem by implementing a backtracking algorithm using a stack. Show the values of such a stack after each push or pop operation for 4-Queens problem until the first solution is found. You may assume the rows and columns are both indexed from $0$ to $3$ (bottom-to-top and left-to-right, as appropriate) and that lower indexed rows are tried before higher ones, and the same is true for columns.

                                                 2
                     1                       0   0
         2       3   3   3               3   3   3
     0   0   0   0   0   0   0       1   1   1   1
    === === === === === === === === === === === ===
    

  6. Complete the implementation of the class NQueensSolver that prompts the user for a board size, and then finds and prints all solutions to the NQueens problem (i.e., placing $n$ queens on an $n \times n$ board so that no queen can attack any other) for that size board, as the sample run below suggests.

    Use an explicit stack and backtracking instead of recursion to keep track of the positions of the queens placed so far.

    Hint: an $8 \times 8$ board has 92 solutions.

    $ java NQueens↵
    Enter board size to solve:
    4↵
     *  Q  *  * 
     *  *  *  Q 
     Q  *  *  * 
     *  *  Q  * 
    
     *  *  Q  * 
     Q  *  *  * 
     *  *  *  Q 
     *  Q  *  * 
    
    Solutions Found: 2
    
  7. In an $n \times n$ Latin Square, filled with $n$ different symbols, each symbol occurs exactly once in each row and exactly once in each column. For example, the following is a Latin Square where $n=3$:

    $$\begin{array}{|c|c|c|}\hline 1 & 2 & 3\\\hline 3 & 1 & 2\\\hline 2 & 3 & 1\\\hline \end{array}$$ Complete the implementation of the class LatinSquares that prompts the user for the value of $n$ (you may assume $2 \le n \le 9$) and then finds all Latin Squares using symbols $1$ to $n$ on an $n \times n$ board, displays them, and reports how many there are.

    Below is a sample run:

    $ java LatinSquares↵
    Enter n:
    4↵
    
    Solutions:
    
    1234
    2143
    3412
    4321
    
    1234
    2143
    3421
    4312
    
     .
     .
     .
    
    4321
    3412
    2143
    1234
    
    576 solutions found!
    
  8. In a Sudoku puzzle, one is given a partially filled $9 \times 9$ grid. The goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and $3 \times 3$ subgrid contains exactly one instance of the digits from 1 to 9.

    Complete the implementation of the class SudokuSolver whose constructor accepts a 2d-array of ints representing a sudoku puzzle (where entries of $0$ in the array signify empty cells). The provided main() method finds and prints the solution (if it exists) to two puzzles specified in this way, as the sample run below suggests.

    Use an explicit stack and backtracking instead of recursion to keep track of the numbers filled in the blanks during the solution process.

    $ java SudokuSolver↵
    NEW PUZZLE:
    
    ·39┃···┃7··
    ···┃7··┃1··
    6··┃·8·┃··4
    ━━━╋━━━╋━━━
    8·4┃··7┃··6
    ···┃8··┃4··
    ·5·┃2·6┃81·
    ━━━╋━━━╋━━━
    ···┃···┃·7·
    58·┃··3┃94·
    723┃4·8┃6··
    
    1 solutions(s) found:
    
    139┃624┃785
    248┃759┃163
    675┃381┃294
    ━━━╋━━━╋━━━
    814┃937┃526
    962┃815┃437
    357┃246┃819
    ━━━╋━━━╋━━━
    491┃562┃378
    586┃173┃942
    723┃498┃651
    
    -----------------
    
    NEW PUZZLE:
    
    316┃578┃42·
    52·┃···┃···
    ·87┃···┃·31
    ━━━╋━━━╋━━━
    ··3┃·1·┃·8·
    9··┃863┃··5
    ·5·┃·9·┃6··
    ━━━╋━━━╋━━━
    13·┃···┃25·
    ···┃···┃·74
    ··5┃2·6┃3··
    
    0 solutions(s) found:
    
  9. In the game of chess, a knight is a piece often shaped in the form of a horse's head and neck, that in one move can travel to any other space on the board that is either up/down 2 spaces and left/right 1 space from its current location, or left/right 2 spaces then up/down 1 space from its current location. In the course of doing so, knights may "jump" over any other pieces in their paths. This means that a knight may move in up to 8 different ways from a given square it occupies, as shown below.

    A knight's tour is a sequence of moves of a knight on a chessboard whereby the knight visits every square exactly once.

    Create a class KnightsTourSolver which imagines a $n \times n$ chessboard as an array and finds all knight's tours of that board starting with the position in the upper left corner, which is presumed to be the position in row $0$ and column $0$ of the corresponding array.

    Finding these tours should be accomplished using a stack-based backtracking algorithm (do not use recursion), where legal moves are explored in the order enumerated in the image above. Solutions found should be numbered and displayed as two-dimensional arrays showing the order in which each cell is visited, in a manner consistent with the portion of the sample run shown below.

    $ java KnightsTourSolver↵
    Enter board size to solve: 
    5
    Solution 1
    1     12    3     18    21    
    4     17    20    13    8    
    11    2     7     22    19    
    16    5     24    9     14    
    25    10    15    6     23    
    
    Solution 2
    1     14    3     8     21    
    4     9     20    13    18    
    15    2     17    22    7    
    10    5     24    19    12    
    25    16    11    6     23    
    
    ...
    
    Solution 304
    1     14    19    8     25    
    6     9     2     13    18    
    15    20    7     24    3    
    10    5     22    17    12    
    21    16    11    4     23
    
  10. Complete the implementation of the class MazeSolver, whose constructor accepts a 2d-array of int values representing a maze (entries of $1$ correspond to walls and entries of $0$ correspond to empty corridors), with the starting position for the maze in first row and second column, and the finishing position in the bottom row and second-to-last column. The provided main() method finds and prints -- for 3 separate mazes -- how many solutions exist and the solution path for each, as the sample run below suggests.

    Use an explicit stack and backtracking instead of recursion to keep track of the choices of direction taken by the person solving the maze during the solution process.

    $ java MazeSolver↵ 
    NEW MAZE:
    
    ░S░░░░░░░░░
    ░ ░  ░░   ░
    ░ ░░ ░  ░ ░
    ░ ░    ░░ ░
    ░   ░░ ░  ░
    ░░░ ░  ░ ░░
    ░   ░░ ░  ░
    ░ ░ ░   ░ ░
    ░░░░░░░░░F░
    
    1 solutions(s) found:
    
    ░S░░░░░░░░░
    ░•░  ░░•••░
    ░•░░ ░••░•░
    ░•░••••░░•░
    ░•••░░ ░••░
    ░░░ ░  ░•░░
    ░   ░░ ░••░
    ░ ░ ░   ░•░
    ░░░░░░░░░F░
    
    NEW MAZE:
    
    ░S░░░░░░░░░░░░░░░░░░░
    ░       ░ ░       ░ ░
    ░░░ ░░░ ░ ░░░ ░░░░░ ░
    ░   ░   ░ ░ ░     ░ ░
    ░ ░░░ ░░░ ░ ░ ░░░ ░ ░
    ░               ░ ░ ░
    ░ ░░░░░░░ ░░░░░░░ ░ ░
    ░ ░ ░ ░   ░       ░ ░
    ░ ░ ░ ░░░░░░░ ░░░ ░ ░
    ░   ░       ░ ░   ░ ░
    ░░░ ░ ░░░░░░░ ░░░░░ ░
    ░     ░ ░ ░     ░   ░
    ░ ░░░ ░ ░ ░ ░ ░░░░░ ░
    ░   ░ ░ ░ ░ ░     ░ ░
    ░ ░ ░ ░ ░ ░░░░░ ░ ░ ░
    ░ ░ ░ ░   ░   ░ ░   ░
    ░ ░░░ ░ ░░░░░ ░ ░░░ ░
    ░   ░   ░   ░   ░ ░ ░
    ░ ░░░░░ ░ ░░░ ░░░ ░ ░
    ░   ░         ░     ░
    ░░░░░░░░░░░░░░░░░░░F░
    
    4 solutions(s) found:
    
    ░S░░░░░░░░░░░░░░░░░░░
    ░•••••••░ ░       ░ ░
    ░░░ ░░░•░ ░░░ ░░░░░ ░
    ░   ░•••░ ░ ░•••••░ ░
    ░ ░░░•░░░ ░ ░•░░░•░ ░
    ░    •••••••••  ░•░ ░
    ░ ░░░░░░░ ░░░░░░░•░ ░
    ░ ░ ░ ░   ░  •••••░ ░
    ░ ░ ░ ░░░░░░░•░░░ ░ ░
    ░   ░       ░•░   ░ ░
    ░░░ ░ ░░░░░░░•░░░░░ ░
    ░     ░ ░ ░  •  ░   ░
    ░ ░░░ ░ ░ ░ ░•░░░░░ ░
    ░   ░ ░ ░ ░ ░•••••░ ░
    ░ ░ ░ ░ ░ ░░░░░ ░•░ ░
    ░ ░ ░ ░   ░   ░ ░•••░
    ░ ░░░ ░ ░░░░░ ░ ░░░•░
    ░   ░   ░   ░   ░ ░•░
    ░ ░░░░░ ░ ░░░ ░░░ ░•░
    ░   ░         ░    •░
    ░░░░░░░░░░░░░░░░░░░F░
    
    ░S░░░░░░░░░░░░░░░░░░░
    ░•••••••░ ░       ░ ░
    ░░░ ░░░•░ ░░░ ░░░░░ ░
    ░   ░•••░ ░ ░     ░ ░
    ░ ░░░•░░░ ░ ░ ░░░ ░ ░
    ░•••••          ░ ░ ░
    ░•░░░░░░░ ░░░░░░░ ░ ░
    ░•░ ░ ░   ░       ░ ░
    ░•░ ░ ░░░░░░░ ░░░ ░ ░
    ░•••░       ░ ░   ░ ░
    ░░░•░ ░░░░░░░ ░░░░░ ░
    ░  •••░ ░ ░     ░   ░
    ░ ░░░•░ ░ ░ ░ ░░░░░ ░
    ░   ░•░ ░ ░ ░  •••░ ░
    ░ ░ ░•░ ░ ░░░░░•░•░ ░
    ░ ░ ░•░   ░   ░•░•••░
    ░ ░░░•░ ░░░░░ ░•░░░•░
    ░   ░•••░   ░•••░ ░•░
    ░ ░░░░░•░ ░░░•░░░ ░•░
    ░   ░  •••••••░    •░
    ░░░░░░░░░░░░░░░░░░░F░
    
    ░S░░░░░░░░░░░░░░░░░░░
    ░•••    ░ ░       ░ ░
    ░░░•░░░ ░ ░░░ ░░░░░ ░
    ░•••░   ░ ░ ░•••••░ ░
    ░•░░░ ░░░ ░ ░•░░░•░ ░
    ░•••••••••••••  ░•░ ░
    ░ ░░░░░░░ ░░░░░░░•░ ░
    ░ ░ ░ ░   ░  •••••░ ░
    ░ ░ ░ ░░░░░░░•░░░ ░ ░
    ░   ░       ░•░   ░ ░
    ░░░ ░ ░░░░░░░•░░░░░ ░
    ░     ░ ░ ░  •  ░   ░
    ░ ░░░ ░ ░ ░ ░•░░░░░ ░
    ░   ░ ░ ░ ░ ░•••••░ ░
    ░ ░ ░ ░ ░ ░░░░░ ░•░ ░
    ░ ░ ░ ░   ░   ░ ░•••░
    ░ ░░░ ░ ░░░░░ ░ ░░░•░
    ░   ░   ░   ░   ░ ░•░
    ░ ░░░░░ ░ ░░░ ░░░ ░•░
    ░   ░         ░    •░
    ░░░░░░░░░░░░░░░░░░░F░
    
    ░S░░░░░░░░░░░░░░░░░░░
    ░•••    ░ ░       ░ ░
    ░░░•░░░ ░ ░░░ ░░░░░ ░
    ░•••░   ░ ░ ░     ░ ░
    ░•░░░ ░░░ ░ ░ ░░░ ░ ░
    ░•              ░ ░ ░
    ░•░░░░░░░ ░░░░░░░ ░ ░
    ░•░ ░ ░   ░       ░ ░
    ░•░ ░ ░░░░░░░ ░░░ ░ ░
    ░•••░       ░ ░   ░ ░
    ░░░•░ ░░░░░░░ ░░░░░ ░
    ░  •••░ ░ ░     ░   ░
    ░ ░░░•░ ░ ░ ░ ░░░░░ ░
    ░   ░•░ ░ ░ ░  •••░ ░
    ░ ░ ░•░ ░ ░░░░░•░•░ ░
    ░ ░ ░•░   ░   ░•░•••░
    ░ ░░░•░ ░░░░░ ░•░░░•░
    ░   ░•••░   ░•••░ ░•░
    ░ ░░░░░•░ ░░░•░░░ ░•░
    ░   ░  •••••••░    •░
    ░░░░░░░░░░░░░░░░░░░F░
    
    NEW MAZE:
    
    ░S░░░░░░░░░░░░░░░░░░░
    ░     ░ ░     ░ ░   ░
    ░ ░ ░░░ ░ ░ ░░░ ░ ░ ░
    ░ ░   ░ ░ ░ ░     ░ ░
    ░ ░ ░ ░ ░░░ ░ ░░░░░░░
    ░ ░ ░ ░ ░         ░ ░
    ░ ░░░ ░ ░ ░░░░░ ░░░ ░
    ░ ░   ░       ░     ░
    ░ ░░░ ░ ░░░ ░░░░░░░ ░
    ░ ░ ░     ░ ░     ░ ░
    ░ ░ ░░░░░ ░░░░░░░ ░░░
    ░ ░   ░   ░   ░   ░ ░
    ░ ░ ░░░░░ ░ ░ ░ ░░░ ░
    ░       ░ ░ ░ ░     ░
    ░ ░ ░░░░░ ░░░ ░ ░ ░ ░
    ░ ░   ░     ░   ░ ░ ░
    ░ ░░░ ░░░░░ ░ ░ ░ ░ ░
    ░   ░     ░ ░ ░ ░ ░ ░
    ░ ░░░░░ ░░░ ░░░ ░ ░░░
    ░ ░     ░     ░ ░   ░
    ░░░░░░░░░░░░░░░░░░░F░
    
    0 solutions(s) found: