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
    $\begingroup$ 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). $\endgroup$
    – Ariel
    Sep 30, 2015 at 12:47
  • 2
    $\begingroup$ If the size of your board is fixed, it's even decidable in constant time. $\endgroup$
    – François
    Sep 30, 2015 at 12:59
  • $\begingroup$ 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. $\endgroup$
    – TLW
    Sep 30, 2015 at 19:01

1 Answer 1


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

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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