Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?
share|improve this question
up vote 10 down vote accepted

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 |
       -----------------------------
share|improve this answer
    
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. – Diego Martinoia Mar 8 at 17:10
    
I confirm, well done. How did you generate it? – Angkor Mar 8 at 17:15
    
@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. – Diego Martinoia Mar 8 at 17:16
    
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) – Diego Martinoia Mar 8 at 17:26
1  
@Gamow the picture is a spoiler though – Diego Martinoia Mar 11 at 12:11

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

share|improve this answer
    
Good call. If my solutions is correct, there are indeed 5 on the border. – Diego Martinoia Mar 8 at 17:13

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 ;)

share|improve this answer
1  
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. – f'' Mar 8 at 17:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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