I heard different interpretations of sound and complete. I understand that completeness means finding a solution if there is one. What does it mean to say an algorithm is sound.  

What does it mean to say an algorithm is Sound and Complete?

These are very specific terms as related to logic.  

Here are some starting points: 

http://en.wikipedia.org/wiki/Soundness 

http://en.wikipedia.org/wiki/Completeness_(logic)

Basically, soundness (of an algorithm) means that the algorithm doesn't yield any results that are untrue.  If, for instance, I have a sorting algorithm that sometimes does not return a sorted list, the algorithm is not sound.

Completeness, on the other hand, means that the algorithm addresses all possible inputs and doesn't miss any.  So, if my sorting algorithm never returned an unsorted list, but simply refused to work on lists that contained the number 7, it would not be complete.

It is complete and sound if it works on all inputs (semantically valid in the world of the program) and always gets the answer right.
