Lab:
Latin Squares
Think you're done? Download puzzlemonster.txt, if you dare!
Background
A Latin square is an n × n grid, where each cell contains an integer from 1 to n, and each row and column contain all n values. Here are a few examples:
1 2 2 1 3 1 3 4 2
2 1 3 2 1 4 2 3 1
1 3 2 2 4 1 3
3 1 2 4
The following is not a Latin square. Do you see why?
1 2 3
2 3 1
3 2 1
In a Latin square puzzle, you are given a square grid with some numbers filled in, and it's up to you to fill in the remaining cells to form a valid Latin square. For example:
1 . . .
. . 4 2
. . 2 .
. . . .
(Note that a Sudoku puzzle is really just a Latin square puzzle with an additional constraint.)
In this lab, you'll use recursive backtracking to solve Latin square puzzles. Here is a high-level outline for a recursive backtracking algorithm:
// if solvable, solve puzzle and return true; otherwise return false
public boolean solve()
{
if already solved, return true
for each move
{
execute this move
if (solve()) return true; // return true if can solve from here
undo this move
}
return false; // already tried every move and none led to solution
}
The Code
Download latinsquarelab.zip. Inside you'll find:
a number of .txt files containing puzzles that can be loaded by the PuzzleDisplay class.
PuzzleDisplay.java - A user interface for displaying cross sum puzzles. This code won't compile yet, because it depends on the Puzzle class, which you'll need to write. You should never need to look at this code. Here is a reference for the PuzzleDisplay class:
PuzzleDisplay(String fileName)
constructor for solving the puzzle in the given file
void valueChanged(int row, int col)
informs the display that the value in the given white box has been changed or cleared
Exercise 1: The Puzzle Class
Create a class called Puzzle, which will represent a single Latin square puzzle. For an n × n puzzle, the values stored in the puzzle will be integers from 0 to n, where the value 0 indicates that the cell is empty. It's up to you to create appropriate fields and choose appropriate data structure(s) to store those values. Implement the following constructor and methods in the Puzzle class.
Puzzle(int size)
constructs a Puzzle with given number of rows and columns
precondition: size > 0
int getSize()
returns the number of rows or columns
int getValue(int row, int col)
returns the value at the given location (row 0 is the top row and column 0 is the leftmost column); returns 0 if the cell is empty
preconditon: row and col are valid for this puzzle
void setValue(int row, int col, int value)
sets the value at the given location to be the given value
preconditon: row and col are valid for this puzzle; 0 <= value <= getSize()
boolean isValid(int row, int col)
simply returns true ... for now
preconditon: row and col are valid for this puzzle
boolean solve(PuzzleDisplay display)
simply returns true ... for now
Once you have completed these methods, the PuzzleDisplay class will compile successfully. Try out your code by constructing a new PuzzleDisplay, passing the name of a puzzle file to the PuzzleDisplay constructor. The PuzzleDisplay will load the file contents into a new Puzzle object, and will then allow you to work on the puzzle. The Clear button at the bottom of the user interface should clear any values you have entered, but the other buttons will not do anything yet.
Exercise 2: isValid
Complete the Puzzle class's isValid method. Assume that the given cell contains an integer in the range from 1 to n. The method returns true if that value does not appear in the same row or column. For the example puzzle below, isValid(1, 1) returns true (because that cell contains the only 3 in the center row and center column), while isValid(1, 2) returns false (because there is another 1 in the rightmost column).
1 2 3
2 3 1
3 2 1
If your code works correctly, the PuzzleDisplay will show invalid numbers in red. (Note that the PuzzleDisplay updates only when the cursor is moved to another cell.) Try testing your code on puzzle4.txt, which should be large enough for you to identify any errors.
Exercise 3: solve
In this exercise, you'll complete the solve method, which uses recursive backtracking to solve the puzzle or to report that it cannot be solved. First, let's work through some examples. Suppose the puzzle appears as follows.
3 1 2
2 3 1
1 2 3
This puzzle has no more empty spaces. You therefore assume that it has been solved and return true. That's your base case.
Here's another example. Suppose the puzzle appears as follows.
3 1 .
2 3 1
1 2 3
You place a 1 in the empty cell, and you determine that choice is invalid. You are sad. Then you place a 2 in the empty cell, and you determine that choice is valid. You are happy. You make a recursive call, and it returns true, telling you that the puzzle has already been solved. You are super happy, and therefore you return true.
Here's a third example. Suppose the puzzle appears as follows.
1 3 2
. . 1
. 2 .
You pick any empty space. Let's suppose you pick the leftmost cell in the middle row. You place a 1 in that cell, and you determine that choice is invalid. You frown. You now place a 2 in that cell, and you determine that choice is valid. You smile. You make a recursive call, and it returns false, telling you that the puzzle cannot be solved. Frustrated, you therefore place a 3 in that cell, and you determine that choice is valid. You feel better. You make a recursive call, and it returns false again, telling you that the puzzle still cannot be solved. You are furious now! Having tried every value in this cell, you conclude that this puzzle cannot be solved. You leave the cell empty, return false, and resist the urge to put your fist through a wall.
Here's a summary of the algorithm.
Return true if all cells have been filled.
Otherwise, pick any single empty cell.
Try placing a 1 in that cell, then a 2, then a 3, and so on. Each time you do, call PuzzleDisplay's valueChanged method, so you can see your code's choices on the screen.
Return true if any choice is valid and a recursive call returns true.
Leave that cell empty and return false if all values were unsuccessful.
Notice that you must call call PuzzleDisplay's valueChanged method in order to see your code's progress in the PuzzleDisplay.
Test that your code can now solve any puzzle, using the Step and Run buttons in the user interface. (This may take a while, depending on the difficulty of the puzzle.) When your code solves the puzzle, you will see the solution appear. When your code determines that the puzzle cannot be solved, a window will report that something is not right. In this case, all boxes should contain their original values.
Additional Credit Suggestions
Modify isValid to test if the puzzle is 9×9. If so, assume it's a Sudoku puzzle and determine if that value is valid for Sudoku.
When your solve method chooses an empty cell to fill, choose the most constrained cell (the one with the fewest valid choices).
Use recursive backtracking to generate your own Latin square puzzles or Sudoku puzzles. Here's how. (1) Make a helper method called solveRandom, that works exactly like solve, but it makes random choices. Test solveRandom by feeding it an empty puzzle (all zeros). Each time you run it, you should see a different random Latin square. In theory, you could now take one of these completed Latin squares and remove values at random to produce a puzzle. But, if you remove too many numbers, you may end up with an invalid puzzle--one that has multiple solutions. Therefore, the next step is to count how many solutions your puzzle has. (2) Make another helper method called countSolutions, which also works exactly like solve, except that it returns an int instead of a boolean. The int you return represents the number of ways the puzzle can be solved. (3) Finally, write a method that creates an empty puzzle (all zeros), uses solveRandom to fill it in with random values, and then picks random non-empty cells forever. If the value in that cell is essential (removing it would introduce new solutions) then put it back. If the value in that cell is inessential (removing it would not introduce new solutions), then remove it and print out the contents of the puzzle.
Use recursive backtracking to solve any other kind of puzzle, such as: virtually any newspaper puzzle, peg solitaire, sliding block puzzles (e.g. Rush Hour), an anagram generator, verbal arithmetic (e.g. SEND + MORE = MONEY), any NP-Complete problem (e.g. hamiltonian cycle), any other one-player deterministic puzzle game without hidden information, and where each move brings you closer to a solution or dead end (e.g. your favorite puzzle app).