8 kings

Computer Science Level 5

In chess, a king can move one square in any direction (horizontally, vertically, or diagonally), as shown in the picture below.

How many ways are there to put 8 kings in an 8 × 8 8×8 checkerboard such that no two kings can place each other in check in one move?

Computer solutions are allowed for this problem.


The answer is 119138166.

Alice Smith by Alice Smith , 20, China

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Arthur Komatsu
Sep 29, 2018

A simple solution is to just bruteforce the answer using the backtracking technique. The following C++ code shows an implementation to approach this problem. My computer ran the code in 11s. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
#include<bits/stdc++.h>
using namespace std;

const int MAX = 8;
int ans = 0;
bool grid[MAX][MAX];

bool ok(int i, int j) {
    return i >= 0 && i < MAX && j >= 0 && j < MAX;
}

void backtrack(int idx, int cnt) {
    if(cnt == MAX) {
        ans++;
        return;
    }

    if(idx == MAX * MAX)
        return;

    int i = idx / MAX, j = idx % MAX;

    //dont choose any king
    backtrack(idx + 1, cnt);

    //check if there are any surrounding kings
    if(ok(i-1, j)   && grid[i-1][j])   return;
    if(ok(i+1, j)   && grid[i+1][j])   return;
    if(ok(i, j-1)   && grid[i][j-1])   return;
    if(ok(i, j+1)   && grid[i][j+1])   return;
    if(ok(i-1, j-1) && grid[i-1][j-1]) return;
    if(ok(i-1, j+1) && grid[i-1][j+1]) return;
    if(ok(i+1, j-1) && grid[i+1][j-1]) return;
    if(ok(i+1, j+1) && grid[i+1][j+1]) return;

    //choose the king at position idx
    grid[i][j] = true;
    backtrack(idx + 1, cnt + 1);
    grid[i][j] = false;
}

int main() {
    memset(grid, 0, sizeof grid);
    backtrack(0, 0);
    cout << ans << endl;
    return 0;
}

2 Helpful 1 Interesting 0 Brilliant 0 Confused

I though this problem can be solved without coding. We can always solve these questions by coding. Just like eight queens problem. Trying out all options.

Srikanth Tupurani - 2 years, 8 months ago
Jon Haussmann
Sep 22, 2018

The oeis gives an answer of 119138166. I do not see a tractable way of solving this problem.

1 Helpful 0 Interesting 0 Brilliant 0 Confused

Same. I found the Number of ways to place n nonattacking kings on an n X n board for n=1,2,3 I gave up on 4. Hoping it would be enough I tried using the search "1,0,8 king" and the relevant sequence came up.

Jeremy Galvagni - 2 years, 8 months ago

I don't think that the question is clearly phrased - IMO "no two kings can attack each other in one move" fits better a model where each king makes one move and so they have to be separated by two squares (if by "attack" you mean "occupy the same square") or three squares (if by "attack" you mean "be within one square of each other"). I would have preferred this to be stated as "no two kings are attacking each other" or "placing each other in check" without any reference to moves.

John Sergeant - 2 years, 8 months ago

Log in to reply

Absolutely. The problem is phrased wrongly. Afterwards it was changed to "Can not give each other check in one move", which is worse when the original intend was to say that the kings simply aren't allowed to stand next to each other. With the current formulation of the problem the answer should be 37760.

Carlo Wood - 2 years, 7 months ago

Since this is a computer science problem, clearly a computational answer is key. Here is a slow and inefficient (but clear to follow, I hope) Python3 program to do so. This will doubtless trigger a "rubbish coding" flaming ;-)

perm_ct=0

def place king(kingCount, nextSquare, board): global perm ct 

if (kingCount == 8):
    perm_ct += 1
    print("#", perm_ct, " (", "".join(board), ")")
    return

while (nextSquare < 64):
    row = nextSquare // 8
    col = nextSquare % 8

    minX = max(col - 1, 0)
    minY = max(row - 1, 0)
    maxX = min(col + 1, 7)

    y = minY
    while (y <= row):
        x = minX
        while (x <= maxX):
            ind = y * 8 + x
            if (ind >= nextSquare):
                # Ok - we can place king
                board[ind] = "k"
                place_king(kingCount+1, nextSquare + 1, board)
                board[ind] = " "
                break
            elif (board[ind] == "k"):
                # We cannot place king here
                y = (row + 1)
                break
            else:
                x += 1

        y += 1

    # Continue to next square
    nextSquare += 1

place king(0, 0, list(" " * 64)) print("Permutations = ", perm ct)

John Sergeant - 2 years, 8 months ago
Carlo Wood
Nov 8, 2018

Sorry, but the formulation of this problem is (still) seriously wrong. It states "no two kings can give eachother check in one move". That means that they are TWO spaces apart (there is two spaces BETWEEN the kings; for example, one king is on c4 and another on f4, with empty squares d4 and e4 in between). If a king is on c4 and another on e4, with only one square in between, then in one move (Kc4-d4) the king on c4 can give "check".

The series on oeis unrelated, because that simply talks about non-attacking kings; aka kings that do not stand immediately next to eachother.

I wrote a program to solve this - and I had a variable to change the required distance between the kings, so I tried the correct answer first: 37760 ways. Then I tried the number of ways with only one square in between (because the original formulation was unclear at best; it was changed later on).

You can find my program here . Change line 41 to 1 to get 119138166 (which takes half a second on my PC).

0 Helpful 0 Interesting 0 Brilliant 0 Confused

2 pending reports

Vote up reports you agree with

×

Problem Loading...

Note Loading...

Set Loading...