NQueens/Sudoku Assignment
Contents
 1 Motivation
 2 NQueens
 3 Sudoku
 3.1 Background
 3.2 Roadmap to Victory
 3.3 The Core Questions
 3.4 Code To Investigate
 3.5 Code To Implement
 4 Testing Your Solution
 5 Rubric
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 NQueens problem and Sudoku in parallel.
NQueens in particular can be used to explain the call stack as the chessboard *IS* the call stack.
In this assignment, you will implement solutions to both the NQueens and Sudoku problems.
NQueens
Background
The nqueens 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 attack horizontally, vertically, and diagonally across the board. Thus, to solve the nqueens 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 nqueens for any given n.
Roadmap to Victory
 (Warm Up) SequentialNQueens
 DefaultImmutableQueenLocations
 FirstAvailableRowSearchAlgorithm
 ParallelNQueens
The Core Questions
 What are the tasks?
 What is the data?
 Is the data mutable?
 If so, how is it shared?
Code To Implement
Sequential Warm Up
public static int countSolutions(int boardSize) { MutableInt count = new MutableInt(); int[] board = new int[boardSize]; Arrays.fill(board, EMPTY); search(count, board, 0); return count.intValue(); }
class:  SequentialNQueens.java  
methods:  search  
package:  nqueens.lab  
source folder:  src/main/java 
method: private static void search(MutableInt count, int[] board, int row)
(sequential implementation only)
Parallel Studio
Board State: DefaultImmutableQueenLocations
class:  DefaultImmutableQueenLocations.java  
methods:  createNext getBoardSize getColumnOfQueenInRow getCandidateColumnsInRow 

package:  nqueens.lab  
source folder:  src/main/java 
createNext(row,col)
method: public DefaultImmutableQueenLocations createNext(int row, int col)
(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?
getBoardSize()
method: public int getBoardSize()
(sequential implementation only)
Note that we will refer to the standard 8x8 chessboard's size as 8 and not 64.
getColumnOfQueenInRow(row)
method: public Optional<Integer> getColumnOfQueenInRow(int row)
(sequential implementation only)
For an 8x8 board with queens placed in (row=0, col=1), (row=1, col=6), and (row=2, col=4)
 getColumnOfQueenInRow(0) returns Optional.of(1)
 getColumnOfQueenInRow(1) returns Optional.of(6)
 getColumnOfQueenInRow(2) returns Optional.of(4)
 getColumnOfQueenInRow(3) returns Optional.empty()
 getColumnOfQueenInRow(4) returns Optional.empty()
 getColumnOfQueenInRow(5) returns Optional.empty()
 getColumnOfQueenInRow(6) returns Optional.empty()
 getColumnOfQueenInRow(7) returns Optional.empty()
getCandidateColumnsInRow(row)
method: public List<Integer> getCandidateColumnsInRow(int row)
(sequential implementation only)
For an 8x8 board with a single queen placed in (row=0, col=4)
 getCandidateColumnsInRow(0) returns []
 getCandidateColumnsInRow(1) returns [0,1,2,6,7]
 getCandidateColumnsInRow(2) returns [0,1,3,5,7]
 getCandidateColumnsInRow(3) returns [0,2,3,5,6]
 getCandidateColumnsInRow(4) returns [1,2,3,5,6,7]
 getCandidateColumnsInRow(5) returns [0,1,2,3,5,6,7]
 getCandidateColumnsInRow(6) returns [0,1,2,3,5,6,7]
 getCandidateColumnsInRow(7) returns [0,1,2,3,5,6,7]
The provided isLocationThreatFree(row, col) method should be helpful.
Search Order: FirstAvailableRowSearchAlgorithm
This class will provide methods that will allow us to implement a clean and efficient parallel solution in the final step.
class:  FirstAvailableRowSearchAlgorithm .java  
methods:  selectedNextUnplacedRow  
package:  nqueens.lab  
source folder:  src/main/java 
method: public Optional<Integer> selectedNextUnplacedRow(ImmutableQueenLocations queenLocations)
(sequential implementation only)
For an 8x8 board with queens placed at (row=0, col=0), (row=1, col=3), (row=2, col=6), and (row=6, col=7):
 selectedNextUnplacedRow(queenLocations) returns Optional.of(3)
For a board with no unplaced rows, for example, a solution:
 selectedNextUnplacedRow(queenLocations) returns Optional.empty()
Warning:Do NOT skip empty rows simply because they have no candidate columns 
In cases where a row does not have a queen placed in it, but has no valid candidate columns, for example a 3x3 board with a queen placed at (row=0, col=1):
It is critical that
 selectedNextUnplacedRow(queenLocations) returns Optional.of(1)
When searching for solutions we do not want to avoid dead rows. If anything, we want to move them to the front of the line, so that search can cease the current fruitless path.
ParallelNQueens
Searching for solutions like nqueens 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 a single finish . 
class:  ParallelNQueens.java  
methods:  searchForSolutions countSolutions 

package:  nqueens.lab  
source folder:  src/main/java 
method: public static int countSolutions(ImmutableQueenLocations queenLocations, RowSearchAlgorithm rowSearchAlgorithm)
(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.
Creating a new instance of FinishAccumulator is done via on of the many static methods on the V5 class (the same class we get async and finish from).
Refer to the syntax page in order to see the syntax for properly setting up the accumulator.
method: private static void searchForSolutions(FinishAccumulator<Integer> accumulator, ImmutableQueenLocations queenLocations, RowSearchAlgorithm rowSearchAlgorithm)
(parallel implementation required)
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 9by9 grid of squares. This grid is also divided into 9 large boxes, each of which is a 3by3 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 NQueens by challenging yourself to solve Sudoku's solver without assistance. The game of Sudoku is bit more complex though than NQueens, 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 implement alternate 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 and RowMajorSquareSearchAlgorithm, since these classes closest resembles the work you just did in nqueens. Below is one path that we recommend. In this path, you will build the methods before other methods use them. Many find DefaultConstraintPropagator to be the most challenging part, however. In summary, you can work on these classes in whatever order makes the most sense for you personally.
 DefaultConstraintPropagator
 DefaultImmutableSudokuPuzzle
 RowMajorSquareSearchAlgorithm
 FewestOptionsFirstSquareSearchAlgorithm
 ParallelSudoku
 (Optional Challenge) Add Unit and Twins Constraint Propagation to DefaultConstraintPropagator
The Core Questions
 What are the tasks?
 What is the data?
 Is the data mutable?
 If so, how is it shared?
Code To Investigate
Square
enum Square
 Collection<Square> getPeers()
 valueOf(row, column)
 all enums have a values() method
SudokuUtils
class SudokuUtils
 deepCopyOf(Map<Square, SortedSet<Integer>> other)
 allUnits()
 getRowUnit(row)
 getColumnUnit(col)
 getColumnUnit(row,col)
 getUnitsForSquare(square)
CandidateSet
class CandidateSet<E> implements SortedSet<E>
 public static CandidateSet createAllCandidates()
Code To Implement
Constraint Propagator
class:  DefaultConstraintPropagator.java  
methods:  createCandidateSetsFromGivens createNextCandidateSets assign eliminate 

package:  sudoku.lab  
source folder:  src/main/java 
You will need to implement two public methods to satisfy the ConstraintPropagator interface: createCandidateSetsFromGivens
and createNextCandidateSets
. 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.
createCandidateSetsFromGivens
method: public Map<Square, SortedSet<Integer>> createCandidateSetsFromGivens(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 Map from Square to Optional<Integer>. If a square is given (that is it has a specified starting value) the Optional will be present and its value will be set. If a specific spot of the board wasn't given in the input, it will be empty.
Tip: A good choice for Maps which have enums as their keys is EnumMap. Use new EnumMap<>(Square.class) for an EnumMap of Squares. 
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.
Tip: Square.values() is useful here for iterating over all of the Square enum constants. 
Tip: [CandidateSet.createAllCandidates() is useful here when looking to start a square's candidates off at [1,2,3,4,5,6,7,8,9]. 
Once that is complete go through the givens and get your private method(s) to work for you.
createNextCandidateSets
method: public Map<Square, SortedSet<Integer>> createNextCandidateSets(Map<Square, SortedSet<Integer>> otherCandidateSets, 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 nqueens 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 SudokuUtils.deepCopyOf
method and refrain from mutating the incoming parameter otherCandidateSets
.
As warned above, do not actually do any of the constraint propagation in this method. Simply get the copy of the options set, then leverage your private assign
method (which in turn may leverage eliminate
) to update the copy to be correct before returning it.
Tip: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. 
Assign and Eliminate
Background
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 Peer Elimination Constraint 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:
Two Paths
All Assign All The Time
In this implementation, you will perform all of your work in the assign method. eliminate will never be invoked.
Mutual Recursion
In this implementation, assign and eliminate will take on their own roles, at times calling each other. This implementation leads nicely into the extra credit portion.
assign(resultOptionSets,square,value)
method: private void assign(Map<Square, SortedSet<Integer>> resultOptionSets, Square square, int value)
(sequential implementation only)
Tip:If you are hitting a ConcurrentModificationException here, make sure you are using CandidateSet. 
Tip:If you are hitting a ConcurrentModificationException here and you are using CandidateSet, think about how a chain reaction might be causing what you ensured to no longer be true. 
eliminate(resultOptionSets,square,value)
method: private void eliminate(Map<Square, SortedSet<Integer>> resultOptionSets, Square square, int value)
(sequential implementation only)
DefaultImmutableSudokuPuzzle
As the name suggests, DefaultImmutableSudokuPuzzle
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 work you did for #NQueens.
class:  DefaultImmutableSudokuPuzzle.java  
methods:  constructors createNext getValue getOptions 

package:  sudoku.lab  
source folder:  src/main/java 
constructors
DefaultImmutableSudokuPuzzle has two private final fields:
private final ConstraintPropagator constraintPropagator; private final Map<Square, SortedSet<Integer>> candidateSets;
Each will need to be initialized in both of the constructors.
DefaultImmutableSudokuPuzzle(constraintPropagator,givens)
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 candidate sets.
DefaultImmutableSudokuPuzzle(other,square,value)
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. This will be invoked via a public method on DefaultImmutableSudokuPuzzle during the search process.
createNext(square,value)
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?
getValue(square)
method: public Optional<Integer> getValue(Square square)
(sequential implementation only)
Warning:Ignore any documentation which reports this method should return 0 if it is unfilled. 
Based on the state of the board, return the value of a given square if it is known. Otherwise, return empty.
How do we determine if a value for a given square is "known"?
getCandidates(square)
method: public SortedSet<Integer> getCandidates(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.
To implement them, ask yourself:
 How do I determine if a square is filled?
 How do I find the unfilled square with the minimum number of candidates?
When you have completed them, ask yourself:
 Which algorithm will perform better and why?
 What properties make a square "filled"?
Warning:Do NOT omit squares with 0 candidates. 
RowMajorSquareSearchAlgorithm
class:  RowMajorSquareSearchAlgorithm.java  
methods:  selectNextUnfilledSquare  
package:  sudoku.lab  
source folder:  src/main/java 
method: Optional<Square> selectNextUnfilledSquare(ImmutableSudokuPuzzle puzzle)
(sequential implementation only)
Warning: Ignore any documentation which reports this method should return null if it is completely filled. This method should return Optional.empty() for a completely filled board. 
Simply run through the Square.values()
which will iterate through squares going down the row (A1, A2, A3, ...). Make sure not to return squares that have already been filled.
FewestOptionsFirstSquareSearchAlgorithm
class:  FewestOptionsFirstSquareSearchAlgorithm.java  
methods:  selectNextUnfilledSquare  
package:  sudoku.lab  
source folder:  src/main/java 
method: Optional<Square> selectNextUnfilledSquare(ImmutableSudokuPuzzle puzzle)
(sequential implementation only)
Warning: Ignore any documentation which reports this method should return null if it is completely filled. This method should return Optional.empty() for a completely filled board. 
Go through every square by calling Square.values()
, find a square that is (1) not already filled, and (2) has the minimal number of possible options among all the squares, and return that square.
Solver
This part of the assignment is also similar to its nqueens counterpart. 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
and is, in fact, required by the test.
Warning:Ensure that you complete all of your tasks by enclosing them all in a single finish . 
Tip:Use the iterable version of forasync 
class:  ParallelSudoku.java  
methods:  solve solveKernel 

package:  sudoku.lab  
source folder:  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)
(Optional) Advanced Constraint Propagation
Unit Constraint Propagation
The second rule in Peter Norvig's Essay is Unit Constraint Propagation: "If a unit has only one possible place for a value, then put the value there". This propagation rule is it bit more challenging to put into code, but doing so can make even the hardest of Sudoku puzzles fall nice and quickly. To complete this bonus part of the lab, simply update your assign
and eliminate
methods to do unit constraint propagation (don't remove the old propagation rule!). After assigning a square, you'll have to look at the new options set to see if any unit (a single row, column, or box) has only one unassigned square that is a possibility for any value. We encourage you to think of a solution on your own! Below is a example of unit constraint propagation.
Naked Twins
In what is dubbed a more sophisticated strategy in Peter Norvig's Essay is Naked Twins strategy which "looks for two squares in the same unit that both have the same two possible digits. Given {'A5': '26', 'A6':'26', ...}, we can conclude that 2 and 6 must be in A5 and A6 (although we don't know which is where), and we can therefore eliminate 2 and 6 from every other square in the A row unit. We could code that strategy in a few lines by adding an elif len(values[s]) == 2 test to eliminate."
Tips
 Make sure your solver uses the generic SquareSearchAlgorithm so that it works with both versions of the search ordering.
 Just like nqueens, your
solveKernel
is the recursive method that will be called in the solve method. Again, watch where you put yourfinish
.  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
NQueens
class:  NQueensVizApp.java  VIZ 
package:  nqueens.viz.solution  
source folder:  src/visualization/java 
Sudoku
Propogate
class:  FxSudokuPropagateApp.java  VIZ 
package:  sudoku.viz.propogate  
source folder:  src/visualization/java 
Solve
class:  FxSudokuSolutionApp.java  VIZ 
package:  sudoku.viz.solution  
source folder:  src/visualization/java 
Correctness
Warm Up
class:  SequentialNQueensWarmUpTestSuite.java  
package:  nqueens.warmup  
source folder:  src/test/java 
Lab
There is a toplevel test suite comprised of sub test suites which can be invoked separately when you want to focus on one part of the assignment.
class:  BacktrackTestSuite.java  
package:  backtrack.lab  
source folder:  src/test/java 
NQueens
class:  NQueensTestSuite.java  
package:  nqueens.lab  
source folder:  src/test/java 
ImmutableQueenLocations
class:  ImmutableQueenLocationsTestSuite.java  
package:  nqueens.lab  
source folder:  src/test/java 
FirstAvailableRowSearchAlgorithm
class:  FirstAvailableRowSearchTestSuite.java  
package:  nqueens.lab  
source folder:  src/test/java 
ParallelNQueens
class:  ParallelNQueensSolutionCountTestSuite.java  
package:  nqueens.lab  
source folder:  src/test/java 
Sudoku
class:  SudokuTestSuite.java  
package:  sudoku.lab  
source folder:  src/test/java 
DefaultConstraintPropagator
class:  DefaultConstraintPropagatorTestSuite.java  
package:  sudoku.lab  
source folder:  src/test/java 
DefaultImmutableSudokuPuzzle
class:  DefaultImmutableSudokuPuzzleTestSuite.java  
package:  sudoku.lab  
source folder:  src/test/java 
RowMajorSearchOrder
class:  RowMajorSearchOrderTestSuite.java  
package:  sudoku.lab  
source folder:  src/test/java 
FewestOptionsFirstOrder
class:  FewestOptionsFirstOrderTestSuite.java  
package:  sudoku.lab  
source folder:  src/test/java 
ParallelSudokuSolve
class:  ParallelSudokuSolveTestSuite.java  
package:  sudoku.lab  
source folder:  src/test/java 
Holistic
class:  HolisticTestSuite.java  
package:  sudoku.lab  
source folder:  src/test/java 
Extra Credit Challenge Unit Constraint Propagation
class:  ChallengeSudokuTestSuite.java  
package:  sudoku.challenge  
source folder:  src/test/java 
Rubric
As always, please make sure to cite your work appropriately.
Total points: 100
NQueens subtotal: 35
 Correct DefaultImmutableQueenLocations (10)
 Correct FirstAvailableRowSearchAlgorithm (5)
 Correct ParallelNQueens (10)
 Parallel ParallelNQueens (10)
Sudoku subtotal: 65
 Correct ImmutableSudokuPuzzle (5)
 Correct ContraintPropagator (20)
 Correct RowMajorSearch (10)
 Correct FewestOptionsFirstSearch (10)
 Correct ParallelSudoku (10)
 Parallel ParallelSudoku (10)
Penalties may be assessed for clarity and efficiency.