Good feature engineering involves two components. The first is an understanding the properties of the task you're trying to solve and how they might interact with the strengths and limitations of the classifier you're using. The second is experimental work were you test your expectations and find out want actually works and what doesn't.
This can be done iteratively: Your top down understanding of the problem motivates experiments, and then the bottom up information you learn for those experiments helps you obtain a better understanding of the problem. The deeper understanding of the problem can then drive more experiments.
Fitting Features to Your Classifier
Say you're using a simple linear classifier like logistic-regression or a SVM with a linear kernel. If you think there might be interesting interactions between various attributes you can measure and provide as input to the classifier, you'll need to manually construct and provide features that capture those interactions. However, if you're using a SVM with a polynomial or Gaussian kernel, interactions between the input variables will already be captured by the structure of the model.
Similarly, SVMs can perform poorly if some input variables take on a much larger range of values than others (e.g., most features take on a value of 0 or 1, but one feature takes on values between -1000 and 1000). So, when doing feature engineering for a SVM, you might want to try normalizing the values of your features before providing them to the classifier. However, if you're using decision trees or random forests, such normalization isn't necessary, as these classifiers are robust to differences in magnitude between the values that various features take on.
Notes Specifically on Puzzle Solving
If you're looking at solving a problem with a complex state space, you might want to use a reinforcement learning approach like Q-learning. This helps structure learning tasks that involve reaching some goal by a serious of intermediate steps by the system.