Strategies in Solving N-Queens Puzzle
Start with an empty board
Repeat:
Add a queen to a column
Start with an empty board
Repeat:
Add a queen to a column
…
Should we keep going?
Start with an empty board
Repeat:
Add a queen to a column
…
No! Even though this is a “partial” state,
we know that any solution that starts
with this partial state will not result in a
solution
Start with an empty board
Repeat:
Add a queen to a column
…
How many “complete” states did we just
remove from consideration?
Start with an empty board
Repeat:
Add a queen to a column
4*4 = 16 states (~6% of the states)
We saved ourselves from having to
examine these!
…
Now what should we do?
Start with an empty board
Repeat:
Add a queen to a column
Start with an empty board
Repeat:
Add a queen to a column
Start with an empty board
Repeat:
Add a queen to a column
Start with an empty board
Repeat:
Add a queen to a column
Now what?
Start with an empty board
Repeat:
Add a queen to a column
Start with an empty board
Repeat:
Add a queen to a column
Start with an empty board
Repeat:
Add a queen to a column
Start with an empty board
Repeat:
Add a queen to a column
Start with an empty board
Repeat:
Add a queen to a column
…
Eventually we realize none of the queen
positions in the 3
rd
column work from this
partial state.
Now what?
Start with an empty board
Repeat:
Add a queen to a column
Backtrack to the first column and try a different queen position
This is called “
backtracking search with branch and bound
”.
•
Backtracking
: if you don’t find a solution down one path,
backtrack to the last place you had another option and try that
path.
•
Branch and bound
: don’t go down any paths from a partial state
where you know you cannot get to a solution
Backtrack to the first column and try a different queen position
This is called “
backtracking search with branch and bound
”.
•
Backtracking
: if you don’t find a solution down one path,
backtrack to the last place you had another option and try that
path.
•
Branch and bound
: don’t go down any paths from a partial state
where you know you cannot get to a solution
Exhaustive search
: is state a solution? (true/false)
What do we need to ask for branch and bound?
Backtrack to the first column and try a different queen position
This is called “
backtracking search with branch and bound
”.
•
Backtracking
: if you don’t find a solution down one path,
backtrack to the last place you had another option and try that
path.
•
Branch and bound
: don’t go down any paths from a partial state
where you know you cannot get to a solution
Exhaustive search
: is state a solution? (true/false)
Branch and bound search
: ask questions about
partial
states/solutions
.
What different values could we have for a partial configuration?
Backtrack to the first column and try a different queen position
This is called “
backtracking search with branch and bound
”.
•
Backtracking
: if you don’t find a solution down one path,
backtrack to the last place you had another option and try that
path.
•
Branch and bound
: don’t go down any paths from a partial state
where you know you cannot get to a solution
PENDING
No problems yet. Solutions
could
include this partial
configuration
INCORRECT
CORRECT
Solution!
No way to reach a solution from this partial configuration.
Backtrack to the first column and try a different queen position
This is called “
backtracking search with branch and bound
”.
•
Backtracking
: if you don’t find a solution down one path,
backtrack to the last place you had another option and try that
path.
•
Branch and bound
: don’t go down any paths from a partial state
where you know you cannot get to a solution
Exhaustive search
: next state function transitions from one
complete
state to
another
complete
state
What do we do for backtracking (w/ branch and bound)?
Start with an empty board
Repeat:
Add a queen to a column
[] : PENDING
Start with an empty board
Repeat:
Add a queen to a column
[1] : PENDING
[] : PENDING
Now what?
Start with an empty board
Repeat:
Add a queen to a column
[1] : PENDING
[] : PENDING
[1,1] :
INCORRECT
Start with an empty board
Repeat:
Add a queen to a column
[1] : PENDING
[] : PENDING
[2,1] :
INCORRECT
Start with an empty board
Repeat:
Add a queen to a column
[1] : PENDING
[] : PENDING
[3,1] :
PENDING
Two types of transitions between partial states:
Start with an empty board
Repeat:
Add a queen to a column
[1] : PENDING
[] : PENDING
[3,1] :
PENDING
Two types of transitions between partial states:
•
extend
: current configuration is plausible
(PENDING) build upon this configuration
Start with an empty board
Repeat:
Add a queen to a column
[1] : PENDING
[] : PENDING
[3,1] : PENDING
Two types of transitions between partial states:
•
extend
: current configuration is good
(PENDING) build upon this configuration
•
increment
: current configuration is bad
(INCORRECT) try
changing
the configuration
(without adding anything)
[2,1] : INCORRECT
[1,1] : INCORRECT
To the code!
http://atomicwanderers.com/2013/12/05/gotham-city-14-
miles-and-the-batmobile-parachute-pickup-service/
Dive into the process of solving the N-Queens puzzle by adding one queen to a column at a time on an empty board. Witness the elimination of partial states that do not lead to a solution, appreciating the reduction in considered complete states and the strategic decision-making involved in reaching a solution.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Start with an empty board Repeat: Add a queen to a column
Start with an empty board Repeat: Add a queen to a column Q
Start with an empty board Repeat: Add a queen to a column Q Q Q Should we keep going?
Start with an empty board Repeat: Add a queen to a column Q No! Even though this is a partial state, we know that any solution that starts with this partial state will not result in a solution Q Q
Start with an empty board Repeat: Add a queen to a column Q How many complete states did we just remove from consideration? Q Q 4*4 = 16 states (~6% of the states) We saved ourselves from having to examine these!
Start with an empty board Repeat: Add a queen to a column Q Now what should we do? Q Q
Start with an empty board Repeat: Add a queen to a column Q Q Q
Start with an empty board Repeat: Add a queen to a column Q Q Q
Start with an empty board Repeat: Add a queen to a column Q Now what? Q Q Q Q Q Q Q Q Q Q Q Q Q Q
Start with an empty board Repeat: Add a queen to a column Q Q Q
Start with an empty board Repeat: Add a queen to a column Q Q Q Q Q Q
Start with an empty board Repeat: Add a queen to a column Q Q Q Q Q Q
Start with an empty board Repeat: Add a queen to a column Q Q Q Q Q Q
Start with an empty board Repeat: Add a queen to a column Q Q Q Eventually we realize none of the queen positions in the 3rd column work from this partial state. Q Now what? Q Q
Start with an empty board Repeat: Add a queen to a column Q Backtrack to the first column and try a different queen position This is called backtracking search with branch and bound . Backtracking: if you don t find a solution down one path, backtrack to the last place you had another option and try that path. Branch and bound: don t go down any paths from a partial state where you know you cannot get to a solution
Backtrack to the first column and try a different queen position This is called backtracking search with branch and bound . Backtracking: if you don t find a solution down one path, backtrack to the last place you had another option and try that path. Branch and bound: don t go down any paths from a partial state where you know you cannot get to a solution Exhaustive search: is state a solution? (true/false) What do we need to ask for branch and bound?
Backtrack to the first column and try a different queen position This is called backtracking search with branch and bound . Backtracking: if you don t find a solution down one path, backtrack to the last place you had another option and try that path. Branch and bound: don t go down any paths from a partial state where you know you cannot get to a solution Exhaustive search: is state a solution? (true/false) Branch and bound search: ask questions about partial states/solutions. Q Q What different values could we have for a partial configuration?
Backtrack to the first column and try a different queen position This is called backtracking search with branch and bound . Backtracking: if you don t find a solution down one path, backtrack to the last place you had another option and try that path. Branch and bound: don t go down any paths from a partial state where you know you cannot get to a solution Q Q No way to reach a solution from this partial configuration. INCORRECT Q PENDING No problems yet. Solutions could include this partial configuration Q Q Q CORRECT Solution! Q Q
Backtrack to the first column and try a different queen position This is called backtracking search with branch and bound . Backtracking: if you don t find a solution down one path, backtrack to the last place you had another option and try that path. Branch and bound: don t go down any paths from a partial state where you know you cannot get to a solution Exhaustive search: next state function transitions from one complete state to another complete state What do we do for backtracking (w/ branch and bound)?
Start with an empty board [] : PENDING Repeat: Add a queen to a column
Start with an empty board [] : PENDING Repeat: Add a queen to a column Q [1] : PENDING
Start with an empty board [] : PENDING Repeat: Add a queen to a column Q [1] : PENDING Q Q Now what? [1,1] : INCORRECT
Start with an empty board [] : PENDING Repeat: Add a queen to a column Q [1] : PENDING Q [2,1] : INCORRECT Q
Start with an empty board [] : PENDING Repeat: Add a queen to a column Q [1] : PENDING Two types of transitions between partial states: Q [3,1] : PENDING Q
Start with an empty board [] : PENDING Repeat: Add a queen to a column Q [1] : PENDING Two types of transitions between partial states: extend: current configuration is plausible (PENDING) build upon this configuration Q [3,1] : PENDING Q
Start with an empty board [] : PENDING Repeat: Add a queen to a column Q [1] : PENDING Two types of transitions between partial states: extend: current configuration is good (PENDING) build upon this configuration increment: current configuration is bad (INCORRECT) try changing the configuration (without adding anything) [1,1] : INCORRECT Q [2,1] : INCORRECT Q [3,1] : PENDING
To the code! http://atomicwanderers.com/2013/12/05/gotham-city-14- miles-and-the-batmobile-parachute-pickup-service/
