All distances different on a chessboard

Question

Inspired by this Puzzling SE question: All distances different on a chess board.

Introduction

Lets define a sequence \$a(n), n\geqslant 1\$ as how many pawns can you put on a \$n \times n\$ chessboard in such a way that all the distances between two pawns are different.

• Pawns are placed always in the centre of the square.
• The distance is simple Euclidean distance.

Example

\$a(4)=4\$:

1100
0000
0010
0001

Challenge

This is a standard sequence challenge and the default rules apply.

This is also code-golf, so the shortest code per language wins!

Test cases

First 9 terms: 1,2,3,4,5,6,7,7,8.

Some more: A271490.

Trivia/hints

• \$a(n) \leqslant n\$
• \$a(n)\$ is weakly increasing, ie. \$a(n) \leqslant a(n+1)\$

Answer 1

Pyth, 16 bytes

lef{I.aM.cT2y*=U

Try it online!

Uses the standard algorithm: form all sets of points, form all pairs of points in the set, find distances, check for duplicates, find longest set without duplicates, output length.

However, there are some fun tricks to reduce the length. *=U is one I'm proud of.

lef{I.aM.cT2y*=U
               U    From input Q, form list [0..Q-1]
              =     Assign the result back to Q
             *      Take the Cartesian product with Q
                    Now, we have a list of all pairs of points.
                    The naive way would be ^UQ2, one character longer.
            y       Powerset, sorted by length
  f                 Filter the powerset on
        .cT2        Form all pairs (without repetition) of points in the set
     .aM            Map the pairs of points to their euclidean distances.
   {I               Check for duplicates (True if no duplicates)
 e                  Last element, longest remaining subset
l                   Length

Answer 2

Jelly, 18 bytes

Very inefficient, \$n=4\$ is just on the edge of timing out on TIO.

Œc_/€²§QƑ
pµŒPÇƇṪL

Try it online!

Commented:

Œc_/€²§QƑ   -- helper function; verify a set of pawn coordinates is valid
Œc          -- unordered pairs of coordinates
  _/€       -- reduce each pair by subtraction
     ²      -- square all values
      §     -- sum to get the squared euclidean distance between each pair
       QƑ   -- is this invariant under deduplication?

p           -- cartesian product of (implicit) ranges [1..n] and [1..n]
  ŒP        -- the powerset of this (sorted by length)
    ÇƇ      -- filter the coordinate subsets on the helper function
      ṪL    -- get the length of the last subset

Answer 3

Python 3.8 (pre-release), 126 bytes

f=lambda n,i=0,l=[]:i<n*n and max(f(n,i+1,L:=l+[i//n+i%n*1j])-len(l)*len(L)/2+len({abs(p-q)for p in L for q in L}),f(n,i+1,l))

Try it online!

A very slow \$ O(2^{n^2}) \$ solution. Timeout for \$n>4\$.

---

Python 3.8 (pre-release), 130 bytes

f=lambda n,i=0,l=[]:i<n*n and max(len(l)*len(L:=l+[i//n+i%n*1j])/2<len({abs(p-q)for p in L for q in L})and-~f(n,i+1,L),f(n,i+1,l))

Try it online!

A bit faster (though time out for \$n=8\$), only need \$ O(n^{2n}) \$ time to rune.

-3 bytes by Jakque

Answer 4

Ruby, 139 ... 116 bytes

->n{(w=*0...n*n).find{|x|w.combination(x+1).all?{|y|y.combination(2).map{|a,b|(a%n-b%n)**2+(a/n-b/n)**2}.uniq!}}||n}

Try it online!

Should work in theory, times out for n>6.

Answer 5

05AB1E, 19 18 bytes

Lãæʒ.Æ€øÆnODÙQ}éθg

Same exact approach as @ovs' Jelly answer, and it's even slightly slower, since it'll time out for \$n=4\$.

-1 byte thanks to @Adnan.

Try it online.

Explanation:

L              # Push a list in the range [1, (implicit) input]
 ã             # Cartesian power with itself to create all pairs
  æ            # Get the powerset of these coordinates
   ʒ           # Filter this by:
    .Æ         #  Get all pairs of coordinates from the current list
      €        #  Map over the pairs of coordinates:
       ø       #   Zip/transpose; swapping rows/columns
        Æ      #  Reduce each inner-most list by substracting
         n     #  Get the square of each integer
          O    #  Sum each together
               #  Check if all items are unique:
           D   #   Duplicate
            Ù  #   Uniquify the items in this copied list
             Q #   Check if it's still equal to the original list
   }é          # After the filter: sort the remaining lists of coordinates by length
     θ         # Pop and leave the last/longest one
      g        # Pop and push its length
               # (after which this is output implicitly as result)

Answer 6

Python 3, 203 163 bytes

r=range
c=lambda l:len(set(l))==len(l)
f=lambda i:max(bin(j).count("1")for j in r(1<<i*i)if c([abs((a-b)%i*1j+a//i-b//i)for a in r(j)for b in r(a)if j>>a&j>>b&1]))

Try it online!

A simple brute force solution. The integer j is a binary encoded board. Next, all distances for j are calculated. The if-guard j>>a&j>>b&1 checks that both selected squares are in the board j. Instead of for a in r(i*i) we can use for a in r(j), since only values of a, where a bit is set in j at index a, matter. This means that a < j always (for set bits).

Answer 7

JavaScript (ES6),  134 133  130 bytes

Saved 3 bytes thanks to @tsh

f=(n,a=[],i=0)=>-a.some(o=i=>a.some(j=>j>i&&!(o[(q=i%n-j%n)*q+(j-=i-q)*j/n/n]^=1)))||i<n*n&&Math.max(1+f(n,[...a,i],++i),f(n,a,i))

Try it online!

(This is just fast enough for f(8) but may time out from time to time.)

Commented

f = (                       // f is a recursive function taking:
  n,                        //   n   = input
  a = [],                   //   a[] = list of pawn positions
  i = 0                     //   i   = current position (0 ≤ i < n²)
) =>                        //
-a.some(o = i =>            // for each position i in a[]:
  a.some(j =>               //   for each position j in a[]:
    j > i &&                //     test whether j is greater than i
    !(o[                    //     and this is the first time
      (q = i % n - j % n)   //     that the we encounter the
      * q +                 //     squared Euclidean distance between:
      (j -= i - q) * j      //       (i % n, j % n) and
      / n / n               //       (floor(i / n), floor(j / n))
    ] ^= 1)                 //
  )                         //   end of inner some()
)                           // end of outer some()
                            // return -1 if truthy
||                          // otherwise:
i < n * n &&                //   return 0 if i is equal to n²
Math.max(                   //   otherwise, return the maximum of:
  1 + f(n, [...a, i], ++i), //     1 + recursive call with i added to a[]
  f(n, a, i)                //     recursive call with a[] unchanged
                            //     (i is incremented in both cases)
)                           //   end of Math.max()

Answer 8

Charcoal, 72 67 bytes

Ｎθ⊞υＥ²⟦⟧ＦθＦθＦυ«≔⁺§λ⁰Ｅ§λ¹ΣＸＥμ⁻ξ⎇πκι²η¿¬⊙η⊖№ημ⊞υ⟦η⁺§λ¹⟦⟦ικ⟧⟧⟧»Ｉ⌈ＥυＬ⊟ι

Try it online! Link is to verbose version of code. No longer manages to complete n=6 on TIO, but that's code golf for you. Explanation:

Ｎθ

Input n.

⊞υＥ²⟦⟧

Start a breadth-first search with no pawns and no squared distances.

ＦθＦθＦυ«

Loop over all squares and all positions.

≔⁺§λ⁰Ｅ§λ¹ΣＸＥμ⁻ξ⎇πκι²η

Calculate the augmented set of squared distances that result when adding this pawn.

¿¬⊙η⊖№ημ

If they are all unique, then...

⊞υ⟦η⁺§λ¹⟦⟦ικ⟧⟧⟧

... add this with the updated set of pawns to the search list.

»Ｉ⌈ＥυＬ⊟ι

Output the maximum number of pawns found.

Answer 9

R, 112 bytes

Or R>=4.1, 105 bytes by replacing the word function with a \.

function(n){for(i in 0:2^n^2)if(all(table(dist(which(a<-!matrix(i%/%2^(1:n^2-1)%%2,n),T)))<2))T=max(T,sum(a));T}

Try it online!

My question with no R answer? No way!

Outputs n-th term 1-indexed.

Explanation

Straightforward brute-force approach:

• generate all numbers between \$0\$ and \$2^{n^2}\$ and convert to binary of fixed length of \$n^2\$
• reshape to \$n \times n\$ matrix
• get indices of zeros (we have to use ! as which works only for logical input) - two-dimensional with T option
• calculate distances
• are they unique? (all(table(...)<2))
• if so, how many ones did we have and update running max (kept in T)