2
$\begingroup$

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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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
    Commented Apr 15, 2017 at 14:32
  • $\begingroup$ Yes. ​ ​ ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Apr 15, 2017 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$
    – tomoka kazuki
    Commented Apr 16, 2017 at 3:00

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.