N-Queens/Sudoku Assignment

Motivation

Not everything in the world should be divided and conquered. Backtracking is a powerful technique which can be readily parallelized. We will gain experience with backtracking by solving the N-Queens problem and Sudoku in parallel.

N-Queens in particular can be used to explain the call stack as the chessboard *IS* the call stack. Whoa.

In this assignment, you will implement solutions to both the n-queens and Sudoku problems.

N-Queens

Example solution of N-Queens when n equals 8

Background

The n-queens problem is a fundamental coding puzzle which asks: how can N queens be placed on an NxN chessboard so that they cannot attack each other? In chess, a queen can move horizontally, vertically, and diagonally across the board. Thus, to solve the n-queens problem, we must effectively figure out how to place the queens in such a way that no two of them occupy the same row, column, or diagonal. We will be building a method that finds the total number of solutions for n-queens for any given n.

Roadmap to Victory

1. DefaultImmutableQueens
2. QueenLocationsUtils
3. SequentialNQueens
4. ParallelNQueens

Code To Implement

Before coding anything, take a look at the javadocs to see what everything does and what you will need to implement.

Sequential Solution

	public static int countSolutions(MutableQueenLocations queenLocations) {
		MutableInt count = new MutableInt(0);
		placeQueenInRow(count, queenLocations, 0);
		return count.intValue();
	}

class:	SequentialNQueens.java
methods:	placeQueenInRow
package:	nqueens.lab
source folder:	student/src/main/java

method: private static void placeQueenInRow(MutableInt count, MutableQueenLocations queenLocations, int row) (sequential implementation only)

Parallel Solution

Board State

Investigate DefaultMutableQueenLocations and AbstractQueenLocations for clues on how to implement DefaultImmutableQueenLocations.

class:	DefaultImmutableQueenLocations.java
methods:	createNext getColumnOfQueenInRow getRowCount getBoardSize
package:	nqueens.lab
source folder:	student/src/main/java

method: public DefaultImmutableQueenLocations createNext(int column) (sequential implementation only)

There are two constructors for this class. A public one which creates a fresh new board state with no queens yet placed. and a private one which creates a new board with the state of a given board which is further constrained by a new queen in the next row. You need to create a new instance using one of these two constructors. Which one is it?

method: public int getColumnOfQueenInRow(int row) (sequential implementation only)

method: public int getRowCount() (sequential implementation only)

method: public int getBoardSize() (sequential implementation only)

The three methods above can all be done in just one line. Don't make things too complicated! Note that we will refer to the standard 8x8 chessboard's size as 8 and not 64.

method: public boolean isNextRowThreatFree(int column) (sequential implementation only)

Do not feel compelled to build this method from scratch. Investigate your super class for a utility method that will be helpful.

isCandidateThreatFree(row, candidateColumn)

Board Utils

This class will provide methods that will speed up our implementation of the parallel solution in the final step.

class:	QueenLocationsUtils.java
methods:	getCandidateColumns getCandidateColumnsForNextRow
package:	nqueens.lab
source folder:	student/src/main/java

method: public static Collection<Integer> getCandidateColumns(QueenLocations queenLocations, int row) (sequential implementation only)

This method should find all the columns in the given row that a queen could be placed, and return them in a single collection (ex. LinkedList). Don't forget to utilize some of the methods you just completed in DefaultImmutableQueensLocation

method: public static Collection<Integer> getCandidateColumnsForNextRow(ImmutableQueenLocations queenLocations) (sequential implementation only)

Nice and simple, don't overthink it! Just use methods you've already written to do all the work.

ParallelNQueens

Searching for solutions like n-queens can be done in parallel without the need to finish at each level. As such, forasync is preferable to forall. However:

Warning:Ensure that you complete all of your tasks by enclosing them all in a finish.

class:	ParallelNQueens.java
methods:	placeQueenInRow countSolutions
package:	nqueens.lab
source folder:	student/src/main/java

method: public static int countSolutions(ImmutableQueenLocations queenLocations) (parallel implementation required)

Warning:FinishAccumulators must be registered with their finish statement

Instead of using a MutableInt in order to count the number of solutions we have found, we want to use a Finish Accumulator. The slide below shows syntax for setting one up, and it is also listed in the #Tips section.

slide

method: private static void placeQueenInRow(FinishAccumulator<Integer> acc, ImmutableQueenLocations queenLocations) (parallel implementation required)

Make sure you look at the Sequential N-Queens solution if you need ideas on how to approach the algorithm.

Tips

• As ImmutableQueenLocations is immutable, you will need to create a new instance of the object whenever you move on from one row to the next. This is where createNext comes in, along with the private constructor of this class.
• The isNextRowThreatFree method can easily be completed with a method in AbstractQueenLocations. Refer to that for help.
• The sequential solution uses MutableQueenLocations while the parallel solution uses your implementation of ImmutableQueenLocations. Be careful to use the correct QueenLocations implementation.
• As the name suggests, placeQueenInRow will go through the columns of the given row to check if a queen can fit in that location. If it can, it will set that value in MutableQueenLocations. If the examined row is that last row of the board, you have found one valid solution to the n-queens problem. Update the correct parameter accordingly. Otherwise, recurse and keep going until you reach the last row.
• For the parallel implementation of placeQueenInRow, we are using the "one-finish" pattern. Do not call finish in the recursive method.
• The syntax for instantiating a FinishAccumulator of Integer is: FinishAccumulator<Integer> acc = newIntegerFinishAccumulator(NumberReductionOperator.SUM);
• The syntax for using a FinishAccumulator is: finish(register(acc), () -> { //body });

Sudoku

Background

We will be using a similar algorithm to solve a Sudoku puzzle. For those not familiar, a Sudoku puzzle is composed of a 9-by-9 grid of squares. This grid is also divided into 9 large boxes, each of which is a 3-by-3 of the smaller squares. In a completed puzzle, each of the smaller squares contains a single number from 1 to 9 (inclusive). However, if a square contains a given number, that same number cannot be anywhere else in the same row, column, or box. Thus, for Sudoku, we are given an incomplete board and must fill in the remaining squares while meeting these requirements.

Sudoku is another problem well solved by backtracking. Check the understanding you gained of backtracking with N-Queens by challenging yourself to solve Sudoku's solver without assistance. The game of Sudoku is bit more complex though than N-Queens, and there are more strategies we can do than just backtracking in order to speed up our solution. To make this assignment more compelling, you will also do search orderings and constraint propagation.

Read Peter Norvig's Essay before you begin coding. It will cover everything related to the Sudoku problem itself and how one can design a solution for it.

Roadmap to Victory

There isn't one easiest path through the required files. Some classes utilize methods written in other files, so some students may take a the path such that they will only call methods that are provided or have already implemented. For other students, it might be conceptually easier to start with ParallelSudoku.java, since this class closest resembles the work you just did in n-queens. Below is one path that we recommend. In this path, you will have to call the constraint propagator in the Immutable Puzzle before completing the actual propagator, but aside from that most methods build on top of one another. In summary, you can work on these classes in whatever order makes the most sense for you personally.

1. DefaultImmutableSudokuPuzzle
2. RowMajorSquareSearchAlgorithm
3. FewestOptionsFirstSquareSearchAlgorithm
4. ParallelSudoku
5. DefaultConstraintPropagator
6. (Optional Challenge) Add Unit Constraint Propagation to DefaultConstraintPropagator

Code To Investigate

enum Square

Collection<Square> getPeers()

valueOf(row, column)

all enums have a values() method

class Units

public static Iterable<Collection<Square>> allUnits()

interface ConstraintPropagator extends AbstractSet<Integer> implements SortedSet<Integer>

class OptionSet

public static OptionSet createAllOptions()

public static OptionSet createSingleOption(int option)

class SquareToOptionSetMapUtils

public static Map<Square, SortedSet<Integer>> deepCopyOf(Map<Square, SortedSet<Integer>> other)

Code To Implement

Constraint Propagator

class:	DefaultConstraintPropagator.java
methods:	createOptionSetsFromGivens createNextOptionSets assign eliminate
package:	sudoku.lab
source folder:	student/src/main/java

You will need to implement two public methods to satisfy the ConstraintPropagator interface: createOptionSetsFromGivens and createNextOptionSets. Each of these two methods will be invoked from a different constructor in the #DefaultImmutableSudokuPuzzle class. It should be relatively obvious which one goes with which based on the parameters.

Warning: Resist the temptation to perform the constraint propagation in these public methods. Get things set up and then get your private method(s) to work for you.

createOptionSetsFromGivens

method: public Map<Square, SortedSet<Integer>> createOptionSetsFromGivens(String givens) (sequential implementation only)

This method will be invoked when you have loaded a new puzzle. Whether it is from the newspaper, or your airline magazine, or Dr. Arto Inkala there is a set of givens the puzzle creator has provided. That string of givens is parsed into a double array of integers that aligns with the Sudoku board (values[0][0] is the top left corner of the board). If a specific spot of the board wasn't given in the input, it will be put into values[][] as 0.

A good approach here is to start of by initializing all of the squares to all the options (1 through 9) whether or not the square has a given value.

Once that is complete go through the givens and get your private method(s) to work for you. Note: Square.valueOf(row, column) should be useful here.

createNextOptionSets

method: public Map<Square, SortedSet<Integer>> createNextOptionSets(Map<Square, SortedSet<Integer>> otherOptionSets, Square square, int value) (sequential implementation only)

This method should be invoked when you are searching for the solution in your solver. Much like when you need to create a new copy of the board every time you make a decision in the n-queens search so too will you need to create a new copy of your sudoku board every time you make a decision in your backtracking search.

Make sure to use the SquareToOptionSetMapUtils.deepCopyOf method and refrain from mutating the incoming parameter otherOptionSets.

As warned above, do not actually do any of the constraint propagation in this method. Simply get the copy of the options set, then send it through your private assign and eliminate to update the copy to be correct before returning it.

Assign and Eliminate

Peter Norvig's Essay is very helpful here. We have adopted his terms, but challenge yourself to complete this section without simply translating his pseudocode.

To simplify things a bit, we have elected to not short circuit when a 0 option square is found (relying on the search ordering to take care of that for us).

It is up to you how to utilize these two methods. The goal is to update the map that is passed in to reflect the "solving" of a square. For example, if assign is called on square A1 for the value 1, the map that is returned should link the square A1 to a list containing just the value 1 ([1]). Furthermore, any square that is a peer of A1 (ex. B1), should not have the value 1 in its set in the map.

But in solving Sudoku, there are some strategies that we can rely on to more efficiently complete the puzzle. The first one, and required in order to finish this lab, is Square Propagation (rule 1 in the Norvig essay). The rule is as follows: "If a square has only one possible value, then eliminate that value from the square's peers."

Let's very slowly walk through a example of this propagation in detail to make it more clear what we are looking for. Start by looking at this nearly finished board:

Board	Info
	We can see that the red square (D1) has only one available option. At this point, let's say we call assign on the red square D1 for the value 1.
	As part of the assignment process, all the peers of red square D1 have the value 1 removed from their possibilities. In this example, yellow square, A1, is directly affected! After eliminating the alternative option, there is only one possible value yellow square A1 could be. This is where our constraint propagator needs to take the next step and treat yellow square A1 as assigned.
	This step right here (going from a small 1 to a big 1) is not actually something our program will do. In our implementation, having only one option in a square's set is equivalent to that square being "assigned" to that value. Because of this, you actually do not need to call assign again for yellow square A1.
	Now that yellow square A1 is known, the final step is to go through all of A1's peers (including green square C3) and remove the value 7. Note that now there is only one possible option left for green square C3. Your code would in theory keep going, looking at all the peers of C3 and eliminating the value 1.

method: private void assign(Map<Square, SortedSet<Integer>> resultOptionSets, Square square, int value) (sequential implementation only)

Warning:If you are hitting a ConcurrentModificationException here, make sure to make a copy of the optionsSet you are iterating over. Use your local utility copyOf method.

	SortedSet<Integer> copy = copyOf(optionSet);
	for (int otherValue : copy) {
		...

method: private void eliminate(Map<Square, SortedSet<Integer>> resultOptionSets, Square square, int value) (sequential implementation only)

Puzzle

Since we will be solving sudoku in parallel, you will create an new immutable puzzle for each task. This is analogous to the work you did for #NQueens.

class:	DefaultImmutableSudokuPuzzle.java
methods:	constructors createNext getValue getOptions
package:	sudoku.lab
source folder:	student/src/main/java

method: public DefaultImmutableSudokuPuzzle(ConstraintPropagator constraintPropagator, String givens) (sequential implementation only)

This constructor creates a puzzle constrained to an initial set of givens. You can think of the givens as the original values provided by the newspaper or airline magazine or puzzle book or whatever.

You will leverage the constraintPropagator to build your map of option sets.

method: private DefaultImmutableSudokuPuzzle(DefaultImmutableSudokuPuzzle other, Square square, int value) (sequential implementation only)

This constructor takes a given previous puzzle and a square value to create a new further constrained puzzle.

method: public ImmutableSudokuPuzzle createNext(Square square, int value) (sequential implementation only)

This method should create a new puzzle instance using one of the constructors. Which one is it?

method: public int getValue(Square square) (sequential implementation only)

Based on the state of the board, return the value of a given square if it is known. Otherwise, return 0.

How do we determine if a value for a given square is "known"?

method: public SortedSet<Integer> getOptions(Square square) (sequential implementation only)

Based on the state of the board, return the candidate values for a given square.

Search Order

Simply by changing the search order, a great reduction of work can be achieved. The class names sadly give away the approaches.

Ask yourself:

• Which algorithm will perform better and why?
• What properties make a square "filled"?

class:	RowMajorSquareSearchAlgorithm.java
methods:	selectNextUnfilledSquare
package:	sudoku.lab
source folder:	student/src/main/java

method: public Square selectNextUnfilledSquare(SudokuPuzzle puzzle) (sequential implementation only)

Simply run through the Square.values() which will return you the Squares in row-major order.

class:	FewestOptionsFirstSquareSearchAlgorithm.java
methods:	selectNextUnfilledSquare
package:	sudoku.lab
source folder:	student/src/main/java

method: public Square selectNextUnfilledSquare(SudokuPuzzle puzzle) (sequential implementation only)

Write pseudocode for finding the minimum item in a collection to get on the right track.

Solver

Searching for solutions like sudoku can be done in parallel without the need to finish at each level. As such, forasync is preferable to forall. However:

Warning:Ensure that you complete all of your tasks by enclosing them all in a finish.

class:	ParallelSudoku.java
methods:	solve solveKernel
package:	sudoku.lab
source folder:	student/src/main/java

method: public static ImmutableSudokuPuzzle solve(ImmutableSudokuPuzzle puzzle, SquareSearchAlgorithm squareSearchAlgorithm) (parallel implementation required)

method: private static void solveKernel(MutableObject<ImmutableSudokuPuzzle> solution, ImmutableSudokuPuzzle puzzle, SquareSearchAlgorithm squareSearchAlgorithm) (parallel implementation required)

Tips

A couple of notes and common issues:

• As the name suggests, ImmutableSudokuPuzzle is immutable, and you will need to create a new instance of the object whenever you move on from one square to the next. This is analogous to the immutable n-queens board.
• If you have two Lists, a and b, and you set a = b, then any changes you make to a will also be made to b. Both variables reference the same objects; they are not copies.
• You will need to implement getValue. Look to the instances fields for what will be useful here.
• Your solvers should be able to handle two different approaches to picking the next square in the puzzle to examine: row major and fewest options first. Row major just means going through the puzzle row by row, while fewest options first means solving the puzzle in the order of which squares has the fewest options.
  • For fewest options first, go through every square (you can do this by calling Square.values()) and see how many options are available for each square. Return the square with the minimal number of options. However, check to make sure the puzzle is not already completed or that you are returning already filled squares.
• Just like n-queens, your solveKernel is the recursive method that will be called in the solve method. Again, watch where you put your finish.
• In your solveKernel method, you should use the given search algorithm (row major or fewest options first) to select which square you will fill. After selecting a square, you should recursively call the kernel to check every viable option in the context of the puzzle. If there are no more unfilled squares, you should set the value of the solution to the finished puzzle and exit out of the recursion.

Testing Your Solution

Visualization

N-Queens

class:	NQueensVizApp.java	VIZ
package:	nqueens.viz.solution
source folder:	student/src//java

Sudoku

class:	SudokuSolutionApp.java	VIZ
package:	sudoku.viz.solution
source folder:	student/src//java

Correctness

There is a top-level test suite comprised of sub test suites which can be invoked separately when you want to focus on one part of the assignment.

top level

class:	BacktrackTestSuite.java
package:	backtrack.lab
source folder:	testing/src/test/java

sub

class:	NQueensTestSuite.java
package:	nqueens.lab
source folder:	testing/src/test/java

class:	SudokuTestSuite.java
package:	sudoku.lab
source folder:	testing/src/test/java

(Optional) Challenge Unit Constraint Propagation

class:	ChallengeSudokuTestSuite.java
package:	sudoku.challenge
source folder:	testing/src/test/java

Rubric

As always, please make sure to cite your work appropriately.

Total points: 100

N-Queens subtotal: 35

• Correct DefaultImmutableQueenLocations (5)
• Correct SequentialNQueens (10)
• Correct ParallelNQueens (10)
• Parallel ParallelNQueens (10)

Sudoku subtotal: 55

• Correct DefaultImmutableSudokuPuzzle (5)
• Correct ContraintPropagator (15)
• Correct RowMajorSquareSearchAlgorithm (5)
• Correct FewestOtionsFirstSquareSearchAlgorithm (10)
• Correct ParallelSudoku (10)
• Parallel ParallelSudoku (10)

Whole project:

• Clarity and efficiency (10)