16
$\begingroup$

Can you place seven (point-sized) pawns on a $7\times7$ checkerboard, so that

  • every pawn is placed precisely in the middle of one of the little checkerboard squares, and
  • all distances between pairs are different?
$\endgroup$
10
$\begingroup$

Aight, second try. This time was computer generated, so let's see if my code is dummy or what:

Pos{x=0, y=0}, Pos{x=6, y=6}, Pos{x=5, y=5}, Pos{x=1, y=2}, Pos{x=0, y=2}, Pos{x=2, y=6}, Pos{x=3, y=0}

and these are the used distances:

2.0, 5.830951894845301, 7.211102550927978, 7.0710678118654755, 5.385164807134504, 6.324555320336759, 3.0, 2.23606797749979, 6.4031242374328485, 2.8284271247461903, 8.48528137423857, 4.0, 1.0, 5.0, 3.605551275463989, 6.708203932499369, 4.123105625617661, 3.1622776601683795, 4.47213595499958, 1.4142135623730951, 6.082762530298219

For the curious, here is the code (minus syntactic sugar for brevity):

class Pos {
    final int x;
    final int y;
}

class State {
    final Set<Double> usedDistances;
    final Set<Pos> usedCells;
}

void run(String[] args) {
    State initial = new State(new HashSet<>(), new HashSet<>());
    Set<State> visited = new HashSet<>();
    Deque<State> queue = new LinkedList<>();
    queue.add(initial);
    while (!queue.isEmpty()) {
        State state = queue.remove();
        if (!visited.contains(state)) {
            visited.add(state);
            if (isFinal(state)) {
                System.out.println(state);
                return;
            }
            else {
                Set<State> next = nextOf(state);
                queue.addAll(next);
            }
        }
    }
    System.out.println("nothing");
}

private Set<State> nextOf(State state) {
    Set<State> res = new HashSet<>();
    for (int i = 0; i<7; i++) {
        for (int j = 0; j<7; j++) {
            Pos pos = new Pos(i, j);
            if (!state.usedCells.contains(pos)) {
                Set<Double> nextDistances = new HashSet<>(state.usedDistances);
                Set<Pos> nextPos = new HashSet<>(state.usedCells);
                boolean valid = true;
                for (Pos used: state.usedCells) {
                    double distance = computeDistance(pos, used);
                    if (nextDistances.contains(distance)) {
                        valid = false;
                        break;
                    }
                    else {
                        nextDistances.add(distance);
                    }
                }
                if (valid) {
                    nextPos.add(pos);
                    res.add(new State(nextDistances, nextPos));
                }
            }
        }
    }
    return res;
}

Finally, here is a picture of the solution:

       -----------------------------
       | X |   |   | X |   |   |   |
       -----------------------------
       |   |   |   |   |   |   |   |
       -----------------------------
       | X | X |   |   |   |   |   |
       -----------------------------
       |   |   |   |   |   |   |   |
       -----------------------------
       |   |   |   |   |   |   |   |
       -----------------------------
       |   |   |   |   |   | X |   |
       -----------------------------
       |   |   | X |   |   |   | X |
       -----------------------------
$\endgroup$
  • $\begingroup$ The distances seem varied enough to make me think this is correct and not due to precision errors. But I'm happy to consider the option. $\endgroup$ – Diego Martinoia Mar 8 '16 at 17:10
  • $\begingroup$ I confirm, well done. How did you generate it? $\endgroup$ – Angkor Mar 8 '16 at 17:15
  • $\begingroup$ @Angkor Simple DFS: keep track of states you visited already, enqueue all the "next" valid states. Eventually you run out of states or find a final state. Will add the code. $\endgroup$ – Diego Martinoia Mar 8 '16 at 17:16
  • $\begingroup$ The search space seems scary in the beginning, but you are limited by at most 7 assigned, so it's not 2^49 but more like 49! / (7! * 42!) (strings of 7 assigned and 42 unassigned) (+all the partial states, but screw those in the estimate). Shy of 100M, which is doable with some luck (the constraint on distances prune A LOT of states) $\endgroup$ – Diego Martinoia Mar 8 '16 at 17:26
  • 1
    $\begingroup$ @Gamow the picture is a spoiler though $\endgroup$ – Diego Martinoia Mar 11 '16 at 12:11
10
$\begingroup$

Not really an answer but I'd like to add my thought process to this

First I checked: How many possible distances are there really on a 7x7 checkerboard? To do this you can draw lines from (1,1) to (1,7) till (7,7), from (1,1) to (1,6) till (6,6) and so on. This mean $7+6+5+4+3+2 = 27$, However because 3,4,5 is a pythagorean triple it is one less because (1,1) to (4,5) = (1,1) to (6,1). There are 21 connections between 7 points. My intuition therefore says it is very unlikely that there are 21 connections that are all different because there are only 26 possibilities to begin with.

This does tell us that if there is a solution that at least 3 points are in a square along the border. Why? There are 7 distances that go from border to border and only a maximum of 5 are not used of these. The two distances could share a point, therefore at least 3 points are on the border squares

$\endgroup$
  • $\begingroup$ Good call. If my solutions is correct, there are indeed 5 on the border. $\endgroup$ – Diego Martinoia Mar 8 '16 at 17:13
0
$\begingroup$

I would say:

No this isn't possible. You should only have 26 different options of distance between pawns and the total number of relationships to take into account is 5040. Still thinking on it, but if I'm right feel free to tell me.

This is unless:

The board itself isn't square ;)

$\endgroup$
  • 1
    $\begingroup$ The number of relationships is 7 choose 2, which is 21. It is not 7!=5040, which is the number of ways to order seven things. $\endgroup$ – f'' Mar 8 '16 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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