13
\$\begingroup\$

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 challenge and the default rules apply.

This is also , 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)\$
\$\endgroup\$
12
  • 2
    \$\begingroup\$ I don't think hint #3 is correct. The total number of distances between n-1 points is (n-1)-choose-2 whereas the number of distinct distances available on a nxn square grid is (n+1)-choose-2 - 1 - number-of-relevant-Pythagorean-triples-and-other-duplicates. As the fraction of such triples will on average grow whereas the relative slack between the relevant binomial coefficients tends to 0 a(n) cannot keep above n-1 forever. \$\endgroup\$
    – loopy walt
    Nov 30 '21 at 9:39
  • 2
    \$\begingroup\$ \$ a(n)\ge n-1\$ will not hold for larger \$n\$. Consider \$n=100\$, there are only 3664 different distance. (This can be verified by simple len(set(p*p+q*q for p in range(100) for q in range(100)))) And \$ 3664<C(87, 2) \$. So \$a(100)<87\$. \$\endgroup\$
    – tsh
    Nov 30 '21 at 9:42
  • 1
    \$\begingroup\$ Provided that my code is correct, we have a(10)=9. \$\endgroup\$
    – Arnauld
    Nov 30 '21 at 11:56
  • 1
    \$\begingroup\$ Just a note, this is a code-golf challenge, not extend-the-sequence challenge :) Although I had that also in mind ;) \$\endgroup\$
    – pajonk
    Nov 30 '21 at 12:01
  • 6
    \$\begingroup\$ This is A271490 on the OEIS. \$\endgroup\$ Nov 30 '21 at 13:41
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ -3 bytes by replacing set( ... ) by { ... } \$\endgroup\$
    – Jakque
    Dec 1 '21 at 1:25
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Ahh, right! I completely forgot that existed hahaha, very nice. I think the 2 from 2.Æ can be omitted, as that is the default when only a list is supplied. \$\endgroup\$
    – Adnan
    Nov 30 '21 at 14:47
  • \$\begingroup\$ @Adnan Oh, I didn't knew that builtin used a default 2 as well. Thanks for -1! :) \$\endgroup\$ Nov 30 '21 at 15:30
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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()
\$\endgroup\$
1
  • \$\begingroup\$ -3 bytes: o[(t=i%n-j%n)*t+((i-j-t)/n)**2] \$\endgroup\$
    – tsh
    Dec 1 '21 at 5:43
1
\$\begingroup\$

Charcoal, 72 67 bytes

Nθ⊞υE²⟦⟧FθFθFυ«≔⁺§λ⁰E§λ¹ΣXEμ⁻ξ⎇πκι²η¿¬⊙η⊖№ημ⊞υ⟦η⁺§λ¹⟦⟦ικ⟧⟧⟧»I⌈EυL⊟ι

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:

Nθ

Input n.

⊞υE²⟦⟧

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

FθFθFυ«

Loop over all squares and all positions.

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

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.

»I⌈EυL⊟ι

Output the maximum number of pawns found.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$

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.