The number of solutions to Hertzsprung's Problem

Question

Hertzprung's Problem (OEIS A002464) is the number of solutions to a variant of the Eight Queens Puzzle, where instead of placing \$n\$ queens, you place \$n\$ rook-king fairy pieces (can attack like both a rook and a king); in other words, it's how many possible positions you can place \$n\$ rook-kings on an \$n \times n\$ board such that each piece does not occupy a neighboring square (both vertically, horizontally, and diagonally).

Challenge

Write the shortest function or full program that will output the number of solutions to Hertzprung's Problem.

You may either:

• output just \$\operatorname{A002464}(n)\$, given a positive integer \$n > 0\$, or
• output all terms of \$\operatorname{A002464}(k) \text{ where } 0 < k < \infty\$ as a sequence.

Notes

• A formula is derived in this video: $$ \operatorname{A002464}(n) = n! + \sum_{k=1}^{n-1} (-1)^k(n-k)!\sum_{r=1}^k 2^r \binom{n-k}{r} \binom{k-1}{r-1} $$

Test Cases

1:  1
2:  0
3:  0
4:  2
5:  14
6:  90
23: 3484423186862152966838

Answer 1

Nekomata + -n, 6 bytes

r↕∆A1>

Attempt This Online!

Brute force. Slow for large input.

r↕∆A1>
r↕      Find a permutation of [0..n-1] such that
  ∆A    the absolute differences of adjacent elements
    1>  are all greater than 1

The flag -n count possible solutions.

Answer 2

Jelly, 7 bytes

^{I almost asked this question after watching Another Roof's video.}

Œ!IỊ§¬S

A monadic Link that accepts \$n\$ and yields the number of solutions.

Try it online!

How?

Œ!IỊ§¬S - Link: non-negative integer, n  e.g. 4
Œ!      - all permutations (of [1..n])        [[1,2,3,4],[1,2,4,3],...,[2,4,1,3],...,[3,1,4,2],...,[4,3,2,1]]
  I     - forward differences                 [[1,1,1],[1,2,-1],...,[2,-3,2],...,[-2,3,-2],...[-1,-1,-1]]
   Ị    - insignificant?                      [[1,1,1],[1,0,1],...,[0,0,0],...,[0,0,0],...[1,1,1]]
    §   - sums                                [3,2,...,0,...,0,...3]
     ¬  - logical NOT                         [0,0,...,1,...,1,...,0]
      S - sum                                 2

...yes, it also works if \$n=0\$ (the alternative of Œ!IỊ§ċ0 would give \$0\$ rather than \$1\$).

Answer 3

05AB1E (legacy), 7 bytes

Lœ¥Ä≠PO

Port of @alephalpha's Nekomata answer, so also a slow brute-force for larger inputs.

Try it online or verify most test cases.

Explanation:

L       # Push a list in the range [1, (implicit) input-integer]
 œ      # Get all permutations of this list
  ¥     # † For each inner permutation-list: get its deltas / forward-differences
   Ä    # Get the absolute value of each inner-most difference
    ≠   # Check for each that it's NOT 1 (so basically >= 2)
     P  # Product on each inner list, to check for which all overlapping pairs are >=2
      O # Take the sum, to check how many are truthy
        # (after which it is output implicitly as result)

† Uses the legacy version of 05AB1E to save 1 byte, because ¥ vectorizes on a list of lists, whereas the new 05AB1E version would give an error, and would require an additional € before the ¥ to accomplish the same thing.

Answer 4

><> (Fish), 60 bytes

11005:&$:@*3[{:}]&3-:&*-4[{:}]&3-:&*-5[{:}]&2+:&*+:nao&5+40.

Try it

Infinitely prints values starting at n=4.

Based on the recursive formula pioneered by Arnauld but instead of recursing just keeps previous values pushed to the stack.

Answer 5

Desmos, 69 bytes

K=n-k+1
f(n)=n!-∑_{k=2}^n(-1)^kK!∑_{a=1}^k2^anCr(K,a)nCr(k-2,a-1)

Nice.

Try It On Desmos!

Try It On Desmos! - Prettified

Answer 6

PowerShell, 125 bytes

Try it online

Golfed Version:

function G($i){if($i -lt 4){if($i -lt 2){1}else{0}}else{($i+1)*(G($i-1))-($i-2)*(G($i-2))-($i-5)*(G($i-3))+($i-3)*(G($i-4))}}

Un-Golfed Version:

function G($i){
if($i -lt 4)
    {if($i -lt 2){1}
    else{0}
}else{
    ($i+1)*(G($i-1))-($i-2)*(G($i-2))-($i-5)*(G($i-3))+($i-3)*(G($i-4))
}
}

Let me know of any improvements!

Answer 7

Aussie++, 136 bytes

Tested in commit 9522366. Loses precision for inputs >18, because all numbers are doubles.

THE HARD YAKKA FOR a IS(n)<YA RECKON n <2?BAIL 1;YA RECKON n <4?BAIL 0;BAIL(n +1)*a(n -1)-(n -2)*a(n -2)-(n -5)*a(n -3)+(n -3)*a(n -4);>

Aussie++ requires every identifier to be followed by whitespace, a semicolon, a comma, or a paren, so I can't remove the spaces before all the operators. It also doesn't have bitwise operators, and the equivalent to -- is PULL YA HEAD IN, so I can't take the same shortcuts as the JS and C answers.

Example test code:

G'DAY MATE!

THE HARD YAKKA FOR a IS(n)<YA RECKON n <2?BAIL 1;YA RECKON n <4?BAIL 0;BAIL(n +1)*a(n -1)-(n -2)*a(n -2)-(n -5)*a(n -3)+(n -3)*a(n -4);>

I RECKON i IS A WALKABOUT FROM [0 TO 18] <
  GIMME "" + i + ": " + a(i);
>

CHEERS C***!

Answer 8

Vyxal Rl, 36 bits¹, 4.5 bytes

Ṗ'¯ȧċA

Try it Online! (link is to bitstring)

Port of Kevin Cruijssen's 05AB1E answer, which is in turn a port of alephalpha's Nekomata answer. Like those, it is a brute force solution, suffering with the same slowdown on larger inputs.

Ṗ      # permutations of the range 1..n (due to the R flag)
 '     # filtered by
  ¯ȧ   # absolute value of the deltas
     A # are all
    ċ  # not 1
       # the length of this filtered list is taken by the l flag
       # and implicitly output

Answer 9

PARI/GP, 51 bytes

n->Vec(sum(i=0,n,i!*(x*(1-x)/(1+x))^i)+O(x^n++))[n]

Attempt This Online!

Based on the generating funtion on the OEIS page.

Answer 10

JavaScript (ES6), 56 bytes

Based on the recurrence formula provided on OEIS.

f=n=>n<4?n/2^1:-~n--*f(n--)-n*f(n)-(n-3)*f(--n)+n*f(n-1)

Try it online!

With Bigints, 58 bytes

f=n=>n<4?n/2n^1n:-~n--*f(n--)-n*f(n--)-~-~-n*f(n)+n--*f(n)

Try it online!

Answer 11

C (gcc), ⁶⁰ 58 bytes

f(n){n=n<4?n<2:-~n--*f(n--)-n*f(n)-(n-3)*f(--n)+n*f(n-1);}

Try it online!

Port of Arnauld's JavaScipt answer.

Saved 2 bytes thanks to Arnauld

Answer 12

Raku, 132 bytes

Translated the (corrected) formula directly; not particularly golfed, just crunched out all the unnecessary whitespace:

->\n{[*](1..n)+[+]((1..n-1).map: ->\k{(-1)**k*[*](1..n -k)*[+]((1..k).map: ->\r{2**r*combinations(n -k,r)*combinations(k-1,r-1)})})}

Try it online!

Answer 13

Charcoal, 34 bytes

Ｆ⁴⊞υ‹ι²ＦＮ⊞υΣ×⮌υ⟦⁺⁵ι±⁺²ι⁻¹ι⊕ι⟧Ｉ§υ±⁴

Attempt This Online! Link is to verbose version of code. Outputs the nth element. Explanation:

Ｆ⁴⊞υ‹ι²

Start with the first four values (0-indexed, so 1, 1, 0, 0).

ＦＮ⊞υΣ×⮌υ⟦⁺⁵ι±⁺²ι⁻¹ι⊕ι⟧

Use the recurrence relation to calculate n more values.

Ｉ§υ±⁴

Output the 4th last value.

Answer 14

Japt -x, 10 bytes

õ á Ëäa eÉ

Try it

Answer 15

Scala, 97 bytes

Based on the recurrence formula provided by A002464.

Golfed version. Try it online!

def f(n:Int):Int=if(n<4){if(n<2)1 else 0}else (n+1)*f(n-1)-(n-2)*f(n-2)-(n-5)*f(n-3)+(n-3)*f(n-4)

Ungolfed version.

object Main {
  def f(n: Int): Int = {
    if (n < 4) {
      if (n < 2) 1 else 0
    } else {
      (n + 1)*f(n-1) - (n - 2) *f(n-2) - (n - 5) *f(n - 3) + (n - 3)* f(n - 4)
    }
  }

  def main(args: Array[String]): Unit = {
    val tests = Array(1, 2, 3, 4, 5, 6)
    val expected = Array(1, 0, 0, 2, 14, 90)
    val checker = Array("✕", "✓")

    for (index <- tests.indices) {
      val t = tests(index)
      val s = f(t)
      val e = expected(index)
      println(s"$t -> $s ${checker(if (s == e) 1 else 0)}")
    }
  }
}