Open Research Index

King Chasing Problem in Chinese Chess is NP-hard

Chao Li, Zhujun Zhang, Chao Yang

arXivarxiv/2604.01935Apr 2, 2026math.COscore 0

We prove that king chasing problem in Chinese Chess is NP-hard when generalized to $n\times n$ boards. `King chasing' is a frequently-used strategy in Chinese Chess, which means that the player has to continuously check the opponent in every move until finally checkmating the opponent's king. The problem is to determine which player has a winning strategy in generalized Chinese Chess, under the constraints of king chasing. Obviously, it is a sub-problem of generalized Chinese Chess problem. We prove that king chasing problem in Chinese Chess is NP-hard by reducing from the classic…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2604.01935
curl -X POST /api/v1/records/arxiv/2604.01935/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.01935/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'