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.

Further, by employing constraint propagation and search we can dramatically improve performance for problems like Sudoku.

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 using a similar algorithm to solve a Sudoku puzzle. 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. For more explanation, take a look at Peter Norvig's essay about solving Sudoku.

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

Code To Implement

N-Queens

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

Investigate out 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)

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

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

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

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

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)

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

Tips

N-Queens

There are three classes you will need to modify: DefaultImmutableQueenLocations.java, SequentialNQueens.java, and ParallelNQueens.java. Start with QueenLocations and then we recommend moving on to the sequential solution before the parallel one. Take a look at the javadocs to see what everything does and what you will need to implement.

A couple of notes and common issues:

• 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

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.

We then add constraint propagation and search ordering to make this problem more compelling.

Background

Peter Norvig's Essay

Code To Implement

Feel free to tackle this problem however you choose. We have pushed the #Constraint Propagator to the end since it might be the most challenging. It is also quite interesting, so do not feel forced to wait until the end if you prefer.

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)

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

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

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

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

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

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)

Constraint Propagator

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).

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

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

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

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

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

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

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)