CSCI3901-Assignment 4 Solved

Problem 1
Goal

Work with exploring state space and backtracking.

Background
Some games and puzzles like sudoku can be solved with a computer by systematically exploring all possible solutions, called the state space, until a correct solution is found. They do this by backtracking to a previous state whenever an incorrect solution is found, and then continuing from that point by exploring different possible solutions. In this assignment you will write a program to solve a mathematical puzzle which is closely related to sudoku by backtracking and state space exploration.

You will be solving a puzzle called mathdoku[1] (see http://www.mathdoku.com). Figure 1 shows a sample puzzle. In a mathdoku puzzle, you are given a square n × n grid. Within the grid, each cell is identified as part of some grouping. Each grouping is a connected set of 1 or more cells and each grouping is given

1.   a mathematical operator like + or /, and

2.   an integer which is the result of applying the operator to the cells.

The task is to put the integers 1 to n into the cells of the grid so that:

•   No integer appears twice in any row

•   No integer appears twice in any column

•   Applying the operator to the values in a grouping gives the integer assigned to that grouping.

Figure 2 shows a solution to the puzzle in Figure 1.

The possible operators for a cell are + for addition, − for subtraction, ∗ for multiplication, / for division, and = to specify that a grouping (of one cell) has a given value. For the − and / operations, the groupings must have exactly 2 cells, and the larger value always comes first in the computation. For example, if the operation is / and the values are 2 and 6, the result of that grouping would be

6/2 = 3.

The results of operations on groupings must always be integers, so 4/3 is not a valid assignment.

4+
2/
75×
 
2=
 
4+

1
2/

4
75∗

3
5
2=

2
 
 
 
2×
4=
3
2
5
2∗

1
4=

4
5=
60×
 
 
1=
5=

5
60∗

3
4
2
1=

1
8×
 
1−
1−
 
8∗

2
5
1−

1
1−

4
3
 
 
 
8+
 
 
 
 
8+
 
 
 
 
 
 
 
4
1
2
3
5
                    Figure 1: A mathdoku puzzle.                  Figure 2: The solution to the puzzle in Figure 1.

Problem
Your task is to create a class called Mathdoku that accepts a puzzle and ultimately solves it. The class has at least 5 public methods with the following signatures:

 

public boolean loadPuzzle(BufferedReader stream) Read a puzzle in from a given stream of data. Further description on the puzzle input structure appears below. Return true if the puzzle is read successfully. Return false if some other error happened.

public boolean validate() Determine whether or not the loaded puzzle is valid. Return true if the puzzle is valid and can be solved, and return false otherwise. Further information on this method appears below.

public boolean solve() Do whatever you need to do to find a solution to the puzzle. The method should store the solution in the object so that it can be retrieved later. Return true if you solved the puzzle and false if you could not solve the puzzle. This method should also keep track of the number of guesses you make in the process of solving the puzzle, and then store this in the object to be retrieved later by the choices method below.

public String print() Return the current puzzle state as a String object.

public int choices() Return the number of guesses that your program had to make and later undo/backtrack while solving the puzzle.

 

You get to choose how you will represent the puzzle in your program and how you will proceed to solve the puzzle. The only constraint on your solution is that it should be somewhat efficient. In this case efficiency means that you explore as few solutions as possible before arriving at a correct one or discovering that there is no solution to the puzzle.


 
[1] These puzzles appear under the trade name of KenKen (https://www.kenkenpuzzle.com).