Queen & "paralyzed" King vs King

Question

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

Answer 1

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)

Answer 2

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.