CS 143 EXTRA CREDIT Assignment 4 (50 points + 10 points extra credit)

Recursive Backtracking for Unruly

See Canvas for the due date!

Consider the Unruly game demonstrated in class and found online at https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/unruly.html. A grid is presented with some squares filled in black and some filled in white, and some are unfilled (gray). Fill in the gray squares as black or white so that every row and every column has the same number of black and white squares, and there are never three or more squares of the same color next to each other in a row or column.

We use a 2D array of integers for our grid and represent the two different filled in colors as the two different integer values 1 and 2, and unfilled squares as 0.

To aid with your recursive backtracking algorithm, write the checkOK method which returns true if no immediate rule violation is found, or false if there is one. (An immediate rule violation would be 3 consecutive 1s or 2s in a row or column, or a row or column containing more than half of 1s or 2s.) The checkOK method should probably just consist of a series of for loops in your array, not any recursion.

The checkOK method must not modify the grid.

public static boolean checkOK(int[][] grid)

Once you finish checkOK, implement the following method in the Unruly class:

public static boolean solve(int[][] grid)

Your code can assume that the array is full of 0, 1, and 2 values and is a square of even width and height. Your method should leave all the existing 1 and 2 values and try to fill in all the 0s with 1 and 2 values so that every row and column has an equal number of 1 and 2 values and there is no run of three or more 1 or 2 values in a row or column. If there is such a solution, you should leave the grid filled in with a solution of all 1 and 2 values according to the rules and return the value true. If there is no solution, solve should return false. (HINT: Your code will probably restore the grid to the original state in that case.) If you wish, you may also use helper methods in your code.

Make sure you follow and understand the “Recursive Backtracking General Strategy” from the Recursive Backtracking module. For each recursive call, a “move” should correspond to filling in a 0 with a 1 or 2.

You can have your solve method make a tentative move, check if it’s ok with the checkOK method, and if not immediately undo the move and try something else. Remember, any grid location can only contain two possible values – if neither one is OK, the move must not be possible! If you do this, your code should be fast enough for all the given examples. For each problem, your solve method will be given a time limit of 1 minute, but the solve method should run instantly on a modern computer if your code is bug free. For this assignment, your code shouldn’t search for the “best” next move to make with any kind of heuristic; this is more likely to lead to bugs in your code. Keep it simple! You should probably use loops to look for places to move – it does not need to be “purely recursive” like RecursionIntro required. Your solve method must take less than 30 seconds on each example; a simple version takes under a tenth of a second in the worst case among all the examples.

You may also want to read the article linked from our Recursive Backtracking module entitled “Recursive Backtracking Tutorial (N Queens)” as well as viewing the “Recursive Backtracking Visualization (1 through 8 Queens)”. This problem has a lot in common with the “n Queens” problem!

Page 1 of 1