[Question]
  [
### Challenge
Implement the "greedy queens" sequence (OEIS: [A065188](https://oeis.org/A065188)).
### Details
*Taken from the [OEIS page](https://oeis.org/A065188).*
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](/questions/tagged/sequence "show questions tagged '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](/questions/tagged/code-golf "show questions tagged '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]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 38 [bytes](https://github.com/abrudz/SBCS)
```
1+{⍵,⊃⍸|⊃×/×(⌽⍳≢⍵)(⊢×+×-)⍵-⊂⍳3×≢⍵}⍣⎕⊢⍬
```
[Try it online!](https://tio.run/##JZA9TsNAEEZ7n2LLRNmIXY//chxLYJoIEFQoSQMSUiws0bkmtHQIiYbKN9mLmPeFYndm3nyzM7Pt3XZ9@dhub6/nLr287ea42qXh26f@OQ0/e8w0XkzjIr3@puErHU8kl4vUn6ZxNY3rJeE69U/kbBr/04c0fGDQpOFzPsydiyHrnIUM1N480KZz9Tm6v1LT6J15V3qXe1d4t/EugiIsAivvGjxojQJJDFipFYNNYnFqDW5wgxfiVEfKC3iEF/g59SW5kga5LJoSXuldWCXOWxU8lx5bk6vpUcNrxXCDGazRgTdwo7bRTNoDbtLBNzpaIwRdWvTsaKyguTS/Fiu0dbRM/3R853/@AA "APL (Dyalog Unicode) – Try It Online")
Kinda port of tsh's [JS](https://codegolf.stackexchange.com/a/235150/78410) and [Python](https://codegolf.stackexchange.com/a/235153/78410) 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]
# [JavaScript (Node.js)](https://nodejs.org), 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!](https://tio.run/##FcpNCoMwEEDhq8ymOJOaoLRQKoweokvrImgURSfiT6Cnt7p7fLzBBrvWSz9vWnzjjqNl4dyyFKUxpkWthWLsOJxoXHDLD3fOcdccSKmH3tWkJq3jiYWKkHUY7ikRplRlZXXUXlY/OjP6Dlt8JWQmOyNKDD0B54ACd4giMrNtPptdNnzSKdjDDdIEmOENBURfiSC7PjKD7wWvOv4 "JavaScript (Node.js) – Try It Online")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 19 bytes
```
Ṁ×3Rḟḟ+;_ɗJ$Ṃ;
1Ç¡Ḣ
```
[Try it online!](https://tio.run/##y0rNyan8///hzobD042DHu6YD0Ta1vEnp3upPNzZZM1leLj90MKHOxb9///fyAAA "Jelly – 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](https://tio.run/##y0rNyan8///hzobD042DHu6YD0Ta1vEnp3upPNzZZM1leLj9UeOOQwsf7lj038jg4Y5tQH7Tmv8A "Jelly – Try It Online") 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]
# 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!](https://tio.run/##FYxBCsIwEEWvMkIXGSfRdlsdexNpaFpRykRakQmlZ49x9XmPx3/5r1@H5fn@OIlhzHliI1a5tokb5Js47aZiiPSoZxM4uYJOEe@h0/ZAlGzCNuUpLkaAob6AwBWa/xIhDFHWOI@nOT5M7021yY4lq7Zyg3uP@Qc "JavaScript (Node.js) – 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](https://tio.run/##FYzBCsIwEER/JUIPWTfRehKqaz9ElIamEUvZSCuS0PbbY3qaecxjevMzUzu@P1/N3nYpOZKsApUq0gno5u78INah3sqyuDwihn04SktRZ9QB4GnrUO0Qo4pQxeT8KFmQKC@CxVWct0QE0Xqe/NAdBv@SjZHFzCtkrZjzDawNpD8) (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]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 64 [bytes](https://github.com/abrudz/SBCS)
```
{a←⍬⋄⍵↑1+-/¨a[⍋⌽¨a]⊣{a,←1↑(⍸∘.≥⍨w)~a∘.+(¯1+⍳3 2)∘.×w←⍳3×⍵}¨⍳3×⍵}
```
[Try it online!](https://tio.run/##RY8/SwNBEMX7fIotE7LR3Zv7l9pGW2MnFgtyNkEFiyBBGyWYxAtaSGxVhCuEFEGwsbl8k/ki53tpLHb3zW/ezM6Ey2Hv9DoML86aZhx08qTll87vtfzWybPv9nbrKhxrOdfHX6gTnX2Mg4XNI93W8kcfXnd0@qllNercBkbddr3yXS3XYqIOwWY52vZdy2aJvjd19a@bYpta6OyuXgl66uJlcLiH@2j/YNAUxrtWYcS1dPYezq9gLkzmWpTTN2@NWJNYE1kTW9O3xgN5MA@YWpNDgWZwwOIdXroZAwvN5KgVcAEX8Jgc1R7lMbgHj6Ej1CfIJfgg4gtPAp6yL1hKjl4peEQ/3gy5DH9k4BljcAETsJwHPAcX1OaciXuAC33gfR6u4RwvLroVHMtxLs7PxWJu7eUP "APL (Dyalog Unicode) – 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]
# [Python 3](https://docs.python.org/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!](https://tio.run/##jY5BCsIwEEX3OcVYKGRsKw26EuIRvICIxNrolGRS0hbUy9fWhbp0M3zm895M@@hvgdfjaLUz/nwxwDlptaWlcU5y4RfanDtJhZUecVfaEMEDMUTD11oy4rSwcoIyhWMbiXu5PCTp5pJAOhWEMCP0RVSJRxSCfBtiD3bgqg/BdcLqT165OJwqU91q6c29o2et94FrlBbFbGt@bTmo8j1w@8/5Jocme/8wvgA "Python 3 – Try It Online")
[Answer]
# [R](https://www.r-project.org/) >= 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!](https://tio.run/##PcgxCoAwDAXQ6@RrBFs3wUu4ioO0DbhUtBXi6aOTb3yXyWRy51D3I1PGnOIdEv2j/CBQSTXuIuRGGpoHHL7XlrappJMUYO02YHErK9iNGSbke5j5/gU "R – Try It Online")
A function taking an integer n and returning the sequence of the first n terms in reverse order.
[Answer]
# [Perl 5](https://www.perl.org/), 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!](https://tio.run/##JYxRCgIhFEW3YnD7adKUGELCJbQGGRgLIXR4ShCDW@/l1N85F85dAj1HZpQVsbndg8Kyojr464a/WcIfUNvRWquU0do0oxTiMJxMOE9pFmV6gxzi/u@9cCDZJZOgMGdx77A1nvmiP3mpMafCMrG8vcZ@@QU "Perl 5 – Try It Online")
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 22 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
╙½#≡]☺è60S|f♣V♦i+é(ç░m
```
[Run and debug it](https://staxlang.xyz/#p=d3ab23f05d018a3630537c66055604692b822887b06d&i=)
Runs as an infinite loop producing output. It's very brute-force.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 17 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
+;_ɗ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!](https://tio.run/##ASYA2f9qZWxsef//KztfyZdKO@KBuDHhuJ8xIzsKMcOHwqHhuKL///83MA "Jelly – 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]
# [Charcoal](https://github.com/somebody1234/Charcoal), 30 bytes
```
ＦＮ«≔¹θＷ⊙υ№×Ｅ³⊖ν⁻ιμ⁻θλ≦⊕θ⊞υθ»Ｉυ
```
[Try it online!](https://tio.run/##Rc29DoIwFIbhGa7ijOckNZE4MhFcGDAM3kDFKk3aA/RHY4zXXiEh@m3v8OXpB@n6UZqUbqMDbHiK4RTtRTkkgneeVd7rO2MhYKYyz56DNgqw4hdGAfUYOeBZW@WxlRMeBBxV75RVHNQVmUhAqzl61ALsv2YBhpbBctqAhn@/jeqiH1ZkjU/eOb1QtfQBI1GZUrFPu4f5Ag "Charcoal – 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]
# [APL(Dyalog Unicode)](https://dyalog.com), ~~104~~ 70 bytes [SBCS](https://github.com/abrudz/SBCS)
```
{⊢/↑⍸⍉{1@(⊂⊃{⍵[⍋⊢/↑⍵]}⍸~⊃∨/(≢⍵)∘{⊃∘.(=∨0=×)/|⍵-⊂⍳⍺}¨⍸⍵)⊢⍵}⍣⍵⊢1↑⍨2/2×⍵}
```
[Try it on APLgolf!](https://razetime.github.io/APLgolf/?h=AwA&c=q37UtUj/UdvER707HvV2Vhs6aDzqanrU1Vz9qHdr9KPebrj01thaoJo6oNSjjhX6Go86FwHFNB91zKgGC83Q07AFShjYHp6uqV8DlNIFmdO7@VHvrtpDK8CmA1V3gTQBzVkMpIAcQ7DJK4z0jQ5PB0kAAA&f=S1MwNAQA&i=AwA&r=tryapl&l=apl-dyalog&m=dfn&n=f)
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.](https://chat.stackexchange.com/transcript/message/59090582#59090582)
]