Introduction
The purpose of the project is to try in practice the use of recursion and object-oriented program design.Please make sure to read this entire note before starting your work. Pay close attention to the sections on deadlines, deliverables, and exam rules.
The problem
Your task in this part of the project is to write a solver for Sudoku puzzles. Sudoku puzzles are a kind of crossword puzzles with numbers where the following two conditions have to be met:- In each row or column, the nine numbers have to be from the set [1,2,3,4,5,6,7,8,9] and they must all be different.
- For each of the nine non-overlapping 3x3 blocks, the nine numbers have to be from the set [1,2,3,4,5,6,7,8,9] and they ust all be different.
The following two figures show a Sudoku puzzle and its solution.
The input
The input of your program, the Sudoku puzzles, is given in text files.More specifically, they are represented as nine lines of nine characters separated by spaces.
The characters can be of two types:
- A letter “X” signifies an empty cell, i.e., a cell that your solver needs to find a number for.
- A number signifies a cell whose value is fixed, i.e., the corresponding cell needs to have this number in the solution that you find.
Thus, for our example above, would be given the following text file:
X X 8 1 X X 5 X X
9 6 X X 8 X X X X
X 5 X X 3 6 X 9 8
X X 7 X 6 9 X 1 2
X X 6 8 X 7 3 X X
8 1 X 4 5 X 6 X X
4 2 X 6 7 X X 8 X
X X X X 4 X X 6 3
X X 5 X X 8 7 X X
The output
The output of your solver should be a representation of the Sudoku playing field for the solved puzzle. For our example above the output should thus be:+-------+-------+-------+
| 3 7 8 | 1 9 4 | 5 2 6 |
| 9 6 4 | 2 8 5 | 1 3 7 |
| 1 5 2 | 7 3 6 | 4 9 8 |
+-------+-------+-------+
| 5 4 7 | 3 6 9 | 8 1 2 |
| 2 9 6 | 8 1 7 | 3 5 4 |
| 8 1 3 | 4 5 2 | 6 7 9 |
+-------+-------+-------+
| 4 2 1 | 6 7 3 | 9 8 5 |
| 7 8 9 | 5 4 1 | 2 6 3 |
| 6 3 5 | 9 2 8 | 7 4 1 |
+-------+-------+-------+
The abstract data type An abstract data type based on arrays can model the Sudoku playfield.
- It should implement the following operations:
- public void fromFile(String fileName) which initializes the playing field from an input file.
- public boolean tryValue(int val, int i, int j) which returns false if the value val cannot be placed at row i and column j, and it returns true and sets the cell to val otherwise.
- public boolean isEmpty(int i, int j) which checks if the cell at row i and column j is empty.
- public void clear(int i, int j) which sets the cell at row i and column j to empty.
The first task
Write a command line solver for Sudoku puzzles that takes as argument the name of a file containing a Sudoku puzzle and prints the solution to the screen. Implement the solver USING RECURSION!The second task
Write a graphical user interface (GUI) for the solver from the first task. Use Java’s SWING libraries (JPanel, JTable, JFileChooser, JFrame,JButton, JMenu, …) for the GUI implementations, if possible. Write a class “SudokuGUI”, which extends the class “Sudoku” from the first task. Whenever possible use methods you have implemented before in the “Sudoku” class.Proceed as follows:
- Familiarize with the Java class “JFileChooser” (check the Java API).
- When “SudokuGUI” starts, a window shall appear. Here, add the option to load the input file using JFileChooser.
- After loading this file, a table visualization (use, for instance, the class JTable) shall appear (similar to the above left figure).
- In addition, a “Start”-button shall appear, which, if pressed, solves the Sudoku puzzle using the methods implemented in the first task, i.e. the class “Sudoku”, which “SudokuGUI” extends.
- The solution shall be visualized in a table as well.
- Now also include a possibility (using a JFileChooser) to store the results.
Comments
Post a Comment