Used a profiler to figure out the notSeen function is consuming 2/3 of the execution time.  Did some minor optimizations to the rule checking to help improve that for now.
Optimizing execute times: Impvroved by 280s by rewriting the markedSeen and notSeen functions to take advantage of dictionaries.  This allows for O(1) lookup times.  Current execution times are around 90seconds.
Reduced about 29seconds by reducing the number of calls to deepCopy().  This was accomplished by waiting to see if the new puzzle state was valid before making the copy.  The current puzzle state is used as a testing bed with each temporary move undone afterwards. Calls to deepCopy() went from about 36s of execution time to about 7seconds.
Reduced execution time by 1.5 seconds from the call to "conformsToRuleTwo()" by making a more thorough copy of the newly mutated Puzzle. I thought this would reduce execution time on "conformsToRuleThree()" as well, but no luck.
Reduced the isBlack and isWhite functions in execution time by about 9 seconds total. I think I can get larger gains if the conformsToRuleThree function is tackled directly, which makes a lot of calls to these functions.