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?

  • Comments are not for extended discussion; this conversation has been moved to chat. – Gilles Apr 15 '17 at 16:37

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

  • In your position, the white huygens must be on the same row/column as the black king, otherwise it's trivially decidable. – Ariel Apr 15 '17 at 14:32
  • Yes. ​ ​ ​ ​ ​ ​ – user12859 Apr 15 '17 at 14:33
  • 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. – tomoka kazuki Apr 16 '17 at 3:00

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.