When Fibonacci meets the Queens

Question

(inspired by Helka's response to my random pairing of "chess" and "Fibonacci" tags in chat)

---

Fibonacci

The Fibonacci numbers are one of the more well-known sequences in mathematics, where each number is composed by adding the two previous numbers together. Below is a definition of the zero-indexed sequence:

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)

This results in the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, ... (OEIS link). In this challenge, we'll be focusing on only the strictly-positive values (so 1, 1, 2, 3, ...), and you can choose zero-indexing or one-indexing, but please state which in your submission.

The Fibonacci numbers can be used for a tiling of the plane, by using squares that are successive f(n) in size, and aligning their edges together. The tiling is done in a counter-clockwise fashion, by placing squares in the pattern "right-up-left-down" from the current square. An example of this partial tiling for f(8)=21, with the starting square highlighted in blue, is as follows:

You can see the f(1)=1 as the starting square (highlighted in blue), the f(2)=1 square placed to the right of it, the f(3)=2 square placed up from there, the f(4)=3 square placed left and so on. The next square would be f(9)=21+13=34 and would be placed to the bottom. This is the partial tiling method we'll be using in this challenge.

---

The Queens

In the game of chess, the most powerful piece is the queen because it can move any number of spaces horizontally, vertically, or diagonally. In the below board diagram, the squares with a black circle show where the queen can move:

We'll define the term coverage as

The percentage of squares that the queen can move to versus the total number of squares, given the queen's particular position on an empty board, and including the queen's own starting position.

For the example moves above, the queen's coverage is 28/64 = 43.75%. If the queen was in the upper-right h8 square, the coverage would be 22/64 = 34.375%. If the queen was in e7, the coverage would be 24/64 = 37.5%.

---

The Challenge

We're going to use the Fibonacci tiling demonstrated above as our chess board for this challenge. You'll be given two positive integers as input, n and x:

• The n represents how large the tiling is. The example tiling above, with the 21 square on the left, is a board of size n = 8 since f(8) = 21 (when zero-indexed).
• The x represents which of the Fibonacci squares is used for the queen(s) placement, for calculating the coverage. The queens are placed one-at-a-time on each square in that particular Fibonacci square tile, and the total coverage is the summation of the individual (unique) coverage.

For example, here is an image of n = 8 (the same tiling as above) and x = 4 (corresponding to the f(4) = 3 square, shaded blue). By placing a queen one-at-a-time into each of those nine blue squares, the queens can (combined) cover every square that's shaded orange. The total coverage in this example is therefore 309/714 = 43.28%.

Quite obviously, any time that n = x, the coverage is going to be 100% (for example, with n=8 and x=8, you can see that every square on the entire board is going to be covered at least once). Conversely, with a suitably large n and x=1 or x=2, the coverage is going to approach (but never reach) 0% (for example, with n=8 and x=1, the coverage is a paltry 88/714 = 12.32%).

Given two such input numbers, you must output the coverage percentage, accurate to two decimal places. Please specify how your code handles rounding.

---

Rules

• The input and output can be given in any convenient format, but must be accurate to two decimal places. Please specify how your code handles rounding.
• Assume no other pieces are on the board or otherwise interfere with the moves.
• Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
• If possible, please include a link to an online testing environment so other people can try out your code!
• Standard loopholes are forbidden.
• This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

---

Examples

n = 8, x = 4
43.28

n = 8, x = 8
100 or 100.00

n = 8, x = 1
12.32

n = 4, x = 1
66.67

n = 4, x = 2
60 or 60.00

n = 5, x = 3
75 or 75.00

n = 5, x = 1
47.5 or 47.50

Answer 1

APL(Dyalog Unicode), 61 bytes ^SBCS

{2⍕100×(+/÷≢)∨⌿⊃∊⍤1⍥{⍉↑(⊢,+/,-/)¨⍸⍵}/1 0⌈{⌽⍉⍺,⍣(≢⍵)⍪⍵}/⌽⍺=⍳⍵}

Try it on APLgolf!

A pretty nice challenge for APL. This is an infix function that takes x on its left and n on its right, and returns the string representation of the rounded percentage. A full program would be 59 bytes (though I don't like using that I/O format because writing tests is cumbersome):

2⍕100×(+/÷≢)∨⌿⊃∊⍤1⍥{⍉↑(⊢,+/,-/)¨⍸⍵}/1 0⌈{⌽⍉⍺,⍣(≢⍵)⍪⍵}/⌽⎕=⍳⎕

How it works

Constructs a boolean matrix representing the grid in question where 1 means a queen, and counts all the cells that share their row, column, diagonal, or anti-diagonal with some 1 cell.

{⌽⍉⍺,⍣(≢⍵)⍪⍵}/⌽⍺=⍳⍵    Part 1: construct the matrix; ⍺←x, ⍵←n
              ⌽⍺=⍳⍵    A boolean vector of length n with x-th from the end
                       marked as 1
{           }/    Reduce from right to left:
   ⍺,⍣(≢⍵)⍪⍵      Attach a square filled with ⍺ on the left of current matrix ⍵
 ⌽⍉               Rotate clockwise once
                  Reduction gives an enclosed matrix

∊⍤1⍥{⍉↑(⊢,+/,-/)¨⍸⍵}/1 0⌈    Part 2: Find possible Queen moves
                     1 0⌈    Get an all-ones matrix and the original matrix
   ⍥{              }/    Apply to each matrix:
                 ⍸⍵      Get all coordinates of ones
       (⊢,+/,-/)¨        For each coord [r, c], get [r, c, r+c, r-c]
                         (rownum, colnum, anti-diag-num, diag-num)
     ⍉↑                  Matrixify and transpose
∊⍤1    For each row, convert each number on its left side as 1 if
       it appears on the right on the same row
       The result is a 4-row matrix with each column representing a cell,
       where a 1 means that cell is reachable by moving in specific direction

2⍕100×(+/÷≢)∨⌿⊃    Part 3: Calculate average
               ⊃    Disclose the enclosed matrix
            ∨⌿     Boolean OR of each column
      (+/÷≢)       Average (reachable cells ÷ all cells)
2⍕100×             Percentage rounded to 2 decimal places

Answer 2

VB.NET, (.NET 4.5), 1238 1229 bytes

-9 bytes thanks to @totallyhuman

Function A(n,x)
Dim g=New List(Of List(Of Long))
g.Add(New List(Of Long))
g(0).Add(1)
For i=2To n
Dim b=1
If i>2Then 
Dim w=0,y=1
b=w+y
For j=3To i
w=y
y=b
b=w+y
Next
End If
Select Case i Mod 4
Case 1
For j=1To b
Dim l=New List(Of Long)
For k=1To b
l.Add(i)
Next
g.Add(l)
Next
Case 2
For Each r In g
For j=1To b
r.Add(i)
Next
Next
Case 3
For j=1To b
g.Insert(0,New List(Of Long))
For k=1To b
g(0).Add(i)
Next
Next
Case 0
For Each r In g
For j=1To b
r.Insert(0,i)
Next
Next
End Select
Next
For i=0To g.Count-1
Dim c=g(i)
For j=0To c.Count-1
Dim e=c(j)
If e=x Then
For k=1To Math.Max(g.Count,g(0).Count)
If j-k>=0AndAlso c(j-k)<>x Then c(j-k)=0
If i-k>=0AndAlso g(i-k)(j)<>x Then g(i-k)(j)=0
If j+k<c.Count AndAlso c(j+k)<>x Then c(j+k)=0
If i+k<g.Count AndAlso g(i+k)(j)<>x Then g(i+k)(j)=0
If i-k>=0AndAlso j-k>=0AndAlso g(i-k)(j-k)<>x Then g(i-k)(j-k)=0
If i-k>=0AndAlso j+k<c.Count AndAlso g(i-k)(j+k)<>x Then g(i-k)(j+k)=0
If i+k<g.Count AndAlso j-k>=0AndAlso g(i+k)(j-k)<>x Then g(i+k)(j-k)=0
If i+k<g.Count AndAlso j+k<c.Count AndAlso g(i+k)(j+k)<>x Then g(i+k)(j+k)=0
Next
End If
Next
Next
Dim hits=0
For Each r In g
For Each c In r
If c=x Or c=0Then hits+=1
Next
Next
Return Math.Round(hits*100/(g.Count*g(0).Count),2)
End Function

Simulation of the problem statement. I start by creating the grid, looping through each new fibonacci number to increase the square size. I store the index in each cell, so that it's easy to find where the queens will go in the next step.

Then, I find every cell that should have a queen in it, and mark each threatened square with a zero. I skip the cells where the queens are so that I don't have to worry about backtracking.

At the end, I count up the cells that are cleared, and the cells with queens, and then divide it by the total number of spaces. Multiply by 100 to get the percent, and round to the nearest two decimal places.

Answer 3

Python 2, 524 499 bytes

def Q(n,x):
 global w,h,f;f,R,L=0,range,len
 for d in R(n):s=x-1==d;f=f or[[s]];w=L(f[0]);W,H=R(w),R(L(f));exec"for j in "+("W:f.append([s]*w)","f:\n\tfor k in H:j.append(s)","W:f.insert(0,[s]*w)","f:\n\tfor k in H:j.insert(0,s)","f:0")[d%4-(d==0)]
 w,h=L(f[0]),L(f);l=0,1,-1
 for Y in R(h):
	for X in R(w):exec("""def F(u,v,x,y):
 while(u==v==0)==0<=x<w!=0<=y<h:f[y][x]=1+(f[y][x]!=1);x+=u;y+=v
for s in l:
 for t in l:F(s,t,X,Y)""","")[f[Y][X]!=1]
 q=w*h;return(q-sum(j.count(0)for j in f))*100./q

Try it online!

Defining a function that takes in both the tiling size n and the queen's fibonacci square number x. The ouput percentage is porperly rounded to two decimal places (in the footer, where all output is taking place).

f is a two-dimensional array containing the board information being initiated to 0. Then, the fibonacci chess board is calculated and populated with queens where queens shall be. Those queens are then moved to every place they can be moved; all positions are counted and printed as a percentage of the entire board.

Answer 4

Mathematica 11.1, 336 bytes, 1-based

R=Rectangle[#,+##]&;f=Fibonacci;o=Join@@Outer[##,1]&;r=RegionUnion;s=RegionMeasure;p[1]={0,0};p[i_]:=p[i-1]+{{-f@i,-f[i-2]},{0,-f@i},{f[i-1],0},{f[i-1]-f@i,f[i-1]}}[[i~Mod~4+1]];t[i_]:=r[R[p@#,f@#]&/@Range@i];k[n_,x_]:=Round[100s@RegionIntersection[r[R[#,f@x]&/@((#+p@x)&/@o[1##&,o[List,{-1,0,1},{-1,0,1}],Range[2f@n]])],t@i]/s@t@i,.01]

Usage: k[n, x]. Pay attention that the function is 1-based. Rounding is achieved by Round[100x,0.01]

Basically, p[i] is a function of determining position of each square. And area is calculated by upper-level functions like RegionIntersection, RegionUnion, RegionMeasure