Questions: Problem Representation and Solution Search

Question 1

Two chess players encounter an unfamiliar position. Player A immediately thinks: 'The queen on d6 is undefended — this looks like a forcing sequence exists.' Player B thinks: 'There's a queen, two rooks, several pawns…' and starts evaluating moves one by one. What best explains Player A's faster, more accurate analysis?

• A. Player A has greater working memory capacity, allowing them to hold more candidate moves in mind simultaneously
• B. Player A is using a better problem representation — encoding the position in terms of structural chess principles rather than surface piece locations
• C. Player A is using a more exhaustive search strategy, evaluating all continuations before settling on a candidate
• D. Player A's shortcuts are faster but less reliable; Player B's approach is more accurate despite being slower

Answer: (B)

The key insight is that Player A's representation ('exposed queen → forcing sequence') encodes the position's deep structural features — the relationships that determine what solutions are possible. This collapses the search space before any search begins. Research on expert chess players shows they are not faster at searching move trees; they represent positions differently, chunking them into meaningful patterns that immediately suggest the relevant part of the problem space. Player A may actually be MORE accurate, not less — because they are searching the right space rather than all spaces.

Question 2

The mutilated chessboard problem (two opposite corner squares removed from a standard chessboard: can 31 dominoes tile the 62 remaining squares?) is extremely difficult when approached by trying different domino placements, but immediately obvious once you notice that opposite corners are the same color and each domino must cover one black and one white square. This best illustrates:

• A. That heuristics are unreliable for geometric problems and exhaustive search should always be used instead
• B. That problem-solving speed depends primarily on how efficiently the search algorithm traverses the problem space
• C. That problem representation determines problem difficulty — the right representation makes the answer visible without search
• D. That spatial reasoning is generally inferior to abstract reasoning for discrete mathematics problems

Answer: (C)

The mutilated chessboard is not solved by searching harder — it is solved by representing the problem differently. Spatial representation ('where do the dominoes go?') creates an enormous search space with no clear path to a proof. Color-constraint representation ('how many black and white squares remain?') makes the impossibility immediately visible: 30 of one color and 32 of the other means 31 dominoes cannot possibly work, since each covers exactly one of each. No search is needed. This is the central principle: the right representation can collapse a problem from intractable to trivial.

Question 3

Means-ends analysis and working-backward are useful problem-solving strategies because they focus search on what is most relevant, reducing the number of states and operators that need to be evaluated.

• T. True
• F. False

Answer: True

Means-ends analysis identifies the largest difference between the current state and the goal, then selects the operator that most directly reduces that difference — concentrating search on the most promising directions rather than exploring uniformly. Working backward starts from the goal state and identifies what state must have preceded it, pruning the search space by starting from the constraints the solution must satisfy. Both strategies exploit the structure of the problem to make large search spaces tractable, rather than enumerating all possible state transitions.

Question 4

Once a solver adopts a good problem representation, search strategies like means-ends analysis and heuristics become unnecessary.

• T. True
• F. False

Answer: False

Good representation and efficient search are complementary, not mutually exclusive. Representation determines the structure and size of the problem space — sometimes dramatically collapsing it. But many real problems (chess, route planning, engineering design) have large problem spaces even with excellent representations. In those cases, search strategies are essential for finding solutions within bounded time and cognitive resources. The two tools work together: representation determines the space you are searching; search strategies navigate it efficiently.

Question 5

Why does problem representation matter more than search effort for determining problem-solving difficulty? Give an example that illustrates this principle.

Model answer: Problem representation determines the structure of the problem space — which states exist, which operators apply, and how close any given state is to the goal. A representation that encodes the deep structural features of a problem creates a small, navigable space where solutions are visible or quickly found. A representation that maps onto surface features creates a large, undifferentiated space that resists exhaustive search. The mutilated chessboard illustrates this: representing it spatially ('where do 31 dominoes go?') forces hopeless search through an astronomical number of tilings. Representing it in terms of color constraints ('are there equal numbers of black and white squares?') makes the impossibility immediately deducible — no search required. The difference is not how hard you search; it is what you encode.

This is the conceptual heart of problem representation research. Students who think problem-solving is primarily about effort or technique miss the insight that expert performance is largely about having better structured representations that avoid the need for extensive search in the first place.