I noticed in a paper that the mate-in-n problem of chess, even played on an infinite board is decidable. The mate-in-n problem of infinite chess is decidable

I believe the paper assumes only traditional chess pieces are used.

What if one of the chess pieces is a huygens? (A huygens is a chess piece which jumps prime numbers of squares).

Is the mate-in-n problem of chess on an unbounded board with each color using traditional chess pieces plus at least one huygens also decidable?


Presburger arithmetic with a predicate for the primes is probably undecidable, so at least the technique used by your question's link should not easily generalize to allowing a huygens.

For example, although decidability of the special case I'm about to mention
would follow from there being only finitely many positive even integers that
are neither prime gaps nor sums of two distinct primes, I don't see any way of
proving decidability of mate-in-ONE for king+huygens against a smothered king:

enter image description here

  • $\begingroup$ In your position, the white huygens must be on the same row/column as the black king, otherwise it's trivially decidable. $\endgroup$
    – Ariel
    Apr 15 '17 at 14:32
  • $\begingroup$ Yes. ​ ​ ​ ​ ​ ​ $\endgroup$
    – user12859
    Apr 15 '17 at 14:33
  • $\begingroup$ I think that's a good answer, and I also like the composed position you created to illustrate it. I really appreciate the thought that you put into this. $\endgroup$ Apr 16 '17 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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