3 ms·
I wonder how they set the initial state. I think it's fairly easy to calculate the minimum number of moves required to solve from a given state, so you'd think
by baddox 11y ago
I wonder how they set the initial state. I think it's fairly easy to calculate the minimum number of moves required to solve from a given state, so you'd think they would control for this.
- rusbus 11y agoMost states can be solved in around 21 moves by the best computer algorithms, but the fastest humans usually solve it in significantly more.
- deleted 11y ago[deleted]
- atom-morgan 11y agoThe initial state is a random computer generated scramble. It's easy to calculate if you have a computer but it isn't easy when you have to do it in your head.
- harryh 11y agoIt is, in fact, not easy at all to calculate that. https://en.wikipedia.org/wiki/God%27s_algorithm https://en.wikipedia.org/wiki/God%27s_algorithm (There isn't as much info as there should be on that Wikipedia page but it was an open area of research for decades.)
- deleted 11y ago[deleted]
- baddox 11y agoIsn't it though? I thought the hard part was proving the minimum number of moves that can solve all possible initial states. Korf's algorithm and several subsequent improvements seem to be able to find the minimum number of moves to solve any given initial state.
- harryh 11y agoA yes. You are correct. Finding minimum # of moves from a single state = not so hard. Finding the worst possible state (the state where the minimum # of moves is a maximum) = pretty hard, though now solved.