Just for fun, I've written a puzzle program to see if I can solve it. A good analogy would be Rubik's cube.
I have deliberately not tried to solve it myself, but know that it can be solved - simply by reversing shuffling operations ( as per Rubik's cube)
What I'd like to know is : Can a program be written that will solve the puzzle without using brute-force?
Given that the solving program knows the following:
- the solved state of the puzzle
- the current state of the puzzle at any time
- all actions available to the solver to change the puzzle sate
Thanks
For exemple there are many Sudoku solvers that uses various AI-techniques to solve a grid in a few millseconds while a brute-force solution would take the age of the universe or more !
On the other hand there are also some ($NP$-)hard problems that can be proven to have no "clever" solution besides brute-force (Unless $P = NP$ but this is getting a bit technical). For exemple, if I give you an undirected graph and three pens of three different colors and then I ask you to color every vertex with one color such that no adjacent vertex have the same color. Then the only way to solve that is more or less brute-force. (Wiki, Advanced stuff)
This is a very informal answer I know, but so is the question.