9
$\begingroup$

In this puzzle the standard chess rules apply on standard 8x8 board, white has King & Queen and black has his King, the only exception to normal rules is that white is not allowed to move his king. White wins when he mates black, black wins if white can't mate in any finite amount of moves.

It is a well known fact that white can mate if he is allowed to move both his king and queen pretty easily. The challenge is to do it only moving the queen, the white king remains paralyzed in his starting position.

The initial position I propose for this question is: White king starts at c3. White queen and black king are setup somewhere (in a legal position) and it is white to move. Can white force mate? For which starting positions?

Edit: Black can't "touch" the white king by moving next to it, it's an illegal move, as in normal chess. Think of this puzzle as a situation in which white has to mate normally but doesn't want to move the white king.

Edit: I'm having confusions between Row, rank file. Before answering you, please clarify me this. In matrix notation i normally call them rows (horizontal lines) and columns (vertical lines). Please answer me if you are using with this convention: column=file. Row=rank

$\endgroup$
  • $\begingroup$ Would the white king be allowed to attack the black king if it got in range? $\endgroup$ – Areeb Jul 3 '16 at 18:35
  • $\begingroup$ @Areeb You are not allowed to put your own King in check, assuming that White can still attack if this happens. $\endgroup$ – Klyzx Jul 3 '16 at 19:26
  • $\begingroup$ @CaelanO'Toole that's what I was confused about, since white can't move it is really check? $\endgroup$ – Areeb Jul 3 '16 at 19:33
  • $\begingroup$ Well, black doesn't win by killing the white king, so, maybe. $\endgroup$ – Klyzx Jul 3 '16 at 19:36
  • $\begingroup$ @Areeb I understand from what place that doubt came from. No, the intended puzzle you can't put your own black king in check, and yes, that's check because as in the post, standard chess rules apply. $\endgroup$ – Santropedro Jul 3 '16 at 21:07
2
$\begingroup$

I believe White

can force mate from every legal starting position.

Unfortunately, I believe this

because my crappy home-grown Python program thinks it has found mates for white from every position in at most 46 half-moves -- but the program might consist entirely of bugs.

(Earlier I said "30 moves" which was ambiguous between full-moves and half-moves and wrong either way. I've fixed a bug. The conclusion is the same.)

Here is my crappy Python program:

# position is encoded as follows: WQ x,y in bits 0..2, 3..5;
# BK x,y in bits 6..8, 9..11; BTM flag in bit 12.

moves = [[] for i in range(8193)] # possible successors
states = [None for i in range(8193)] # (Wwin?, halfmoves to end)

states[8192] = (0,0) # immediate draw (pseudo-position for when WQ captured)

# compute moves available in each position and note immediate
# win/draw results

for qx in range(8):
  for qy in range(8):
    for kx in range(8):
      for ky in range(8):
        for btm in (0,1):
          p = qx | (qy<<3) | (kx<<6) | (ky<<9) | (btm<<12)
          m = []
          if btm:
            for dx in (-1,0,+1):
              for dy in (-1,0,+1):
                if dx==dy==0: continue
                kx2,ky2 = kx+dx,ky+dy
                if not (0<=kx2<8 and 0<=ky2<8): continue # off the board
                if max(abs(kx2-2),abs(ky2-2))<=1: continue # into check by WK
                if kx2==qx or ky2==qy or abs(kx2-qx)==abs(ky2-qy): # into check by WQ
                  if kx2==qx and ky2==qy and max(abs(qx-2),abs(qy-2))>1:
                    m.append(8192) # capture WQ
                  else: continue
                m.append(qx | (qy<<3) | (kx2<<6) | (ky2<<9) | (0<<12))
            moves[p] = m
            if not m:
              # no moves: checkmate or stalemate
              if kx==qx or ky==qy or abs(kx-qx)==abs(ky-qy):
                states[p] = (1,0) # immediate win
              else:
                states[p] = (0,0) # immediate draw
          else:
            # wtm
            m = []
            for dx in (-1,0,+1):
              for dy in (-1,0,+1):
                if dx==dy==0: continue
                for n in range(1,9):
                  qx2,qy2 = qx+n*dx,qy+n*dy
                  if not (0<=qx2<8 and 0<=qy2<8): break # off board
                  if qx2==2 and qy2==2: break # collision with WK
                  # no need to check for collision with BK because
                  # WTM positions where this can happen are illegal
                  m.append(qx2 | (qy2<<3) | (kx<<6) | (ky<<9) | (1<<12))
            moves[p] = m

def descr(p):
  return "WQ%s%d BK%s%d %stm" % ("abcdefgh"[p&7], ((p>>3)&7)+1, "abcdefgh"[(p>>6)&7], ((p>>9)&7)+1, "wb"[(p>>12)&1])

# now very inefficiently keep looking for positions whose win/draw status
# is resolvable

changed = True
while changed:
  changed = False
  for i in range(8192):
    if not moves[i]: continue
    btm = (i>>12)&1
    wtm = 1-btm
    seen = [0,0,0]
    for j in moves[i]:
      if states[j]==None: seen[2]=1
      else: seen[states[j][0]]=1
    if seen[wtm]:
      # W has a move to (1,---) so this is a W win
      # or B has a move to (0,---) so this is a draw
      minr = min(states[j][1] for j in moves[i] if states[j] is not None and states[j][0]==wtm)
      if states[i] is None or states[i][1]>minr+1:
        states[i] = (wtm,minr+1)
        changed = True
        print descr(i), states[i]
    elif not seen[2]:
      # all W moves lead to (0,---) so this is a draw
      # or all B moves lead to (1,---) so this is a W win
      maxr = max(states[j][1] for j in moves[i] if states[j] is not None and states[j][0]==btm)
      if states[i] is None or states[i][1]<maxr+1:
        states[i] = (btm,maxr+1)
        changed = True
        print descr(i), states[i]

def bestfrom(p):
  if states[p] is None: return None
  btm = (p>>12)&1
  win = states[p][0]
  remoteness = states[p][1]
  if remoteness <= 0: return None
  return [m for m in moves[p] if states[m] is not None and states[m][0]==win and states[m][1]==remoteness-1][0]

Code to display an example longest White win (it happens to start with a position with Black to move):

p = 3+8*6+64*7+512*7+4096 # or whatever
while p is not None:
  print descr(p)
  p = bestfrom(p)

which, translating from the horrible notation this gives you, goes like this. Start with WQ at d7 and BK at h8, and Black to move. Then:

  1. ... Kg8; 2. Qc6 Kg7; 3. Qa8 Kf7; 4. Qg2 Kf6; 5. Qg8 Kf5; 6. Qf7 Kg5; 7. Qe6 Kf4; 8. Qd5 Kg4; 9. Qe5 Kf3; 10. Qd4 Kg3; 11. Qe4 Kh3; 12. Qf4 Kg2; 13. Qe3 Kh1; 14. Qe2 Kg1; 15. Qe4 Kh2; 16. Qf3 Kg1; 17. Qh3 Kf2; 18. Qg4 Ke3; 19. Qf5 Ke2; 20. Qf4 Ke1; 21. Qd2 Kf1; 22. Qh2 Ke1; 23. Qg2 Kd1; 24. Qf1#

(This seems superficially plausible to me but I haven't attempted to check carefully that neither player can improve on it.)

Code to list all positions with WTM that are not white wins (there are none, so this prints nothing):

for p in range(4096): # 4096 not 8192 because others are BTM
  if states[p] is not None and states[p][0]: continue
  print p, states[p], moves[p], descr(p)
$\endgroup$
  • 3
    $\begingroup$ Could I review your program? @Gareth $\endgroup$ – Areeb Jul 4 '16 at 0:25
  • $\begingroup$ If you just take a setup with the white queen on a1 and the black king in the center and play the game it found, you should be able to convince yourself whether the technique is sound. I doubt it will vary if that position is solvable. Clearly if you can force the king to the 1 row or a column you have a win. $\endgroup$ – Ross Millikan Jul 4 '16 at 1:29
  • $\begingroup$ You say "clearly" but consider the position with BK a8 and WQ b5 and white to move; it may be a win for white (and my program thinks it is) but it's not immediately obvious how to do it. Unfortunately I am at work, my program is at home, and I haven't yet looked at any of the nontrivial output of the program to see (1) whether it makes sense or (2) how it wins any particular nontrivial-looking position. $\endgroup$ – Gareth McCaughan Jul 4 '16 at 10:08
  • $\begingroup$ @Areeb, my program has now had one bug fixed and is in the answer above. $\endgroup$ – Gareth McCaughan Jul 7 '16 at 22:19
  • $\begingroup$ I viewed your longest mating secuence and it's indeed identical after 16 Qf3 to the algorithm I thought. The first part up to 14 Qe2 is easy, but the move 15 Qe4! Shocked me, it gaves a winning system faster than what i conceived, both systems reach the position Q on f3 and king h2(black to move). I can;t review your program for lack of knoledge in programming. So I will accept because the sample secuence it's really cool and indeed works. I appreciate your efforts! $\endgroup$ – Santropedro Jul 9 '16 at 5:17
3
$\begingroup$

White can force mate from any position.

As an example, put the white queen on a1 and the black king on h8, as far away from mate as possible. White plays Qa8+ and black must move to the seventh rank. Say he moves Kg7. White can move Qe8. If black moves to the sixth rank, white can move the queen to the seventh. If black moves to h7, white can move to f8. Black will then be forced to move down the h column and white can follow down the f column. In any case, he can force the black king to the first rank. When he gets black to the first rank, he needs to leave space for black to move between g1 and h1. With black trapped to g1/h1, white can move to e2, then to g4 and (if necessary) h4 to get on the far side of the king. More of the same will force the king back to the first rank, where the queen can chase it to b1 or c1 and deliver mate.

$\endgroup$
  • $\begingroup$ Not clear at all after "with black trapped". $\endgroup$ – Santropedro Jul 4 '16 at 1:56
  • $\begingroup$ @Santropedro: I added more detail in the answer so it would be under the spoiler. $\endgroup$ – Ross Millikan Jul 4 '16 at 2:44
  • $\begingroup$ So it's clear that if you get black to move to the a-file or 1-rank you win. And you can move him along without too much problem. The only remaining question is if he can run interference on your king. Eg can he get himself to an awkward position on d5 and e4? I doubt it, but your proof seems incomplete without it. $\endgroup$ – Dr Xorile Jul 4 '16 at 3:36
  • $\begingroup$ If he is on d5 I can move to b6. Then he has to move to d4 or e5 or something easier. In either case I can keep restricting his freedom, chasing him toward h1. $\endgroup$ – Ross Millikan Jul 4 '16 at 4:05
  • $\begingroup$ I don't understand your solution after taking black king to h1. While pushing the king to the left he goes up, over the white king, and if you want it to go to the a file, you have to accept he will achieve getting to a8-a7 and you are on the same situation as before (simmetrically equivalent) so i don;t see progress. One way to show me your strategy easier will be if you play a game at lichess (free, very easyto register) or any site with me and we setup the position, and play, and I see your algorithm working, please consider this, since there is a point I think you are overlooking. $\endgroup$ – Santropedro Jul 4 '16 at 17:53

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.