If we have a finite chess board and two figures x and y. Is it possible to get y from x by following chess rules and when white is y and white starts from y placement. Is this decidable?

My reasoning is, that we have a finite sets of moves and since all finite languages are decidable and at some point x is going to get y this problem is decidable. What do you think?

  • 1
    BFS on the graph of all possible positions, where two positions are connect if you can reach from one to the other in a single move (a pretty big graph, but who cares). – Ariel Sep 30 '15 at 12:47
  • 2
    If the size of your board is fixed, it's even decidable in constant time. – François Sep 30 '15 at 12:59
  • Note that there are cycles in chess. (In particular, even though the 50-move rule exists it requires a player to claim it, and a player may not claim it) As such, you do need to do a proper graph search. Otherwise your TM won't decide the question, just accept it, as in the case of y not being reachable from x it'll potentially get caught in a loop and never halt. – TLW Sep 30 '15 at 19:01
up vote 4 down vote accepted

The chess board problem is, although complex, a finite problem. Specifically, the number of moves, starting from any board position, is finite.

Then, a TM can just go over all the possible moves (there are only $C$ such moves, for some "small" constant $C$), and verify if a certain position is feasible continuation of a prior position. Hence, any such question is decidable.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.