Scribd
Upload
7 views3 pages

Towers of Hanoi and 8-Puzzle Search Problems

The document discusses two classical problems in computer science: the Towers of Hanoi and the 8-Puzzle. It outlines specific questions related to state representation, state space size, start state, legal actions, goal tests, and cost representation for both problems. The focus is on formulating these problems as search problems and analyzing their components.

Uploaded by

Zach Hsu
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
7 views3 pages

Towers of Hanoi and 8-Puzzle Search Problems

The document discusses two classical problems in computer science: the Towers of Hanoi and the 8-Puzzle. It outlines specific questions related to state representation, state space size, start state, legal actions, goal tests, and cost representation for both problems. The focus is on formulating these problems as search problems and analyzing their components.

Uploaded by

Zach Hsu
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Search Discussion question

Taken from CS188 Summer 2022

1 Towers of Hanoi

The Towers of Hanoi is a famous problem for studying recursion in computer science and recurrence
equations in discrete mathematics. We start with N discs of varying sizes on a peg (stacked in
order according to size), and two empty pegs. We are allowed to move a disc from one peg to
another, but we are never allowed to move a larger disc on top of a smaller disc. The goal is to
move all the discs to the rightmost peg (see figure).

In this problem, we will formulate the Towers of Hanoi as a search problem.

(a) Propose a state representation for the problem

(b) What is the size of the state space?

(c) What is the start state?

(d) From a given state, what actions are legal?

(e) What is the goal test?

1
2 8-Puzzle Problem
Consider the game of 8-Puzzle below:

Goal is to start from an unordered configuration of blocks, and using 2d sliding end up with an
ordering where the first slot is empty.

(a)What are the states?

(b)How to model the Search States?

(c) What are the actions?

(d)What is the goal test?

2
(e) What about the cost, what do you use to represent cost of action then then you will try to
minimize in the long run?

(f) Draw the search tree for first row.

You might also like