Transcript Boggle Game

Boggle Game:
Backtracking Algorithm Implementation
CS 1501
Boggle Game
• Read the assignment requirement carefully.
http://www.cs.pitt.edu/~kirk/cs1501/Ramirez/Summer2009/assigs/boggle/assig1a.html
2016/9/12
2/16
Boggle Game
• Read the assignment requirement carefully.
http://www.cs.pitt.edu/~kirk/cs1501/Ramirez/Summer2009/assigs/boggle/assig1a.html
• The boggle game is to form as many 3+ letter words as
possible from a 2-dimensional board of letters.
– We want to form words by starting at any letter and traversing over
adjacent cubes vertically, horizontally or diagonally.
– Any cube may appear at most once in a word.
– Only real words (from dictionary) are valid.
– Words must be at least 3 letters long to be valid.
2016/9/12
F
R
O
O
Y
I
E
S
L
D
N
T
A
E
R
E
3/16
Boggle Game
• Read the assignment requirement carefully.
http://www.cs.pitt.edu/~kirk/cs1501/Ramirez/Summer2009/assigs/boggle/assig1a.html
• The boggle game is to form as many 3+ letter words as
possible from a 2-dimensional board of letters.
– We want to form words by starting at any letter and traversing over
adjacent cubes vertically, horizontally or diagonally.
– Any cube may appear at most once in a word.
– Only real words (from dictionary) are valid.
– Words must be at least 3 letters long to be valid.
2016/9/12
F
R
O
O
Y
I
E
S
L
D
N
T
A
E
R
E
FRIEND
4/16
Boggle Game
• Read the assignment requirement carefully.
http://www.cs.pitt.edu/~kirk/cs1501/Ramirez/Summer2009/assigs/boggle/assig1a.html
• The boggle game is to form as many 3+ letter words as
possible from a 2-dimensional board of letters.
– We want to form words by starting at any letter and traversing over
adjacent cubes vertically, horizontally or diagonally.
– Any cube may appear at most once in a word.
– Only real words (from dictionary) are valid.
– Words must be at least 3 letters long to be valid.
2016/9/12
F
R
O
O
Y
I
E
S
L
D
N
T
A
E
R
E
ROSTER
5/16
Boggle Game
• Read the assignment requirement carefully.
http://www.cs.pitt.edu/~kirk/cs1501/Ramirez/Summer2009/assigs/boggle/assig1a.html
• The boggle game is to form as many 3+ letter words as
possible from a 2-dimensional board of letters.
– We want to form words by starting at any letter and traversing over
adjacent cubes vertically, horizontally or diagonally.
– Any cube may appear at most once in a word.
– Only real words (from dictionary) are valid.
– Words must be at least 3 letters long to be valid.
2016/9/12
F
R
O
O
Y
I
E
S
L
D
N
T
A
E
R
E
END
FINE
REAL
6/16
Boggle Game
• Read the assignment requirement carefully.
http://www.cs.pitt.edu/~kirk/cs1501/Ramirez/Summer2009/assigs/boggle/assig1a.html
• The boggle game is to form as many 3+ letter words as
possible from a 2-dimensional board of letters.
– We want to form words by starting at any letter and traversing over
adjacent cubes vertically, horizontally or diagonally.
– Any cube may appear at most once in a word.
– Only real words (from dictionary) are valid.
– Words must be at least 3 letters long to be valid.
2016/9/12
F
R
O
O
Y
I
E
S
L
D
N
T
A
E
R
E
XDEAD
XFYLDERE
7/16
Boggle Game
• Wild card *
– A * can represent any letter in the alphabet.
– Wild card essentially causes more word possibilities in a given board.
2016/9/12
F
R
O
O
F
R
O
O
F
R
O
O
Y
I
E
S
Y
I
E
S
Y
I
E
S
L
*
N
T
L
A
N
T
L
B
N
T
A
E
R
E
A
E
R
E
A
E
R
E
F
R
O
O
F
R
O
O
Y
I
E
S
Y
I
E
S
L
D
N
T
L
Z
N
T
A
E
R
E
A
E
R
E
……
8/16
Requirement
• Read board from text file.
• Calculate all possible words (of length at least 3).
• Allow the user to type words from the keyboard and tell him
if each word is “valid” or not.
• Show the user all of the words for the board by printing out
all of the words in the board word list in alphabetical order.
2016/9/12
9/16
Board Search
• Start from any cube on the board
F
R
O
O
Y
I
E
S
L
D
N
T
A
E
R
E
– Track where we are (current position)
– Track where we were (history)
2016/9/12
10/16
Board Search
• Start from any cube on the board
j
F
R
O
O
(0,0)
(0,1)
(0,2)
(0,3)
Y
I
E
S
(1,0)
(1,1)
(1,2)
(1,3)
L
D
N
T
(2,0)
(2,1)
(2,2)
(2,3)
A
E
R
E
(3,0)
(3,1)
(3,2)
(3,3)
i
– Track where we are (current position)
• (i, j)
– Determine where we can go (next position)
• (i-1, j-1) (i-1, j) (i-1, j+1)
(i, j-1)
curr (i, j+1)
(i+1, j-1)(i+1, j)(i+1, j+1)
– Track where we were (history)
2016/9/12
11/16
Backtracking Example
• Start from any cube on the board
j
F
R
O
O
(0,0)
(0,1)
(0,2)
(0,3)
Y
I
E
S
(1,0)
(1,1)
(1,2)
(1,3)
L
D
N
T
(2,0)
(2,1)
(2,2)
(2,3)
A
E
R
E
(3,0)
(3,1)
(3,2)
(3,3)
i
– Start from D
• At (2, 1)
• Next step can be: (1, 0) (1, 1) (1, 2) (2, 0) (2, 2) (3, 0) (3, 1) (3, 2)
• Try (1, 0) – DY
– Advance to (1, 0)
2016/9/12
12/16
Backtracking Example
• Start from any cube on the board
j
F
R
O
O
(0,0)
(0,1)
(0,2)
(0,3)
Y
I
E
S
(1,0)
(1,1)
(1,2)
(1,3)
L
D
N
T
(2,0)
(2,1)
(2,2)
(2,3)
A
E
R
E
(3,0)
(3,1)
(3,2)
(3,3)
i
– Now at Y (1, 0)-(2,1)
• At (1, 0)
• Next step can be: (0, 0) (0, 1) (1, 1) (2, 2) (2, 0)
– (2, 1) is not allowed!
• Try all possible steps and find no valid prefix or words
– Backtrack to D (2, 1)
2016/9/12
13/16
Backtracking Example
• Start from any cube on the board
j
F
R
O
O
(0,0)
(0,1)
(0,2)
(0,3)
Y
I
E
S
(1,0)
(1,1)
(1,2)
(1,3)
L
D
N
T
(2,0)
(2,1)
(2,2)
(2,3)
A
E
R
E
(3,0)
(3,1)
(3,2)
(3,3)
i
– Return to D
• At (2, 1)
• Next step can be: (1, 1) (1, 2) (2, 0) (2, 2) (3, 0) (3, 1) (3, 2)
– (1, 0) has failed.
• Try (1, 1) – DI
– Advance to (1, 1)
….
2016/9/12
14/16
New Step Situations
• When we try a new step on the board, the composition with
the new letter can have 4 possible situations:
– Not a prefix, not a word
• Give up, backtrack to the previous step (pruning)
– Not a prefix, is a word
• Save the word, backtrack to the previous step
– Is a prefix, not a word
• Explore the next possible step
– Is a prefix, is a word
• Save the word, explore the next possible step
– The function to check a prefix or a word are provided.
2016/9/12
15/16
Big Picture
• Proceed forward to a solution until it becomes apparent that
no solution can be achieved along the current path.
• At that point UNDO the solution (backtrack) to a point where
we can again proceed forward
• Some hints:
– Use a stack to track the history path.
• Push stack: advance step
• Pop stack: backtrack
– Use a variable for each cube to track what is the next direction to
explore. (stack)
• Advance step: push the next direction into the stack
• Backtrack: pop the next direction out of the stack
– Use a boolean table (2d array) to mark the cubes visited.
• Advance step: mark new cube
• Backtrack: unmark cube
2016/9/12
16/16