Counting Queen's paths on a rectangular chessboard

Question

Task

Given two positive integers \$m,n\$, imagine a chessboard of size \$m \times n\$. A chess queen is on the upper-left corner. In how many ways can it reach the lower-right corner, by moving only right, down, or diagonally right-down (possibly moving many steps at once, because it's a queen)?

The resulting 2D sequence is A132439.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

m n result
1 1      1
1 2      1
1 3      2
1 4      4
1 5      8
2 2      3
2 3      7
2 4     17
2 5     40
3 3     22
3 4     60
3 5    158
4 4    188
4 5    543
5 5   1712

Answer 1

Haskell, 94 91 64 54 bytes

1!1=1;m!n=sum[m!(n-x)+(m-x)!n+(m-x)!(n-x)|x<-[1..m+n]]

Try it online!

Initially a boring port of the comment on OEIS

-27 from some tricks off dingledooper's answer

-10 from Christian Sievers

Answer 2

Python 2, 75 bytes

@xnor's idea which is 2 bytes smaller than the one below. Returns True for 1 1.

f=lambda m,n:sum(f(m-i,n)+f(m,n-i)+f(m-i,n-i)for i in range(1,n|m))or m>0<n

Try it online!

---

Python 2, 79 77 bytes

f=lambda m,n:(m==n==1)+sum(f(m-i,n)+f(m,n-i)+f(m-i,n-i)for i in range(1,n+m))

Try it online!

Answer 3

K (ngn/k), 36 bytes

{(x~1 1)+/o'x-/:{|/'~x,'-/'x}#1_+!x}

Try it online!

!x odometer

+ transpose

1_ drop the first

{ }# filter

|/'~x,'-/'x either element or their difference is 0

x-/: subtract each right

o' recur each

+/ sum

(x~1 1) does x match 1 1? use as initial value for the sum

Answer 4

Erlang (escript), 92 bytes

Boring port of the Haskell answer.

f(1,1)->1;f(M,N)->lists:sum([f(M,N-X)+f(M-X,N)+f(M-X,N-X)||X<-lists:seq(1,max(M,N)),M*N>0]).

Try it online!

Answer 5

Charcoal, 40 bytes

ＮθＦＮＦθ⊞υ∨¬υΣΦυ∨∨⁼ι÷μθ⁼κ﹪μθ⁼⁻ικ⁻÷μθ﹪μθＩ⊟υ

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input the number of columns.

ＦＮ

Loop over the rows.

Ｆθ

Loop over each column.

⊞υ∨¬υ

The first result is always 1...

ΣΦυ∨∨⁼ι÷μθ⁼κ﹪μθ⁼⁻ικ⁻÷μθ﹪μθ

... otherwise find the existing results that are a Queen's move away, take the total, and push that to the list of results. The list therefore simulates a matrix, requiring its index to be divided or taken modulo the number of columns as appropriate to compare with the loop variables.

Ｉ⊟υ

Output the last result calculated.

Answer 6

J, ⁶⁰ 50 bytes

_2{(],1#.]#~(#:#)(0=*/*-/)@:-"1(#:i.@#))^:(*/@[)&1

Try it online!