Exploring Strategies in Solving N-Queens Puzzle

Slide Note
Embed
Share

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.


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


  1. Start with an empty board Repeat: Add a queen to a column

  2. Start with an empty board Repeat: Add a queen to a column Q

  3. Start with an empty board Repeat: Add a queen to a column Q Q Q Should we keep going?

  4. 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

  5. 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!

  6. Start with an empty board Repeat: Add a queen to a column Q Now what should we do? Q Q

  7. Start with an empty board Repeat: Add a queen to a column Q Q Q

  8. Start with an empty board Repeat: Add a queen to a column Q Q Q

  9. 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

  10. Start with an empty board Repeat: Add a queen to a column Q Q Q

  11. Start with an empty board Repeat: Add a queen to a column Q Q Q Q Q Q

  12. Start with an empty board Repeat: Add a queen to a column Q Q Q Q Q Q

  13. Start with an empty board Repeat: Add a queen to a column Q Q Q Q Q Q

  14. 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

  15. 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

  16. 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?

  17. 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?

  18. 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

  19. 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)?

  20. Start with an empty board [] : PENDING Repeat: Add a queen to a column

  21. Start with an empty board [] : PENDING Repeat: Add a queen to a column Q [1] : PENDING

  22. Start with an empty board [] : PENDING Repeat: Add a queen to a column Q [1] : PENDING Q Q Now what? [1,1] : INCORRECT

  23. Start with an empty board [] : PENDING Repeat: Add a queen to a column Q [1] : PENDING Q [2,1] : INCORRECT Q

  24. 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

  25. 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

  26. 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

  27. To the code! http://atomicwanderers.com/2013/12/05/gotham-city-14- miles-and-the-batmobile-parachute-pickup-service/

Related