Exploring Strategies in Solving N-Queens Puzzle

Slide Note

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.

brazile_m Follow

Uploaded on Sep 20, 2024 | 0 Views

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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

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