Assignment 4 Solution

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 di erent 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 mathdoku1 (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 identi ed 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 rst 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.


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






1

4+
2=
75

2 =



2
4 =
5 =
60


1 =
8

1
1




8+




Figure 1: A mathdoku puzzle.















4+


2=

75




2 =

1


4

3
5


2
































2


4 =

3

2
5

1


4

























5 =


60






1 =

5


3
4
2


1













8




1

1




2

5

1

4

3




















8+




4

1
2

3

5


























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 nd 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 e cient. In this case e ciency 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.






2
Inputs

The loadPuzzle method will accept a description of the puzzle as an input stream. The input stream will be formatted in three sections as follows:

Section 1: Consists of an integer n which gives the size of the puzzle (an n  n grid)

Section 2: Consists of the puzzle square itself. For an n n puzzle square, the input will have n lines of input, each being a string of n characters (excluding the end of the line character). For one line, the n characters are the n cells in the line; each cell is a letter that represents the cell grouping to which the cell belongs.

Section 3: Consists of the constraints for each cell grouping in the puzzle. There will be one line for each cell grouping. That line will have 3 values: the letter representing the grouping, the operation outcome for the grouping, and the operator for the grouping (one of +, -, *, /, or =). The values are separated from one another by at least one space.


Example: The puzzle in Figure 1 would be represented as the following input. The constraints are given alphabetically by the grouping name here, but that’s not a guarantee in all input.

5

abccd

abcef

ghhei

jhkll

jjkmm

a 4 +

b 2 /

c 75 *

d 2 =

e 2 *

f 4 =

g 5 =

h 60 *

i 1 =

j 8 *

k 1 -

l 1 -

m 8 +

















3
Input validation

In many programs, such as compilers, there are multiple stages of input validation to check more complex properties of the input. The validate method performs additional input validation to check whether the input loaded by the loadPuzzle method speci es a valid mathdoku puzzle.

Some conditions you will need to check in your validate method (if you already check some of these in your loadPuzzle, that is ne) are:

The cells form an n  n grid

Every grouping is a connected set of cells | that is, there are no \gaps" between cells in a grouping.

Every grouping has a value and an operator

Every grouping with the = operator has exactly one cell

Every grouping with the    or = operator has exactly two cells

Every grouping with the + or  operator must have at least two cells


Outputs

The print method produces a String that represents the current state of the puzzle. The output provides each row of the current puzzle state; listed from top-to-bottom and rows separated by a carriage return (\n) character. No space is printed between the columns of the rows. If the cell has a value from 1 to n assigned to it then print that value for the cell. Otherwise, print the grouping letter for the cell.

The following is the returned string for the puzzle in Figure 2, noting that \n should be seen as just one character (newline character) in the text below:

14352\n32514\n53621\n25143\n41235\n


Assumptions

None.


Constraints

The character for each cell grouping is case sensitive. So, a cell entered as a and another as A are two di erent groupings.

You may use any data structures from the Java Collection Framework. You may not use an existing library that already solves this problem.

If in doubt for testing, I will be running your program on timberlea.cs.dal.ca.  Correct operation of your program shouldn’t rely on any packages that aren’t available on that system.







4
Notes

Develop a strategy on how you will solve the puzzle before you start coding your data structure(s) for the puzzle

Work incrementally. First write the code to read in a puzzle. Test that. Next, write the code to print the current state of the puzzle. Test that. Then, write the code to validate the puzzle. Test that. Last, write your code to solve the puzzle.

It might be helpful to start by brute-forcing the puzzle | speci cally, try every possible number in each cell and check to see if it’s a solution. You probably won’t be able to solve large puzzles this way, so start with something small like a 4 4 grid. Check http://www.mathdoku.com/ for sample puzzles.

Once you have a working solution, think about ways in which you can make your solution more e cient. For example, if a grouping contains only one cell, do you need to try all possible values in that cell or can you simply infer the correct value for that cell? Note that there is no one solution to making your code e cient.

Do not change any of the given class names, method names or method signatures. Do not mark any of variables or methods in your class as static.

What to submit

Your Mathdoku.java  le and any other supporting java  les. { Do not include package statements in your java  le(s).

A separate .pdf  le with

{ A list of your test cases for the problem.

{ An explanation of your solution | speci cally, the strategy/algorithm you use to solve the puzzles, as well as what steps you have taken to provide some degree of e ciency.


Marking scheme (out of 25)

Documentation, program organization, clarity, modularity, style { 4 marks List of test cases for the problem - 3 marks

Explanation of your solution - 3 marks Ability to solve puzzles - 12 marks

E  ciency of your solution - 3 marks












5