Transcript Backtracking Examples - Magic Number Square

Announcements
Backtracking
Magic Number Square
Tentaizu Approach
Magic Number Squares

A 3x3 magic number square has 9
numbers {1,2,… 9} that must be arranged
in such a way that every row, column, and
diagonal has the same sum.
◦ For a 3x3 magic number square the sum is
3*(3*3+1)/2 = 15.
15
15
Magic Number Square

It is possible to have different sized magic
number squares of size nxn,
◦ where numbers {1,2,… n*n} must be
arranged in such a way that every row and
column has the same sum.
◦ For a nxn magic number square the sum is
n*(n*n+1)/2
Magic Number Square

Say we want to create a class MagicSquare
that takes in an int n and returns all valid
Magic Number Squares of size nxn.
◦ Example, n = 3 returns 8 magic squares:
2 7 6
9 5 1
4 3 8
4 9 2
3 5 7
8 1 6
2 9 4
7 5 3
6 1 8
6 1 8
7 5 3
2 9 4
4 3 8
9 5 1
2 7 6
6 7 2
1 5 9
8 3 4
8 1 6
3 5 7
4 9 2
8 3 4
1 5 9
6 7 2
Magic Number Square

How would we start?
◦ The plan like we did with Eight Queens is just to
try a number in the first position.
 Then we can recursively solve the board at the next
position given that the number has been placed.
 Then we systematically “throw out” boards that do not
meet our constraints.
◦ What do we need to do that?
 First we will want an empty board that we will fill in one
square at a time.
 Then we will want to mark which numbers in the set (1,
… , n*n) have already been used.
 We need to calculate the sum that each row, column, and
diagonal must add up to.
public class MagicSquare {
private int[][] square;
private boolean[] possible;
private int totalSqs;
private int sum;
private int numsquares;
• square[][] will hold the numbers we place.
• possible[] will hold the numbers that have still not bee used
yet.
• sum will store what value the rows/columns/diagonals must
sum to.
// Creates an empty MagicSquare object.
public MagicSquare(int n) {
// Fill in an empty square; 0 represents unfilled.
square = new int[n][n];
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
square[i][j] = 0;
// Start with all numbers being possible.
totalSqs = n*n;
possible = new boolean[totalSqs];
for (int i=0; i<totalSqs; i++)
possible[i] = true;
sum = n*(n*n+1)/2;
numsquares = 0;
}
square[][] is size nxn
initialize all values to 0, it’s empty to
start!
There are n*n total numbers,
so possible[] is size n*n. At first
all of the numbers can be used
so the entire array is set to true.
// Recursive method which fills in the square at (row,col).
// Try each possible number for this square.
public void fill(int row, int col) {
for (int i=0; i<totalSqs; i++) {
// Screen away incorrect squares.
if (possible[i]) {
all possible
values for this spot
if (!checkRows() || Try
!checkCols()
|| !checkDiags())
square[row][col] = i+1;
possible[i] = false;
return;
// Filled everything, so print !!
// Go to the next square.
Find {the new row and col,
if (row == square.length)
int newcol = col+1;
so we can recursively fill the next spot.
System.out.println(this);
numsquares++;
int newrow = row;
if (newcol == square.length) {
newrow++;
return;
newcol = 0;
}
}
Base Cases:
Either we broke the
constraints,
Recursively
call fill() on our new spot.
so we throw that board out.
OR
We’re DONE!!
Undo this square for future recursive calls,
so that we can try ALL valid boards
}
}
// Recursively fill.
fill(newrow, newcol);
// Undo this square.
square[row][col] = 0;
possible[i] = true;
// Recursive method which fills in the square at (row,col).
// Try each possible number for this square.
public void fill(int row, int col) {
for (int i=0; i<totalSqs; i++) {
// Screen away incorrect squares.
if (possible[i]) {
square[row][col] = i+1;
if (!checkRows() || !checkCols() || !checkDiags())
possible[i] = false;
return;
// Go to the next square.
// Filled everything, so print !!
int newcol = col+1;
if (row == square.length) {
int newrow = row;
System.out.println(this);
if (newcol == square.length) {
numsquares++;
newrow++;
return;
newcol = 0;
}
}
// Recursively fill.
fill(newrow, newcol);
// Undo this square.
square[row][col] = 0;
possible[i] = true;
}
}
// Returns true iff all the rows are okay.
public boolean checkRows() {
// Try each row.
for (int i=0; i<square.length; i++) {
int test = 0;
boolean unFilled = false;
Determine whether each row is filled and
the row’s sum.
// Add up the values in this row.
for (int j=0; j<square[i].length; j++) {
test += square[i][j];
if (square[i][j] == 0)
unFilled = true;
}
// If the row is filled and adds up to the wrong number,
// this is an invalid square.
If the row is filled and adds
if (!unFilled && test != sum)
up to the wrong number
return false;
then our row constraint is violated,
}
// Never found proof of an invalid row.
return true;
}
and we return false.
At this point we have checked all rows,
and none of them violated our constraint.
Magic Number Square Decision
Tree

Shown on the board…
Tentaizu Approach

The game is played on a 7x7 board. Exactly 10 of the 49
squares are each hiding a star. Your task is to determine
which squares are hiding the stars.
 Other squares in the board provide clues: A number in a
square indicates how many stars lie next to the square

No square with a number in it contains a star, but a star may
appear in a square with no adjacent numbers.
Tentaizu Approach

Break down the problem into smaller steps
1. Read in the board
• Determine the squares with numbers
• Determine the squares that are blank
2. Place the stars in a backtracking method
based on the possible locations
3. Check that the current or finished board
meets the requirements of the game
• Ten stars are present
• Each numbered square has the
correct number of adjacent stars
Optional Homework Problem

Get together with someone in the class and
brainstorm how you will solve the Tentaizu
assignment.

Turn in a paper describing your strategy.
◦ What matrices and/or arrays will you need?
◦ What constraints will you check against?
 How will you know when these constraints are violated?
◦ How will you know when the board is complete?

Show a decision tree diagramming how your
Tentaizu algorithm will work. (Like how we did
with the Magic Number Square)
References
Slides adapted from Arup Guha’s Computer
Science II Lecture notes:
http://www.cs.ucf.edu/~dmarino/ucf/cop3503/le
ctures/
 Additional material from the textbook:

Data Structures and Algorithm Analysis in Java (Second
Edition) by Mark Allen Weiss

Additional images:
www.wikipedia.com
xkcd.com