--- title: "Well defined problem, state-space search" subject: "Artificial Intelligence" chapter: 2 key: "semester_6/artificial_intelligence:well-defined-problem-state-space" source: https://www.bctengineer.com/q/semester_6/artificial_intelligence/well-defined-problem-state-space site: BCT Engineering --- # Well defined problem, state-space search Artificial Intelligence · Chapter 2: Problem Solving - Asked in: 2071 Bhadra, 3+4 marks - Video: [Well-defined problems Toy problems Vacuum World Example in Artificial Intelligence by Mahesh Huddar](https://www.youtube.com/watch?v=ZBiHAUTYWVc) — Mahesh Huddar - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/artificial_intelligence/well-defined-problem-state-space - Whole chapter: https://www.bctengineer.com/md/semester_6/artificial_intelligence/chapter-2 ## Question What makes a problem "Well Defined"? Explain with a sample example of a state-space search framework. ## Short answer A problem is well defined when it has initial state, operators/successor function, goal test, and path cost; these define the state space. Example: 8-puzzle, with state as tile positions, operators moving blank, goal test matching goal board, path cost 1 per move. ## Answer #### What makes a problem well defined? A problem is **well defined** when it is specified precisely enough for a program to solve it. It needs four components (Russell and Norvig): 1. **Initial state:** where the agent starts. 2. **Operators / successor function:** the actions available and the states they lead to. 3. **Goal test:** a way to check whether a state is a goal (explicit set of states or an abstract property). 4. **Path cost:** a numeric cost for each path (e.g. sum of step costs). A solution is a path from the initial state to a goal state; the best solution has the lowest path cost. The initial state and operators together define the **state space**, the set of all states reachable from the start, which forms a graph (nodes = states, edges = actions). #### State-space search example: the 8-puzzle A 3 x 3 board has tiles 1-8 and one blank. Tiles next to the blank can slide into it. | Component | 8-puzzle | |---|---| | State | Location of each tile and the blank (9!/2 = 181,440 reachable states) | | Initial state | Any given arrangement, e.g. below left | | Operators | Move blank Up, Down, Left, Right (if legal) | | Goal test | Board equals the goal arrangement | | Path cost | 1 per move; total cost = number of moves | ```text Initial Goal 2 8 3 1 2 3 1 6 4 --> 8 _ 4 7 _ 5 7 6 5 ``` **Search framework:** start at the root (initial state), generate successors using the operators, put them on a frontier, pick a node using a strategy (BFS, DFS, A*), test the goal, and repeat. The sequence of moves along the path to the goal is the solution. ```text [2 8 3 / 1 6 4 / 7 _ 5] / | \ blank up blank left blank right ... [2 8 3/1 _ 4/ ...] [... ] [... ] ``` Another well-defined problem is route finding: states = cities, operators = roads, goal = destination, cost = distance. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which is NOT a component of a well-defined problem? A. Heuristic neural weights B. Initial state C. Goal test D. Path cost Answer: A. The four components are initial state, operators, goal test and path cost. (Key point: Four components) 2. What forms the state space? A. Only the goal states B. The initial state and operators together define all states reachable from the start C. The path cost D. The goal test Answer: B. The state space is the graph of reachable states, with nodes as states and edges as actions. (Key point: State space) 3. In the 8-puzzle, what are the operators? A. Swap any two tiles B. Remove a tile C. Move the blank up, down, left or right if legal D. Rotate the board Answer: C. Tiles next to the blank slide into it, equivalent to moving the blank. (Key point: 8-puzzle operators) 4. What is the path cost in the 8-puzzle? A. Number of tiles in place B. Always 0 C. 9! per move D. 1 per move, total equals number of moves Answer: D. Each move costs 1, so the total is the number of moves. (Key point: Path cost) ## Related in Artificial Intelligence - [Problem space; BASE+BALL=GAMES](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Aproblem-space-base-ball-games) — Artificial Intelligence, chapter 2 ## Related in other subjects - [Sample space, event, outcome definitions](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Asample-space-event-outcome) — Probability and Statistics, chapter 1 - [Pattern vs framework; GRASP patterns](https://www.bctengineer.com/question.md?key=semester_6%2Fobject_oriented_analysis_and_design%3Apattern-vs-framework-grasp) — Object Oriented Analysis and Design, chapter 3 - [Gel/space ratio and strength (550 gm cement)](https://www.bctengineer.com/question.md?key=semester_5%2Fconcrete_technology_and_masonry_structure%3Agel-space-ratio-550g) — Concrete Technology and Masonry Structure, chapter 4, asked 3× - [Gel/space ratio and strength (600 gm cement)](https://www.bctengineer.com/question.md?key=semester_5%2Fconcrete_technology_and_masonry_structure%3Agel-space-ratio-600g) — Concrete Technology and Masonry Structure, chapter 4, asked 3×