The Toroidal Chessboard!

Question

Inspired by this awesome question, and this old-but-gold question:

What is the minimum number of Chess pieces to dominate(attack all squares) a 8x8 chessboard in shape of a toroid.

How many squares are on the major and minor radius? 16 in both directions? — , Aug 10 '16 at 19:16
It would be nice if this question could be self-contained — ie. include what dominate means without the link. — Shuri2060, Aug 10 '16 at 19:19
While the torus image is very pleasing, the puzzle is far better solved with a regular grid in 2D. Whenever you move "outside" the board on one end, just "enter" it at some height (if horizontal) or width (if vertical) on the other side. Far less mind-bending. — BmyGuest, Aug 10 '16 at 19:57
Reminds me of the hexagonal three-player chessboards that were briefly popular... Not hard to reinvent, once you have the concept. — keshlam, Aug 11 '16 at 03:30

Jonathan Allan · Accepted Answer · 2016-08-10T23:37:41.560

We can do it with

$4$ queens:

Q . . . . . . .
. . . . Q . . .
. . . . . . . .
. . . . . . . .
. . . Q . . . .
. . . . . . . Q
. . . . . . . .
. . . . . . . .

Can we do it with less pieces?

No.
Placing the first piece on the board dominates the cell in which it is placed and the cells it attacks.
Placing a second (third) piece does the same, but only adds to the set of dominated cells those which were not already dominated by the first (first and second).
There are $64$ cells on the board.
A queen dominates the most cells at $28$, next are rooks at $15$ then bishops at $14$, then kings and knights at $9$, and finally pawns at $2$.
So to perform total domination with $3$ pieces would require use of at least $2$ queens (since $28+15+15<64$)
Placing the first queen dominates $28$ cells including at least $2$ cells in each row and $2$ cells in each column.
Placing the second queen can, therefore, only ever hope to add at most $28-8=20$ freshly dominated cells to the set of dominated cells.
So the $3^\text{rd}$ piece would have to be a queen too (since $28+20+15<64$)
We can then check all arrangements of $3$ queens to see that the most cells that they can dominate is $58<64$.

Here is some code to build and check states

(it's set up for knights too, but this was not necessary in the end - see above)

Q = 1
N = 2
VALS = ' QN'
def initBoard():
    return [[0 for c in range(8)] for r in range(8)]
def place(board, piece, r, c):
    board[r][c] = piece
def dominated(board, r, c, justTruth=True):
    if board[r][c]:
        return True
    for d in range(1,8):
        if board[r-d][c] == Q or board[r][c-d] == Q or board[r-d][c-d] == Q or board[(r+d)%8][c-d] == Q:
            return justTruth or 'q'
    for rd, cds in ((-2,(-1, 1)), (-1,(-2, 2)), (1,(-2, 2)), (2,(-1, 1))):
        for cd in cds:
            if board[(r+rd)%8][(c+cd)%8] == N:
                return justTruth or 'n'
    if justTruth:
        return False
    return '.'
def printBoard(board):
    s = ''
    for r in range(8):
        for c in range(8):
            if board[r][c]:
                s += VALS[board[r][c]] + ' '
            else:
                s += dominated(board, r, c, False) + ' '
        s += '\n'
    print(s)

So let's first check my suggestion works, adding one piece at a time...

>>> b = initBoard()
>>> place(b, Q, 0, 0)
>>> printBoard(b)
Q q q q q q q q
q q . . . . . q
q . q . . . q .
q . . q . q . .
q . . . q . . .
q . . q . q . .
q . q . . . q .
q q . . . . . q



place(b, Q, 1, 4)
printBoard(b)



Q q q q q q q q
q q q q Q q q q
q . q q q q q .
q . q q q q q .
q q . . q . . q
q . . q q q . .
q q q . q . q q
q q q . q . q q



place(b, Q, 4, 3)
printBoard(b)



Q q q q q q q q
q q q q Q q q q
q q q q q q q .
q . q q q q q .
q q q Q q q q q
q . q q q q . .
q q q q q q q q
q q q q q . q q



place(b, Q, 5, 7)
printBoard(b)



Q q q q q q q q
q q q q Q q q q
q q q q q q q q
q q q q q q q q
q q q Q q q q q
q q q q q q q Q
q q q q q q q q
q q q q q q q q

Now let's check for possible lesser placements as described

>>> from itertools import combinations
>>> rcs = [(r, c) for r in range(8) for c in range(8)]
>>> m = 0
>>> for locs in combinations(rcs, 3):
...     b = initBoard()
...     for r, c in locs:
...             place(b, Q, r, c)
...     d = sum(dominated(b, r, c) for r in range(8) for c in range(8))
...     if d > m:
...             m = d
...             printBoard(b)
...             print(d)
...             print()
...
Q Q Q q q q q q
q q q q . . . q
q q q q q . q q
q q q q q q q q
q q q . q q q .
q q q q q q q q
q q q q q . q q
q q q q . . . q
54
Q Q q q q q q q
q q q q Q q q q
q q q q q q q q
q q q q q q q .
q q . . q q . q
q q . q q q q .
q q q q q . q q
q q q . q . q q
55
Q Q q q q q q q
q q q q . . q q
q q q q . q q q
q q q q q q q .
q q q Q q q q q
q q q q q q q .
q q q q . q q q
q q q q . . q q
56
Q q q q Q q q q
q q . q q q q q
q q q q q . q q
q q q q q q . q
q Q q q q q q q
q q q q q q . q
q q q q q . q q
q q . q q q q q
58

In fact

There are $832$ possible ways to choose $4$ of the $64$ cells such that placing queens in those cells would totally dominate the torus.
If we reduce this to the symmetry of the torus (we can shift rows or columns by any number and we can rotate the board in quarters) that yields $70$ possible arrangements.

Added code, this could be used to brute force the solution once extended to include other pieces — Jonathan Allan, Aug 10 '16 at 20:59
Awesome. had to check you code again and again(on my system)... — ABcDexter, Aug 12 '16 at 06:13

score 0 · Answer 2 · answered Aug 10 '16 at 19:39

0

Two bishops?

Explanation:

If you put on bishop on white and one on black, they should be able to spiral throughout the torus and eventually get every space.

answered Aug 10 '16 at 19:39

Mat

117
2

1

This was my initial thought but I believe that the diagonals wrap. If you put a piece at A1 diagonal to H8 then wraps back to A1. Same with the other diagonals B1>H7>A8>B1 and around we go. – gtwebb Aug 10 '16 at 19:47
1

Nope, doesn't work. (Gray is the actual board, the others are just for visualization.) – Deusovi Aug 10 '16 at 19:53

score 0 · Answer 3 · edited Apr 13 '17 at 12:58

INCORRECT ANSWER

I believe the answer is

5, the same as a regular chess board, see here for regular solution which has also been copied below

Because

Basic trial and error seemed to suggest 4 was not even close to enough, Q1 can cover 22 squares (7 each row, column, diagonal plus standing cell), Q2 can cover 16 squares (5 each row, column, diagonal plus standing cell, since Q1 covers 2 in each of the rows, columns, diagonals), This leaves 2 queens to cover 26 cells and each queen can cover less then the last due to already covered cells so I don't think this is possible. (Incorrect as I started in the corner and was only looking at 1 diagonal)

Below

-----------------------------------------------------------------------

Yes. The minimum number of pieces required is 5.

5 queens can be places such that they cover every space on the board, as in the following example:

There are 12 such arrangements, along with rotation and reflection of each of them.
Edit: The above proves that 5 queens is enough, but it doesn't prove that 4 queens isn't enough. According to this MathOverflow question and its answers, there is no easy logical or mathematical proof, but it has been proven by completely evaluating all possible arrangements of queens on a board. See this list to see the minimum number of required queens for any square board from $1\times1$ to $18\times18$.

lois6b · Answer 4 · 2016-08-10T19:38:24.273

-1

Solution:

You need 2 queens.

because:

The red queen covers horizontal and vertical. plus all the black tiles in diagonal.
The other queen covers all the white ones in diagonal.
Since all sides are together, the diagonal are infinite

edited Aug 10 '16 at 19:38

answered Aug 10 '16 at 19:22

lois6b

3,346
21
41

1

Nope, doesn't work. (Gray is the actual board, the others are just for visualization.) – Deusovi Aug 10 '16 at 19:52
This does not work link. Oh, @Deusovi again! :c( – BmyGuest Aug 10 '16 at 19:55
oh ... btw, how did you do the image, @deusovi? – lois6b Aug 10 '16 at 20:02
@lois6b: Google Sheets. – Deusovi Aug 10 '16 at 20:42

The Toroidal Chessboard!

4 Answers4