CSE220 Spring 2015 – Homework 4
Due Thursday 12/3/2015 @ 11:59pm
In this assignment you willimplement severalrecursive functions in MIPS. In each case, the high-levelsourcecodeisprovided.YouMUST implementallthefunctionsintheassignment using the defined algorithms. Do not use other algorithms.
Don’t get wrapped up in WHY these functions and algorithms work. This is not a requirement of this assignment, which is why pseudo code is given to you. Your goal is to implement the algorithm correctly in MIPS assembly to produce the correct results.
As always, you must follow MIPS register and calling conventions. DO NOT submit a file with the functions main or _start defined.
You are strongly encouraged to start EARLY!! Bugs in recursive functions can be very difficult to identify. You will should use the MARS debugger and test parts of your functions independently for correct operation prior to continuing on.
Getting Started
Download the hw4.asm template from Piazza.
Allfunctionalityforyourassignment shouldbe in hw4.asm
At the top of hw4.asm in the comments put your name and id.
# Homework #4
# name: MY_NAME
# sbuid: MY_SBU_ID
Part 1 – Hofstadter Female and Male
Sequences
Implement the Hofstadter Male and Female functions. The Hofstadter Female (F) and Male (M)sequences are definedas follows:
/**
- * Computes the Nth number of the Hofstadter Female
- * sequence. *
- * @param n The number of the F sequence to compute
- * @return The Nth number of the F sequence */
public int F(int n) {System.out.println(“F: ” + n); if (n == 0)
return 1; else
return n – M(F(n-1));
}
/**
- * Computes the Nth number of the Hofstadter Male
- * sequence. *
- * @param n The number of the M sequence to compute
- * @return The Nth number of the M sequence */
public int M(int n) {System.out.println(“M: ” + n); if (n == 0)
return 0; else
return n – F(M(n-1));
}
The first few terms of these sequences are
F: 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, … (more terms here)
M: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, … (more terms here)
Note that when testing these f unctions, their run times will slow considerably as the input grows.
For example, the Hofstadter Mfunction: M(50)takes ~0.38 seconds to execute M(100) takes ~0.89 seconds to execute M(150) takes ~12.5 seconds to execute M(300) takes ~37 minutes to execute
Part 2 – Tak Function
Implement the Tak function. The Tak function is defined as follows:
/**
* Implementation of the Tak function */
public int tak(int x, int y, int z) {
}
if (y >= x) return z;
else
return tak(tak(x-1, y, z),
tak(y-1, z, x), tak(z-1, x, y));
AswiththefunctionsinPartI,runtimeswillslowconsiderablywiththesizeof x, y,andz.Functiontak willmakeahugenumberof recursivecalls.Usesmall numbers!!!!
Part 3 – Sudoku
Forthispartof theassignment,youwillimplementasolverforthegameSudoku.Forthose
unfamiliar with this game, the rules can be found here .
The method employs a technique known as Backtracking to solve the puzzle. Backtracking is a general algorithm that incrementally builds candidates for each cell to build the solutions. It abandons each partial candidate c (“backtracks”) as soon as it determines that c cannot possibly be completed to a valid solution.
Solver algorithm
The solver starts in the top-left corner of the board (see figure in next section, board[0] [0] ) and progresses row by row until it reached the bottom-right corner ( board[8][8] ). If the algorithm reaches the bottom-right corner ( board[8][8] ) of the board, a solution has been found.
if (current cell in the grid is filled) continuing solving via recursive call;
else /* the cell is blank*/
create list of all possible candidates for that cell. for each candidate in list
place the candidate value in the cell; continuing solving via recursive call; if (no candidates remaining)
“backtrack” by setting cell to blank & return;
If the candidate chosen at any point was incorrect, a situation will arise where there are no
candidates for a given cell. At this point, the solver willbegin to “backtrack” (the recursion stack will being to unwind). Eventually, it will backtrack to the point where the incorrect candidate was chosen. It willselect the next candidate from the candidate list, andbegin solving again.
When the solver reaches the bottom-right ( board[8][8] ) corner of the board, a solution was found. we will print the solutions and “backtrack” through all recursive calls.
Implementation details
The Sudoku board will be represented as a 2D array of bytes in memory with 9 rows and 9 columns. The board will be declared in the main program which calls your function(s).
Board layout, terminology legend, and example sudoku puzzle
A blank cell will be represented by the number 0.
You can assume that all Sudoku puzzles are well-f ormed. That is, there exists one and only one solution for a given board.
Note:Allof the remaining functions inthis document willuse “Java-like” pseudo code.
Your main programwhich tests the sudoku function MUST make the init ial call as sudoku(board, 0, -1)
/*
- * Solves a given Sudoku board. *
- * Call initially with sudoku(board, 0, -1) *
- * A BLANK cell in the board is defined to be 0.
- * FINISHED is a global flag variable, defined in hw4.asm.
- * All initial filled cell values for the puzzle are set in
- * the board *
- * @param board Address of the board in memory
- * @param x Starting row
- * @param y Starting column
*/
public void sudoku(byte[][] board, int x, int y) {System.out.println(“Sudoku [” + x + “][” + y + “]”); // If we have found a solution
if (isSolution(x, y)) {// Print the board
printSolution(board);
// global boolean variable
FINISHED = True;
}
else {// Go to the next column in the row
y = y + 1;
// If we go past the last column if (y > 8) {
}
// Then go to first column of the next row
x = x + 1; y = 0;
// If the current square isn’t blank
if (board[x][y] != BLANK) {
// Then keep on solving, recursive call sudoku(board, x, y);
}
} }
// Otherwise..
else {
// Construct a set of all possible choices for the
current position
byte candidates[];
int candidateLength = constructCandidates(board, x, y, candidates);
} }
// Try each candidate in this list
for (int c=0; c < candidateLength; c++) {
// Place the candidate
board[x][y] = candidates[c];
// Attempt to solve the board using this candidate sudoku(board, x, y);
// If we reach this point, must undo the changes // made to the board – “backtrack”
board[x][y] = BLANK;
// If a solution was found, return
if (FINISHED) return
Variable byte candidates[] is a local variable to each call of Sudoku. Local variables are declared on the stack in the activation record of each call. You must implement an activation record in sudoku which uses the f ollowing f ormat. The local variable
candidateLength will also need to be used af ter returning f rom recursive calls, and thereforewillbestoredonthestack.Thebaseaddressof array candidates isthe memory address of the stack for candidates[0] (the $fp ). The address of
candidateLength must be calculated based of f of the position of the $fp , as will the arrayelementsof candidate.ThefunctionconstructCandidateswillsavethevalues into the activation record of the calling sudoku function.
NOTE: You must use this organization for the activation record. The grading script will check!
Helper functions
The isSolution method determines whether a given Sudoku board is a complete solution. A board is a complete solution when the entire board is filled. So, when the bottom-right corner ( board [8][8] ) is reached and filled, a valid solution was discovered.
/*
- * Determines whether the Sudoku board is a complete solution. *
- * @param row The current row in the board
- * @param col The current column in the board
- * @return True (1) if the Sudoku board is solved, False (0)
- * otherwise
*/
public boolean isSolution(int row, int col) {
}
if (row == 8 && col == 8) return True;
return False;
When a solution to the puzzle is found, printSolution is called. In this case, printSolution simply prints out the completed board.
/*
- * Prints the solved Sudoku puzzle. *
- * @param board Address of the board in memory */
public void printSolution(byte[][] board) {System.out.println(“Solution: “); for (int i = 0; i < 9; i++) {
} }
for (int j = 0; j < 9; j++) { System.out.println(board[i][j] + ” “);
} System.out.println();
The constructCandidates function examines each row and column and 3×3 grid square around the current cell position f or all determined cell values. If a value is not in use by any of these, then the value is added to the possible candidate values for the current cell. Array variables rSet , cSet and gSet are defined as global variables in the data section of hw4. asm. The same memory locations can be used by each constructCandidates
f unction call. While these are local variables, which in reality would be allocated space on the stackwithintheactivationrecordof constructCandidates,wewillsimplifythe implementationanddefine globalvariables to holdthese arrays.
/*
- * Constructs a set of all legal candidates for a
- * particular cell in a Sudoku board. *
- * @param board Address of the board in memory
- * @param row The row of the current cell in the board
- * @param col The column of the current cell in the board
- * @param candidates Address of array for all legal candidates
- * for the specified cell
- * @return The number of elements in the array
*/
public int constructCandidates(byte[][] board, int row, int col, byte[] candidates) {int count = 0; // # of elements in the candidate array
byte rLength = rowSet(board, row);
byte cLength = colSet(board, col);
byte gLength = gridSet(board, row, col);
}
// Check if each potential candidate exists
// in current row, col, or grid
// If it isn’t, add it to the list of candidates. for (int i = 1; i <= 9; i++) {
//Use rLength, cLength, and gLength here
if i in rSet: // if number exists in current row,
continue; // go to next loop iteration
if i in cSet: // if number exists in current col,
continue; // go to next loop iteration
if i in gSet: // if number exists in current 3×3,
continue; // go to next loop iteration
candidates[count] = i; // add to candidate list count++; // update count
}
return count;
The constructCandidates method will make use of three helper methods. The rowSet methodwillreturnallnumbersinagivenrow, colSet returnsallnumbersinagiven column, and gridSet returns the numbers in a given 3×3 grid. They are defined as follows:
/*
- * Returns all numbers in a given row of the Sudoku board. *
- * @param board Address of the board in memory
- * @param row The row of the given cell
- * @return The number of elements in the rSet array */
public int rowSet(byte[] board, int row) {int count = 0;
for (i = 0; i < 9; i++) {if (board[row][i] != BLANK) { rSet[count] = board[row][i]; count++;
} }
return count;
}
/*
* Returns all numbers in a given column of the Sudoku board. *
* @param board Address of the board in memory
* @param col The column number of the given cell * @return The number of elements in the cSet array */
public int colSet(byte[] board, int col) {
int count = 0;
for (int i = 0; i < 9; i++) {
if (board[i][col] != BLANK) { cSet[count] = board[i][col]; count++;
} }
return count;
}
/*
* Returns all numbers in a particular 3×3 grid of the Sudoku board.
*
- * @param board The address of the Sudoku board
- * @param row The row number of the given cell
- * @param col The column number of the given cell
- * @return The number of elements in the array
*/
public int gridSet(byte[] board, int row, int col) {
}
int r_start = row / 3 * 3; //Grids start at rows 0,3,6 int c_start = col / 3 * 3; //Grids start at cols 0,3,6 int count = 0;
for (int i = r_start; i < r_start + 3; i++) {
for (int j = c_start; j < c_start + 3; j++) { if (board[i][j] != BLANK) {
gSet[count] = board[i][j]; count++;
} }
}
return count;
We strongly suggest you test each of the helper functions independently for correct operation prior to implementing sudoku. Detecting errors in each function operation is much easier than during recursion.
Grading willbeperformedoneachfunctionindependentlyandwithsudoku.
Hand-in instructions
See Sparky Submission Instructions on piazza for hand-in instructions.
When writing your program try to comment as much as possible. Try to stay consistent with your formatting. It is much easier for your TA and the professor to help you if we can figure out what your code does quickly.