Example Search Problem: SAT
We need to define problems and solutions
Propositional Satisfiability (SAT)
- really a logical problem -- I’ll present as a letters game
Problem is a list of words
- contains upper and lower case letters (order unimportant)
- e.g. ABC, ABc, AbC, Abc, aBC, abC, abc
Solution is choice of upper/lower case letter
- one choice per letter
- each word to contain at least one of our choices
- e.g. AbC is unique solution to above problem.