Solving N-Queens and Missionaries & Cannibals Problems Using Search Algorithms
Explore the application of search algorithms in solving classic problems like the N-Queens problem and the Missionaries & Cannibals dilemma. Understand the concept of states, start states, goals, transitions, and goal states in these puzzles. Dive into the strategies of adding states to a to-visit list, checking for goal states, and determining reachable states, all essential components in algorithmic problem-solving.
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
SEARCH APPLICATIONS David Kauchak CS30 Spring 2015
N-queens problem Place N queens on an N by N chess board such that none of the N queens are attacking any other queen.
N-queens problem Place N queens on an N by N chess board such that none of the N queens are attacking any other queen.
N-queens problem Place N queens on an N by N chess board such that none of the N queens are attacking any other queen.
N-queens problem Place N queens on an N by N chess board such that none of the N queens are attacking any other queen. How do we solve this with search: What is a state? What is the start state? What is the goal? How do we transition from one state to the next?
Search algorithm add the start state to to_visit Repeat take a state off the to_visit list if it s the goal state we re done! if it s not the goal state Add all of the successive states to the to_visit list Is this a goal state? What states can I get to from the current state? Any problem that we can define these two things can be plugged into the search algorithm!
N queens problem http://en.wikipedia.org/wiki/Eight_queens_puzzle
Missionaries and Cannibals Three missionaries and three cannibals wish to cross the river. They have a small boat that will carry up to two people. Everyone can navigate the boat. If at any time the Cannibals outnumber the Missionaries on either bank of the river, they will eat the Missionaries. Find the smallest number of crossings that will allow everyone to cross the river safely. What is the state of this problem (it should capture all possible valid configurations)?
