10
$\begingroup$

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. Toroidal chessboard

image courtesy: Tex.stackexchange.com

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ How many squares are on the major and minor radius? 16 in both directions? $\endgroup$
    – user20
    Aug 10, 2016 at 19:16
  • $\begingroup$ exactly my thoughts @Emrakul $\endgroup$
    – lois6b
    Aug 10, 2016 at 19:16
  • $\begingroup$ @Emrakul Added that part :) $\endgroup$
    – ABcDexter
    Aug 10, 2016 at 19:17
  • 4
    $\begingroup$ It would be nice if this question could be self-contained — ie. include what dominate means without the link. $\endgroup$
    – Shuri2060
    Aug 10, 2016 at 19:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – BmyGuest
    Aug 10, 2016 at 19:57

4 Answers 4

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Will add some code for double checking it shortly... $\endgroup$
    – Jonathan Allan
    Aug 10, 2016 at 20:46
  • 1
    $\begingroup$ Added code, this could be used to brute force the solution once extended to include other pieces $\endgroup$
    – Jonathan Allan
    Aug 10, 2016 at 20:59
  • 1
    $\begingroup$ Update: No lesser possible. $\endgroup$
    – Jonathan Allan
    Aug 10, 2016 at 22:59
  • $\begingroup$ Awesome. had to check you code again and again(on my system)... $\endgroup$
    – ABcDexter
    Aug 12, 2016 at 6:13
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – gtwebb
    Aug 10, 2016 at 19:47
  • 1
    $\begingroup$ Nope, doesn't work. (Gray is the actual board, the others are just for visualization.) $\endgroup$
    – Deusovi ♦
    Aug 10, 2016 at 19:53
0
$\begingroup$

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:
It only takes 5 queens to "cover" a full 8x8 chessboard. color coded version
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$.

Improve this answer
$\endgroup$
-1
$\begingroup$

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

enter image description here

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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