Question

need help with java

In this program you will use a Stack to implement backtracking to solve Sudoku puzzles.

Part I. Implement the stack class.

•  Created a generic, singly-linked implementation of a Stack with a topPtr as the only instance variable. Implement the following methods only:

  public MyStack() //the constructor should simply set the topPtr to null public void push(E e)
  public E pop()

•  Test your class thoroughly before using it within the soduku program

• Part II. Create a class to keep track of a move

 Your move class will need to store the move (a digit 0-9) as well as the row and column of the move.

Part III. Write the program to solve the Sudoku puzzles.

•  An input file, puzzles.txt, containing 10 unsolved puzzles is found on Pilot.

•  Your program should use a 9 x 9 array of integers (NOT an arrayList) to store a puzzle.

•  For each puzzle in the file:

  •  Read the puzzle name and the data for the puzzle from the file into this array. Blank spaces will be

    represented by 0’s in the file.

  •  Display the puzzle number that was read from the file and the unsolved puzzle. You may display the 0’s or display blanks, whichever you prefer. Use vertical and horizontal separators as shown on the sample output on the next page.

  •  Solve the puzzle. The basic algorithm is:

    •  Move to the first square containing a 0. Replace the 0 with a digit 1-9. Be sure the digit is not

      already in the current row, column, or 3x3 section of the grid. Use a stack to keep track of all moves. Once you have placed a digit in that square, move to the next square containing a 0 and do the same.

    •  If your program is unable to find a digit for a particular square, you must backtrack (use the stack). Go to the previous square and change the digit there. If there is no other digit that can go there, change it back to a 0 and backtrack to the square previous to that square.

    •  All puzzles in the file have a solution.

  •  Display the solution to an output file (all solutions to the same file).

Answer 1

class MyStack<T> {

        private class Node {
                T data;
                Node next;
        }

        private Node topPtr;
        
        public MyStack() {
                topPtr = null;
        }

        public void push(T item) {
                Node node = new Node();
                node.data = item;
                node.next = topPtr;
                topPtr = node;
        }

        public boolean isEmpty() {
                return topPtr == null;
        }

        public T peek() {
                return topPtr.data;
        }

        public T pop() {
                T t = peek();
                topPtr = topPtr.next;
                return t;
        }

        public String toString() {
                String result = "TOP: ";
                Node temp = topPtr;
                while (temp != null) {
                        result += temp.data + " | ";
                        temp = temp.next;
                }
                return result;
        }

        public void clear() {
                topPtr = null;
        }
}

This is a very big question, and would require solutions in part.. i am first coding a stack which has been asked in your first part of the question. i would request you to please post separate questions one by one by giving the code available from previous sections, so that we can solve it in the given time limit. Thanks!