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 attack 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. (Warm Up) SequentialNQueens
2. DefaultImmutableQueenLocations
3. FirstAvailableRowSearchAlgorithm
4. 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:	student/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:	student/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:	student/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 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 a single finish.

class:	ParallelNQueens.java
methods:	searchForSolutions countSolutions
package:	nqueens.lab
source folder:	student/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 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 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 n-queens. 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.

1. DefaultConstraintPropagator
2. DefaultImmutableSudokuPuzzle
3. RowMajorSquareSearchAlgorithm
4. FewestOptionsFirstSquareSearchAlgorithm
5. ParallelSudoku
6. (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 createAllOptions()

Code To Implement

Puzzle

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 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 Optional<Integer> 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 empty.

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: Optional<Square> selectNextUnfilledSquare(ImmutableSudokuPuzzle puzzle) (sequential implementation only)

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.

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

method: Optional<Square> selectNextUnfilledSquare(ImmutableSudokuPuzzle puzzle) (sequential implementation only)

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 n-queens 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. However:

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:	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

• Make sure your solver uses the generic SquareSearchAlgorithm so that it works with both versions of the search ordering.
• 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

Propogate

class:	FxSudokuPropagateApp.java	VIZ
package:	sudoku.viz.propogate
source folder:	student/src//java

Solve

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

Correctness

Warm Up

class:	SequentialNQueensWarmUpTestSuite.java
package:	nqueens.warmup
source folder:	testing/src/test/java

Lab

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.

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

NQueens

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

ImmutableQueenLocations

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

FirstAvailableRowSearchAlgorithm

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

ParallelNQueens

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

Sudoku

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

Extra Credit 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 (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.