Greedy queens sequence

Question

Challenge

Implement the "greedy queens" sequence (OEIS: A065188).

Details

Taken from the OEIS page.

This permutation [of natural numbers] is produced by a simple greedy algorithm: starting from the top left corner, walk along each successive antidiagonal of an infinite chessboard and place a queen in the first available position where it is not threatened by any of the existing queens. In other words, this permutation satisfies the condition that \$p(i+d) \neq p(i) \pm d\$ for all \$i\$ and \$d \geq 1\$.

\$p(n) = k\$ means that a queen appears in column \$n\$ in row \$k\$.

Visualisation

+------------------------
| Q x x x x x x x x x ...
| x x x Q x x x x x x ...
| x Q x x x x x x x x ...
| x x x x Q x x x x x ...
| x x Q x x x x x x x ...
| x x x x x x x x x Q ...
| x x x x x x x x x x ...
| x x x x x x x x x x ...
| x x x x x Q x x x x ...
| ...

Rules

Standard sequence rules apply, so you can:

• Take an index \$n\$ and output the \$n^{th}\$ term, either 0 or 1 indexing.
• Take a positive integer \$n\$ and output the first \$n\$ terms.
• Output whole sequence as an infinite list.

This is code-golf, so shortest answer (per language) wins!

Test cases

First 70 terms:

1, 3, 5, 2, 4, 9, 11, 13, 15, 6, 8, 19, 7, 22, 10, 25, 27, 29, 31, 12, 14, 35, 37, 39, 41, 16, 18, 45, 17, 48, 20, 51, 53, 21, 56, 58, 60, 23, 63, 24, 66, 28, 26, 70, 72, 74, 76, 78, 30, 32, 82, 84, 86, 33, 89, 34, 92, 38, 36, 96, 98, 100, 102, 40, 105, 107, 42, 110, 43, 113

(See also: https://oeis.org/A065188/b065188.txt)

Answer 1

APL (Dyalog Unicode), 38 bytes

1+{⍵,⊃⍸|⊃×/×(⌽⍳≢⍵)(⊢×+×-)⍵-⊂⍳3×≢⍵}⍣⎕⊢⍬

Try it online!

Kinda port of tsh's JS and Python answers. They actually need some explanation of why it works, rather than how.

Instead of going through antidiagonals, this solution simply goes through the columns and places a queen on the smallest available row number (testing up to 3×(current column number-1)).

Why it works

The first question is why generating by column works.

Claim: If the \$n\$-th column has its queen on the \$k\$-th row by generating by antidiagonals, it does so by generating by columns.

Proof: The premise means that all cells at \$(x,y)\$ (column, row) where \$x+y < n+k\$ or \$x+y = n+k \;\wedge\; x < n \$ are either occupied by a queen or attacked by an existing queen. Then, any queen placed up to the \$n-1\$-th column cannot attack \$(n,k)\$ since \$(n,k)\$ is strictly above the rightward attack vector of all available cells up to \$n-1\$-th column. Therefore, \$(n,k)\$ is guaranteed to be available when \$n-1\$ columns are filled, and therefore a queen is placed at that precise position. \${\blacksquare}\$

Now, let's dig into the magic formula (u-=v)**3-u*m*m in the JS answer. The entire a.every(...) part can be ungolfed into a.every((u,i)=>(u-v)*(u-v+n-1-i)*(u-v-n+1+i)). 1+i part is induced by 0-indexing of JS, so let's adapt it to 1-indexing instead.

Claim: Given the current sequence \$a=(a_1,a_2,\cdots,a_{n-1})\$, \$a_n\$ is determined as the smallest integer \$k\$ that satisfies \$\forall i, (a_i-k)(a_i-k+n-i)(a_i-k-n+i) \ne 0\$, i.e. \$(a_i-k)^3 - (a_i-k)(n-i)^2 \ne 0\$.

Proof: Since the column numbers are all distinct, it suffices to check the horizontal and two diagonal directions. The queen to place is at \$(n,k)\$ (again, column then row) and the queens already placed are at \$(i, a_i)\$.

• Horizontal: row numbers should be distinct. \$a_i \ne k\$; \$a_i - k \ne 0\$
• Main diagonal: the difference between the row and column should be distinct. \$a_i-i \ne k-n\$; \$a_i-k+n-i \ne 0\$
• Antidiagonal: the sum of the row and column should be distinct. \$a_i+i \ne k+n\$; \$a_i-k-n+i \ne 0\$

Take the product of the three to get the inequality we want. \${\blacksquare}\$

Finally, I'm using 3(n-1) as the search limit, instead of searching towards infinity. That is simply because each queen in the previous columns can attack at most 3 cells on the current column, and there are only n-1 queens placed so far, and (1,1) can attack at most two. So at most 3n-3-1 cells can be attacked in total.

The code

1+{⍵,⊃⍸|⊃×/×(⌽⍳≢⍵)(⊢×+×-)⍵-⊂⍳3×≢⍵}⍣⎕⊢⍬
1+{...}⍣⎕⊢⍬    Given input n, generate n terms
               (1+ is to compensate the first term being 0
                which is the result for empty list)
⍳3×≢⍵    Candidate row numbers
⍵-⊂      a_i - k
(⌽⍳≢⍵)   n - i
(⊢×+×-)  (a_i-k) × ((a_i-k) + (n-i)) × ((a_i-k) - (n-i))
|⊃×/×    Test for each row number that all values are nonzero
⍵,⊃⍸     Take the first nonzero index and append to ⍵

Answer 2

JavaScript (Node.js), 76 bytes

f=n=>a=n?[...f(--n),(g=v=>a.every(u=>(u-=v)**3-u*m*m--,m=n)?v:g(v+1))(1)]:[]

Try it online!

Answer 3

Jelly, 19 bytes

Ṁ×3Rḟḟ+;_ɗJ$Ṃ;
1Ç¡Ḣ

Try it online!

A full program taking a zero-indexed n as the argument and printing the relevant term.

Here’s the first twenty terms with a slightly modified pair of links that can be passed an argument from within (rather than always using the command line argument).

Explanation

Helper link - extend sequence z

Ṁ              | Max
 ×3            | Times 3
   R           | Range (1..this)
    ḟ          | Filter out existing sequence members z
     ḟ     $   | Filter out values guven by the following applied to the current sequence:
      +;_ɗJ    | - z plus indices of z concatenated to z minus indicies of z
            Ṃ  | Min
             ; | Concatenate existing sequence z

Main link

1Ç¡  | Starting with 1, call the helper link the number of times indicated by the argument
   Ḣ | Head

Answer 4

JavaScript (ES6),  58  55 bytes

Returns the \$n\$^th term of the sequence, 0-indexed.

f=(n,x=0,y=1)=>n-x?f(n,++x*x/(d=y-f(n-x))^d?x:!++y,y):y

Try it online!

Because of the nested recursion, this is slow as hell for \$n>9\$. We can speed it up drastically by adding a cache (66 bytes).

How?

Given a candidate value \$y>0\$ for a queen at column \$x>0\$, we compute the difference \$d\$ between \$y\$ and each previous value in the sequence.

The way the sequence is built, the queens are already guaranteed to be on different columns. But we additionally want:

• \$d\neq 0\$, meaning that the queens are on different rows.
• \$|d|\neq |x|\$, meaning that the queens are not on the same diagonal or anti-diagonal.

The second condition can also be written as \$d^2\neq x^2\$. If \$d\neq 0\$, it can be further modified into \$x^2/d\neq d\$.

In the JS code, we actually use a XOR:

x * x / d ^ d

The decimal part of the division is lost in the process. This is fine because the integer part of \$x^2/d\$ is guaranteed to be different from \$d\$ whenever we have \$x\neq d,\:d\neq 0\$.

If \$d=0\$, the above expression is Infinity ^ 0, which evaluates to \$0\$, forcing the solution to be rejected as expected. So we don't need to test \$d=0\$ explicitly and this works for all cases.

Commented

f = (                // f is a recursive function taking:
  n,                 //   n = input
  x = 0,             //   x = counter to test the solution against
                     //       all previous terms
  y = 1              //   y = current solution for a(n)
) =>                 //
  n - x ?            // if x is not equal to n:
    f(               //   do a recursive call:
      n,             //     pass n unchanged
      ++x * x /      //     increment x
      ( d =          //     compute:
        y - f(n - x) //       d = y - f(n - x)
      ) ^ d ?        //     if int(x²/d) is not equal to int(d):
        x            //       leave x unchanged
      :              //     else:
        !++y,        //       increment y and reset x to 0
      y              //     pass y
    )                //   end of recursive call
  :                  // else:
    y                //   success: return y

Answer 5

APL (Dyalog Unicode), 64 bytes

{a←⍬⋄⍵↑1+-/¨a[⍋⌽¨a]⊣{a,←1↑(⍸∘.≥⍨w)~a∘.+(¯1+⍳3 2)∘.×w←⍳3×⍵}¨⍳3×⍵}

Try it online!

tsh's arithmetic formula looks quite nice, I'll try to incorporate that in this answer later.

How it works

In this code, each cell is labeled as (antidiagonal number, horizontal coordinate) so that the antidiagonals are generated and tested in a horizontal fashion (which suits well to APL primitives).

(1,1) (2,2) (3,3) (4,4)
(2,1) (3,2) (4,3)
(3,1) (4,2)
(4,1)
...to...
(1,1)
(2,1) (2,2)
(3,1) (3,2) (3,3)
(4,1) (4,2) (4,3) (4,4)

Then, instead of accumulating "until we have all coordinates for columns 1..n", it simply collects until 3n columns are available, and at k-th iteration, first 3k antidiagonals are tested for the new point to add to a.

In this new coordinate system, the Queen's attack vectors are signified with (1,0) (S), (2,1) (SE), (1,1) (E), and (0,1) (NE). NE is needed to prevent taking another coordinate from the same antidiagonal. I add (0,0) (staying still) and (2,0) (S twice) for the sake of golfiness, so that all the vectors are easily generated as ¯1+⍳3 2.

When the accumulation ends, a is sorted by the column number, and row numbers are evaluated and the first n terms are extracted from that.

Answer 6

Python 3, 68 bytes

f=lambda n,i=1:i*all(n-m!=abs(i-f(m))>0for m in range(n))or f(n,i+1)

Try it online!

Answer 7

R >= 4.1, 68 bytes

\(n)Reduce(\(x,y)c(setdiff(1:(3*y),c(x,x+(a=seq(x)),x-a))[1],x),1:n)

Try it online!

A function taking an integer n and returning the sequence of the first n terms in reverse order.

Answer 8

Perl 5, 103 bytes

$s{$i}=!grep{$t=$_;grep$s{$i-$_*$t},999..1001}1..$i++/1e3and say$r=$i%1e3and$i-=$r-1e3or redo for 1..$_

Try it online!

Answer 9

Stax, 22 bytes

╙½#≡]☺è60S|f♣V♦i+é(ç░m

Run and debug it

Runs as an infinite loop producing output. It's very brute-force.

Answer 10

Jelly, 17 bytes

+;_ɗJ;⁸1ḟ1#;
1Ç¡Ḣ

A full program that accepts a non-negative integer, \$n\$, and prints the sequence element at that (0-indexed) index.

Try it online!

How?

Keeps the natural numbers (i.e. 1-indexed row indices) in a list (initially [1] (well, 1 but Jelly :D)) and repeatedly finds the first row in which a queen may be placed in the next column by counting up from 1 until a number is reached that is not on an any, thus far, occupied row, leading diagonal, or trailing diagonal.

+;_ɗJ;⁸1ḟ1#; - Link 1, prefix with next element: list (current elements in reverse), E
    J        - range of length -> [1,2,...,length(E)]
   ɗ         - last three links as a dyad - f(E, J(E)):
+            -   add (vectorises) -> occupied trailing diagonal row indices
  _          -   subtract (vectorises) -> occupied leading diagonal row indices
 ;           -   concatenate these together
     ;⁸      - concatenate E
       1 1#  - start with 1 and count up, collecting the first 1 that are truthy under:
        ḟ    -   filter discard -> singleton list containing the next available row index
           ; - concatenate E -> a new, slightly longer, list of elements in reverse

1Ç¡Ḣ - Main Link: non-negative integer, n (0-indexed)
1    - start with 1
 Ç¡  - repeat Link 1 n times
   Ḣ - head of the resulting list

Answer 11

Charcoal, 30 bytes

ＦＮ«≔¹θＷ⊙υ№×Ｅ³⊖ν⁻ιμ⁻θλ≦⊕θ⊞υθ»Ｉυ

Try it online! Link is to verbose version of code. Outputs the first n terms. Explanation:

ＦＮ«

Loop n times.

≔¹θ

Start by trying to place the queen in the first row.

Ｗ⊙υ№×Ｅ³⊖ν⁻ιμ⁻θλ

For each previously placed queen, check whether its row offset equals its column offset multiplied by any one of -1, 0 and 1.

≦⊕θ

If any queen is in the same row or diagonal then try the next row.

⊞υθ

Push the newly placed queen to the predefined empty list.

»Ｉυ

Print the list of queens.

Answer 12

APL(Dyalog Unicode), ¹⁰⁴ 70 bytes ^SBCS

{⊢/↑⍸⍉{1@(⊂⊃{⍵[⍋⊢/↑⍵]}⍸~⊃∨/(≢⍵)∘{⊃∘.(=∨0=×)/|⍵-⊂⍳⍺}¨⍸⍵)⊢⍵}⍣⍵⊢1↑⍨2/2×⍵}

Try it on APLgolf!

A dfn submission which takes the number of terms to output.

A bit ungolfed, most of the bytecount is finding the cancelled out squares.

Instead of going by antidiagonal, goes column by column and places greedily.

-34 bytes from dzaima.