Queens on a Board with Two Players

Question

Alice and Bob decide to play a game. Alice goes first. They will take turns placing queens on a chessboard such that the queen is not threatened by any other queen on the board. Both players play optimally.

Winning Condition: Be the last person to place a queen.

Who Wins?

---

After the first game, they play again. Alice again goes first and uses white pieces and Bob uses black pieces. This time, queens are allowed to be threatened by others of the same color.

Winning Condition: Be the last person to place a queen.

Who Wins?

---

Bonus Round:

They play a third game with the same setup and rules as the second game with one addition: If someone is unable to play, their turn is skipped. I.E., if every open space on the board is threatened by a white piece, then Bob cannot place any more black pieces but Alice my continue to place her white pieces. (I expect that the optimal strategy, therefore, would be similar to the second game where you completely block someone out and then fill the rest of the safe spaces with your own pieces. However, that may not be the case.) Play continues until neither person is able to place any more pieces.

What's the minimum number of pieces on the board when the game is over?

What's the maximum number of pieces?

---

Clarifications:

You can threaten every space on a board with five queens. Here is one such configuration:

In the first game, they will both be using the same color queens for simplicity. No queen is allowed to threaten any other queen. Therefore, they're going to place at least 5 queens since that's the minimum required to threaten every space. Here's an example of a game. A is Alice and B is Bob. The number indicates which turn it was for them. I.E., A1 is Alice's first turn and B1 is Bob's first turn. In this game, Alice won because A3 threatened the last of the unthreatened spaces and Bob was unable to play.

In the second game, they use queens of different colors. Each player can play anywhere not threatened by the other player. It is allowed to play somewhere threatened by your own pieces, though. Here's an example game. Again, Alice one. This may end up being the same case as the first game except that someone can "skip" a turn by playing somewhere that doesn't threaten any new cells.

In the bonus game, I think that the "max pieces" question will be the trickiest. It seems like the most important thing is to threaten the most spaces possible so you can go back and fill the board at the end. However, you also have to keep them from threatening the same spaces. Here's an example game. Alice was able to place 6 more pieces after locking out Bob show she won 11 - 5. (I had to switch to hexadecimal so AB is Alice's 11th turn.)

Disclaimer: I am not super-good at chess. I used to play my uncle a lot. I don't know if this question is provably solvable. It was a curiosity that occurred to me and I'm trying to translate from my ignorance into an understandable puzzle.

Answer 1

Partial solution:

For the first question, the answer is that Alice can win the game in 7 moves by playing D4 on the first move. We can show this by using brute force:

#include <stdio.h>
#include <string.h>

int board[8][8]; //1 for the squares occupied or being attacked by a queen,
             //0 for 'free' squares

void clear_board() {

    int x, y;
    for (x=0; x<8; x++) {
        for (y=0; y<8; y++) {
            board[x][y] = 0;
        }
    }
}

void place_queen(int x, int y) {

    int i;
    for (i=0; i<8; i++) {
        board[x][i] = 1;
    }
    for (i=0; i<8; i++) {
        board[i][y] = 1;
    }
    for (i=0; i<8; i++) {
        if (x-y+i >= 0) {
            board[x-y+i][i] = 1;
        }
    }
    for (i=0; i<8; i++) {
        if (x+y-i >= 0) {
            board[x+y-i][i] = 1;
        }
    }
}

//returns 1 iff all squares are occupied or being threatened
int is_dominated() {

    int x, y;
    for (x=0; x<8; x++) {
        for (y=0; y<8; y++) {

            if (!board[x][y]) {
                return 0;
            }
        }
    }
    return 1;
}

int main(int argc, char *argv[]) {

    char strategy_level_1[200000];
    strategy_level_1[0] = '\0';
    char strategy_level_3[200000];
    strategy_level_3[0] = '\0';
    char strategy_level_5[200000];
    strategy_level_5[0] = '\0';
    char strategy_level_7[200000];
    strategy_level_7[0] = '\0';

    int i1, i2, i3, i4, i5, i6, i7;
    for (i1=0; i1<64; i1++) {

        //comment the following line if you want the whole calculation
        i1=27;

        int x1 = i1%8;
        int y1 = i1/8;

        int alice_wins_1 = 1; //will stay 1 by the end of the loop below if and only if Alice has a winning
                          //strategy that starts with (x1, y1)

        for (i2=0; i2<64; i2++) {

            int x2 = i2%8;
            int y2 = i2/8;

            clear_board();
            place_queen(x1, y1);
            if (!board[x2][y2]) {

                int bob_survives_2 = 1; //will stay 1 by the end of the loop below if and only if Bob has a
                                    //non-losing strategy if the moves so far are (x1, y1), (x2, y2)

                for (i3=0; i3<64; i3++) {

                    int x3 = i3%8;
                    int y3 = i3/8;

                    clear_board();
                    place_queen(x1, y1);
                    place_queen(x2, y2);
                    if (!board[x3][y3]) { 

                        int alice_wins_3 = 1; //will stay 1 by the end of the loop below if and only if Alice has a winning
                                          //strategy if the moves so far are (x1, y1), (x2, y2), (x3, y3)

                        for (i4=0; i4<64; i4++) {

                            int x4 = i4%8;
                            int y4 = i4/8;

                            clear_board();
                            place_queen(x1, y1);
                            place_queen(x2, y2);
                            place_queen(x3, y3);
                            if (!board[x4][y4]) {

                                int bob_survives_4 = 1; //etc.

                                for (i5=0; i5<64; i5++) {

                                    int x5 = i5%8;
                                    int y5 = i5/8;

                                    clear_board();
                                    place_queen(x1, y1);
                                    place_queen(x2, y2);
                                    place_queen(x3, y3);
                                    place_queen(x4, y4);
                                    if (!board[x5][y5]) {

                                        int alice_wins_5 = 1;

                                        for (i6=0; i6<64; i6++) {

                                            int x6 = i6%8;
                                            int y6 = i6/8;

                                            clear_board();
                                            place_queen(x1, y1);
                                            place_queen(x2, y2);
                                            place_queen(x3, y3);
                                            place_queen(x4, y4);
                                            place_queen(x5, y5);
                                            if (!board[x6][y6]) {

                                                int bob_survives_6 = 1;

                                                for (i7=0; i7<64; i7++) {

                                                    int x7 = i7%8;
                                                    int y7 = i7/8;

                                                    clear_board();
                                                    place_queen(x1, y1);
                                                    place_queen(x2, y2);
                                                    place_queen(x3, y3);
                                                    place_queen(x4, y4);
                                                    place_queen(x5, y5);
                                                    place_queen(x6, y6);
                                                    if (!board[x7][y7]) {

                                                        clear_board();
                                                        place_queen(x1, y1);
                                                        place_queen(x2, y2);
                                                        place_queen(x3, y3);
                                                        place_queen(x4, y4);
                                                        place_queen(x5, y5);
                                                        place_queen(x6, y6);
                                                        place_queen(x7, y7);
                                                        if (is_dominated()) {

                                                            bob_survives_6 = 0;
                                                            char strategy_line[128];
                                                            sprintf(strategy_line, "Moves: (%d, %d), (%d, %d), (%d, %d), (%d, %d), (%d, %d), (%d, %d), (%d, %d). Alice wins.\n", x1, y1, x2, y2, x3, y3, x4, y4, x5, y5, x6, y6, x7, y7);
                                                            sprintf(strategy_level_7, "%s%s", strategy_level_7, strategy_line);
                                                            break;
                                                        }
                                                    }
                                                }
                                                if (bob_survives_6) {
                                                    alice_wins_5 = 0;
                                                    strategy_level_7[0] = '\0';
                                                    break;
                                                }
                                            }
                                        }
                                        if (alice_wins_5) {
                                            bob_survives_4 = 0;
                                            sprintf(strategy_level_5, "%s%s", strategy_level_5, strategy_level_7);
                                            strategy_level_7[0] = '\0';
                                            break;
                                        }
                                    }
                                }
                                if (bob_survives_4) {
                                    alice_wins_3 = 0;
                                    strategy_level_5[0] = '\0';
                                    break;
                                }
                            }
                        }
                        if (alice_wins_3) {
                            bob_survives_2 = 0;
                            sprintf(strategy_level_3, "%s%s", strategy_level_3, strategy_level_5);
                            strategy_level_5[0] = '\0';
                            break;
                        }
                    }
                }
                if (bob_survives_2) {
                    alice_wins_1 = 0;
                    strategy_level_3[0] = '\0';
                    break;
                }
            }
        }
        if (alice_wins_1) {

            sprintf(strategy_level_1, "%s%s", strategy_level_1, strategy_level_3);
            strategy_level_3[0] = '\0';
            printf("Alice always wins by playing (%d, %d) on her first move. Strategy:\n", x1, y1);
            printf("%s", strategy_level_1);

            return 0;
        }
        else {
            printf("Bob can survive 7 steps if Alice plays (%d, %d) on her first move\n", x1, y1);
        }
    }

    return 0;
}

It is not a very long calculation. However, there is no guarantee that this program works correctly, so you might want to take a look at the generated strategy guide and see if you can beat Alice! The moves in the strategy are expressed in zero-based coordinates, e. g. (0, 5) means A6.