N-Queens/Sudoku Assignment

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.

In a similar vein, the sudoku problem has to do with solving a sudoku puzzle using a coded algorithm. A sudoku puzzle is composed of nine large squares that each contain nine smaller squares. Each of the nine smaller squares represents a number from 1 to 9 and there cannot be any duplicate numbers in a given big square. However, once a number is used in one small square, that number cannot appear again horizontally or vertically across the entire puzzle. Thus, for sudoku, we must figure out how to fill in all 81 squares while meeting these requirements.

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

Refer to these articles regarding the n-queens puzzle and sudoku for more information.

Where to Start

You can find all of the relevant files for this assignment under the backtrack directory. From there, all of the classes you will need to implement can be found under nqueens.assignment or sudoku.assignment. The core directories are utility and building block classes we created for you and the viz directories are visualization apps that might help you understand your code from a visual standpoint. Take a look at these classes to get a better understanding of how to use them for your assignment.

N-Queens

There are three classes you will need to modify: StudentImmutableQueenLocations.java, StudentSequentialNQueensCounter.java, and StudentParallelNQueensCounter.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 QueenLocations 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 NQueensUtils. 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 class.
• 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 QueenLocations. 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, remember to place the async in an appropriate location. As the method is recursive, you do not want to wrap the async in a finish tightly. Rather, you want to wrap each call to the recursive method in a finish. In other words, the finish should go in the countSolutions 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

There are three classes you will need to modify: StudentImmutableSudokuPuzzle.java, SquareSearchAlgorithms.java, and StudentSudokuSolver.java (we would recommend moving through these classes in this order). 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 the SudokuPuzzle is immutable, you will need to create a new instance of the object whenever you move on from one square to the next. This is where createNext comes in, along with the private constructor of this class.
• The getOptions method in SudokuPuzzle should find what value the given square could represent by searching the value of its peers (same row, same column, and same larger square). Starting with ALL_OPTIONS, the number of options should be removed depending on the peer. If the square is already filled in, it should simply return the correct value.
• The getValue method is already done for you, but it might come in useful for a later portion of the assignment.
• Your solvers should be able to handle two different approaches to solving the puzzle: row major and fewest options first. Row major just means brute forcing your way through the puzzle row by row, while fewest options first means solving the puzzle in the order of which squares has the fewest options.
  • The row major approach is already done for you
  • 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 asyncs and finishes.
• In your solveKernel method, you should use your desired 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.