King Chasing Problem in Chinese Chess is NP-hard

Chao Li, Zhujun Zhang, Chao Yang

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 th…