Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2604.01935 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911562964402176 |
|---|---|
| author | Li, Chao Zhang, Zhujun Yang, Chao |
| author_facet | Li, Chao Zhang, Zhujun Yang, Chao |
| contents | 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 NP-complete problem 3-SAT. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_01935 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | King Chasing Problem in Chinese Chess is NP-hard Li, Chao Zhang, Zhujun Yang, Chao Combinatorics Computational Complexity 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 NP-complete problem 3-SAT. |
| title | King Chasing Problem in Chinese Chess is NP-hard |
| topic | Combinatorics Computational Complexity |
| url | https://arxiv.org/abs/2604.01935 |