4
$\begingroup$

Inspired from the N-Queens problem, I here propose you a puzzle from Xiangqi wich is Chinese Chess equivalent, mostly played in Asia.

The most different piece from Xiangqi is the cannon. You can search for cannon here. Quoting from there:

Cannons

https://upload.wikimedia.org/wikipedia/commons/thumb/2/2e/Xiangqi_Cannon_%28Trad%29.svg/274px-Xiangqi_Cannon_%28Trad%29.svg.png

Cannons move like chariots (or towers), any distance orthogonally without jumping, but can only capture by jumping a single piece, friend or foe, along the path of attack. The piece over which the cannon jumps is called the 炮臺 (trad.) / 炮台 (simp.) pào tái ("cannon platform" or "screen"). Any number of unoccupied spaces, including none, may exist between the cannon, screen, and the piece to be captured. Cannons can be exchanged for horses immediately from their starting positions.

enter image description here

Xiangqi board

An empty Xiangqi board is nextly shown:

Note that:

  • Cannons (C) can be exchanged for horses (H) immediately from their starting positions.
  • Each Xiangqi piece is located into an intersection, while it was on a case for Chess.
  • On this empty chessboard, there are $90$ possible intersections to put a cannon.

enter image description here

Intermediary Puzzle 1 : empty threat

From an empty Xiangqi board, find the maximum and minimum, $M>0$ and $n>0$ numbers of cannons you can put, so that no cannon is threatening another.

Intermediary Puzzle 2 : 1-threat

From an empty Xiangqi board, find the maximum and minimum, $M>0$ and $n>0$ numbers of cannons you can put, so that each cannon is threatened by exactly one other cannon.

Puzzle : $k$-threats, Part 1: $k \le 2$

From an empty Xiangqi board and for $0\le k\le 2$, find the maximum and minimum, $M>0$ and $n>0$ numbers of cannons you can put, so that each cannon is threatened by exactly $k$ other cannons.

Hint

$M$ and $n$ may not exist.

Another note from Rand al'Thor's comment:

A red cannon can not threaten another red cannon. It only can threaten a cannon from opponent side (black side). You can have an idea of this note in this similar chess puzzle.

See Part 2 here.

$\endgroup$
  • $\begingroup$ It seems that a cannon can threaten or be threatened by at most 4 others, so I wonder why you are asking for k up to 10? $\endgroup$ – Daniel Mathias Mar 27 at 23:48
  • $\begingroup$ @DanielMathias your comment is totally true and I edited my puzzle accordingly :) Thank you very much ;) $\endgroup$ – JKHA Mar 27 at 23:51
  • $\begingroup$ Colours of the cannons don't matter for this puzzle, right? Any two cannons with a piece between are assumed to be threatening each other? $\endgroup$ – Rand al'Thor Mar 27 at 23:59
  • $\begingroup$ @Randal'Thor, actually this matters. A cannon red cannon threaten another red cannon. It only can threaten a cannon from opponent side :) I'm adding it in the puzzle $\endgroup$ – JKHA Mar 28 at 0:01
  • $\begingroup$ So $M$ and $n$ in each case are the total number, number of red cannons plus number of black cannons? I need to scrap my answer progress then :-/ $\endgroup$ – Rand al'Thor Mar 28 at 0:02
4
$\begingroup$

The answers for $M$ are somewhat surprising! I expected smaller numbers.


$k=0$

Minimum

$n=1$, obviously.

Maximum

$M=90$. Fill the entire ($9\times10$) board with cannons, just make sure that in each row the colours are alternating (checkerboard pattern) so that two cannons of different colours are never attacking each other, i.e. two cannons with a single piece between them are always both the same colour.


$k=1$

Minimum

$n=4$. Put two black cannons and two red cannons in the same row, the red ones in between the black ones.

Maximum

$M=88$, because we can fill almost the whole board up like this:

b b r r r r r b b
r r b b b b b r r
b b r r . r r b b
r r b b b b b r r
b b r r r r r b b
r r b b b b b r r
b b r r r r r b b
r r b b . b b r r
b b r r r r r b b
r r b b b b b r r

In any position where each cannon attacks exactly one other, the cannons can all be divided into mutually attacking pairs (so the total number must be even).

In a given line (row or column), reading along the cannons and ignoring gaps between, assuming no orthogonal attacks, we must start with EITHER b r r b or b b r r (or the colour-swapped versions of these), then continue with EITHER b r r b r b b r or b b r r r r b b (or colour-swapped versions), and in either case continuing further would mean at least 12 pieces in the line, which is impossible.

So first we can fill in every row as

b b r r . r r b b
r r b b . b b r r
b b r r . r r b b
r r b b . b b r r
b b r r . r r b b
r r b b . b b r r
b b r r . r r b b
r r b b . b b r r
b b r r . r r b b
r r b b . b b r r

and then fill that middle column as best we can.


$k=2$

Minimum

$n=16$, with a square like this somewhere in the board:

b r r b
r b b r
r b b r
b r r b

Maximum

I think $M=64$, by filling most of the grid like this:

b r r b . r b b r
r b b r . b r r b
r b b r . b r r b
b r r b . r b b r
. . . . . . . . .
. . . . . . . . .
r b b r . b r r b
b r r b . r b b r
b r r b . r b b r
r b b r . b r r b

Note that we can't fill just one row with every cannon attacking two others, because the outermost cannons can always attack only one. So there must be attacks going both vertically and horizontally, and the best way to ensure this is to make every cannon attack exactly one vertically and one horizontally. That means we're back to the same within-line (row or column) configurations as discussed above, and this seems to be the best way to do it.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I think your $k=2$ Maximum is wrong because some cannons or threatening 3 other cannons. Some even threathen four! +1 for all the others :) $\endgroup$ – JKHA Mar 28 at 0:28
  • 1
    $\begingroup$ @JKHA Actually there's a mistake in my $k=1$ maximum and my $k=2$ maximum :-/ Working on fixing those now ... $\endgroup$ – Rand al'Thor Mar 28 at 0:32
  • $\begingroup$ Actually, there is the same mistake for $k=1$ Maximum, there are cannons that are not threatening the correct number of other cannons. For instance, the black in the middle is threatening $4$ other red cannons. $\endgroup$ – JKHA Mar 28 at 0:32
  • 1
    $\begingroup$ @JKHA Now the $k=1$ and $k=2$ maximums both work. I think these are maximal; I'll try to write up at least a sketch proof of that. $\endgroup$ – Rand al'Thor Mar 28 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.