0% found this document useful (0 votes)

140 views50 pages

Backtracking: CENG 707 Data Structures and Algorithms

Backtracking is a general algorithm for solving problems recursively by trying to build a solution incrementally, abandoning each partial solution ("backtracking") as soon as it is determined that the solution cannot possibly be completed from that state. It involves systematically trying all possible candidates to find a solution. The algorithm uses a stack to keep track of partial solutions to the problem and allows efficiently backtracking by abandoning partial solutions that cannot possibly be completed.

Uploaded by

Anders S. Voyan

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

140 views50 pages

Backtracking: CENG 707 Data Structures and Algorithms

Uploaded by

Anders S. Voyan

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 50

Backtracking

CENG 707
Data Structures and Algorithms
Yusuf Sahillioğlu

1
Backtracking
• Stacks and trees can be utilized to solve problems such as
crosswords, Sudoku, 8-queens puzzle, and many other puzzles

2
Backtracking
• Stacks and trees can be utilized to solve problems such as
crosswords, Sudoku, 8-queens puzzle, and many other puzzles
• You are faced w/ a set of options, one of which must be chosen
• After you make the choice, you get a new set accordingly
• Repeat until you reach a final state
– If your choices were good, your final state is a goal state
– Else, it is not a goal state

3
Backtracking
• Stacks and trees can be utilized to solve problems such as
crosswords, Sudoku, 8-queens puzzle, and many other puzzles
• In other words,
• Each choice (tree children) is recorded (in a stack)
• When you run out of choices for the current decision, you
pop the stack, and continue trying different choices for the
previous decision

4
Backtracking
• Conceptually you start at the root of a tree
• Tree has some good some bad leaves (all may be good/bad)
• You want to get to a good leaf
• At each node, beginning w/ root, you choose one of its children
to move to, and repeat ‘till you get to a leaf
• Suppose you get to a bad leaf
– Do backtrack to continue the search for a good leaf by
canceling your most recent choice (pop stack) and trying out
the next option in that set of options
• Recursion or stack
– If you end up at the root w/ no options left, no good leaf 

5
Backtracking
• Starting at Root, your options are A and B. You choose A.
• At A, your options are C and D. You choose C.
• C is bad. Go back to A.
• At A, you have already tried C, and it failed. Try D.
• D is bad. Go back to A.
• At A, you have no options left to try. Go back to Root.
• At Root, you have already tried A. Try B.
• At B, your options are E and F. Try E.
• E is good. Congratulations!

6
Backtracking
• Generic backtracking algorithm w/ recursion

boolean solve(Node n) {
if n is a leaf node {
if the leaf is a goal node, return true
else return false
} else {
for each child c of n
if solve(c) succeeds, return true

return false
}
}

7
Backtracking
• Generic backtracking algorithm w/o recursion (w/ stacks)

boolean solve(Node n) {
push node n on the stack S;
while S is not empty {
if S.top() node is a leaf {
if it is a goal node, return true
else pop it off S
}
else if S.top() node is unmarked {
Mark S.top() node
for each child c of S.top() node
push c to S
}
else //not a leaf and marked (we are backing out)
pop it off S
}
return false
}
8
Backtracking
• Example puzzle: Balls on the move

• n black balls, n white balls, 2n+1 spaces, middle empty

• Represent the board as an array for the coding: 1,1,-1,2,2 (left)
• Blacks/whites can only move to right/left, no backing up
• A ball can
– move 1 space ahead, if clear
– Jump over 1 opposite-color ball, if clear

9
Backtracking
• Example puzzle: Balls on the move

• A stuck/bad leaf

10
Backtracking
• Example puzzle: Balls on the move

• Each move will yield new boards, which become the children of
the current board
• After some observation on ball movements
– bool canMove(int[] board, int idx)
• If idx is empty, no move possible (return false)
• If idx contains a black ball, check for a valid move to go right
• If idx contains a white ball, check for a valid move to go left

11
Backtracking
• Example puzzle: Balls on the move

• Each move will yield new boards, which become the children of
the current board
• After some observation on ball movements
– int[] makeMove(int[] oldBoard, int idx)
• Make a move from idx on oldBoard and return the new board

12
Backtracking
• Example puzzle: Balls on the move

• Resulting recursive code

boolean solvable(int[] board) {
if (puzzleSolved(board)) {
return true;
}
for (int position = 0; position < BOARD_SIZE; position++) {
if (canMove(board, position)) {
int[] newBoard = makeMove(board, position);
if (solvable(newBoard)) {
printBoard(newBoard);
return true;
}
}
}
return false;} 13
Backtracking
• Example puzzle: Balls on the move

• Output of the recursive code (notice the reverse order)

14
Backtracking
• Example puzzle: Balls on the move

• Resulting non-recursive code

boolean solvable(int[] board) {

//This is part of your homework # 2; see the next slides for help

15
Backtracking
• Let’s see the execution trace along with the Stack

boolean solve(Node n) {
push node n on the stack S;
while S is not empty {
if S.top() node is a leaf {
if it is a goal node, return true
else pop it off S
}
else if S.top() node is unmarked {
Mark S.top() node
for each child c of S.top() node
push c to S
}
else //not a leaf and marked (we are backing out)
pop it off S
} 16
return false }
Backtracking
• Let’s see the execution trace along with the Stack

boolean solve(Node n) {
push node n on the stack S;
while S is not empty {
if S.top() node is a leaf {
if it is a goal node, return true
else pop it off S
}
else if S.top() node is unmarked {
Mark S.top() node
for each child c of S.top() node
push c to S
}
else //not a leaf and marked (we are backing out)
pop it off S
} 17
return false }
Backtracking
• Let’s see the execution trace along with the Stack

boolean solve(Node n) {
push node n on the stack S;
while S is not empty {
if S.top() node is a leaf {
if it is a goal node, return true
else pop it off S
}
else if S.top() node is unmarked {
Mark S.top() node
for each child c of S.top() node
push c to S
}
else //not a leaf and marked (we are backing out)
pop it off S
} 18
return false }
Backtracking
• Let’s see the execution trace along with the Stack

boolean solve(Node n) {
push node n on the stack S;
while S is not empty {
if S.top() node is a leaf {
if it is a goal node, return true
else pop it off S
}
else if S.top() node is unmarked {
Mark S.top() node
for each child c of S.top() node
push c to S
}
else //not a leaf and marked (we are backing out)
pop it off S
} 19
return false }
Backtracking
• Let’s see the execution trace along with the Stack

boolean solve(Node n) {
push node n on the stack S;
while S is not empty {
if S.top() node is a leaf {
if it is a goal node, return true
else pop it off S
}
else if S.top() node is unmarked {
Mark S.top() node
for each child c of S.top() node
push c to S
}
else //not a leaf and marked (we are backing out)
pop it off S
} 20
return false }
Backtracking
• Let’s see the execution trace along with the Stack

boolean solve(Node n) {
push node n on the stack S;
while S is not empty {
if S.top() node is a leaf {
if it is a goal node, return true
else pop it off S
}
else if S.top() node is unmarked {
Mark S.top() node
for each child c of S.top() node
push c to S
}
else //not a leaf and marked (we are backing out)
pop it off S
} 21
return false }
Backtracking
• Let’s see the execution trace along with the Stack

boolean solve(Node n) {
push node n on the stack S;
while S is not empty {
if S.top() node is a leaf {
if it is a goal node, return true
else pop it off S
}
else if S.top() node is unmarked {
Mark S.top() node
for each child c of S.top() node
push c to S
}
else //not a leaf and marked (we are backing out)
pop it off S
} 22
return false }
Backtracking
• Let’s see the execution trace along with the Stack

boolean solve(Node n) {
push node n on the stack S;
while S is not empty {
if S.top() node is a leaf {
if it is a goal node, return true
else pop it off S
}
else if S.top() node is unmarked {
Mark S.top() node
for each child c of S.top() node
push c to S
}
else //not a leaf and marked (we are backing out)
pop it off S
} 23
return false }
Backtracking
• Let’s see the execution trace along with the Stack

boolean solve(Node n) {
push node n on the stack S;
while S is not empty {
if S.top() node is a leaf {
if it is a goal node, return true
else pop it off S
}
else if S.top() node is unmarked {
Mark S.top() node
for each child c of S.top() node
push c to S
}
else //not a leaf and marked (we are backing out)
pop it off S
} 24
return false }
Backtracking
• Let’s see the execution trace along with the Stack

boolean solve(Node n) {
push node n on the stack S;
while S is not empty {
if S.top() node is a leaf {
if it is a goal node, return true
else pop it off S
}
else if S.top() node is unmarked {
Mark S.top() node
for each child c of S.top() node
push c to S
}
else //not a leaf and marked (we are backing out)
pop it off S
} 25
return false }
Backtracking
• Let’s see the execution trace along with the Stack

boolean solve(Node n) {
push node n on the stack S;
while S is not empty {
if S.top() node is a leaf {
if it is a goal node, return true
else pop it off S
}
else if S.top() node is unmarked {
Mark S.top() node
for each child c of S.top() node
push c to S
}
else //not a leaf and marked (we are backing out)
pop it off S
} 26
return false }
Backtracking
• Let’s see the execution trace along with the Stack

boolean solve(Node n) {
push node n on the stack S;
while S is not empty {
if S.top() node is a leaf {
if it is a goal node, return true
else pop it off S
}
• M is a good leaf ☺ else if S.top() node is unmarked {
Mark S.top() node
for each child c of S.top() node
push c to S
}
else //not a leaf and marked (we are backing out)
pop it off S
} 27
return false }
Backtracking
• Let’s see the execution trace along with the Stack

• Assume M was a bad leaf }

else //not a leaf and marked (we are backing out)
pop it off S

– backtrace ‘till G (most recent unmarked node)

}
return false }

– G pushes O and N, which later push P and R

28
Backtracking
• N-queen problem: safely place N queens on an NxN chessboard
• Safe: no 2 queens on the same row, same column, same diagonal
• N=8 case for the ordinary chessboard:

29
Backtracking
bool isSafe(int i, int j)
//return True if Q can be placed at row i, col j
//x[i] global array w/ first i-1 entries set already: x[a]=b
//means that for row a, Q is safely sitting at col b

for k = 1 to i-1 //check rows

if (x[k] == j OR //same column
|k-i| == |x[k]-j| //same diagonal (deltaX=deltaY, slope=1)
return False
return True
(i,j)

(k,l)

Same diagonal
since |i-k|=|j-l|

30
Backtracking
void NQueens(int i, int n) //initial call’ll be NQueens(1, N)

for j = 1 to n //check columns

if (isSafe(i, j))
x[i] = j
if (i == n)
printResult(x); //done!
else
NQueens(i+1, n)
i=1

: remaining j’s
for this i

31
Backtracking
void NQueens(int i, int n) //initial call’ll be NQueens(1, N)

for j = 1 to n //check columns

if (isSafe(i, j))
x[i] = j
if (i == n)
printResult(x); //done!
else
NQueens(i+1, n)
i=1 i=2

: remaining j’s
for this i

32
Backtracking
void NQueens(int i, int n) //initial call’ll be NQueens(1, N)

for j = 1 to n //check columns

if (isSafe(i, j))
x[i] = j
if (i == n)
printResult(x); //done!
else
NQueens(i+1, n)
i=1 i=2 i=3

: remaining j’s no safe column

for this i

33
Backtracking
void NQueens(int i, int n) //initial call’ll be NQueens(1, N)

for j = 1 to n //check columns

if (isSafe(i, j))
x[i] = j
if (i == n)
printResult(x); //done!
else
NQueens(i+1, n)
i=1 i=2 i=3 i=2