# Sequential Counterfactual Decision-Making Under Confounded Reward

Erik Skalnes
<EMAIL_ADDRESS>

###### Abstract

We investigate the limitations of random trials when the cause of interest is
confounded with the effect by formalizing a counterfactual policy-space where
the agent’s natural predilection is input to a soft-intervention. By
connecting the counterfactual intervention in $G$ to a soft-intervention in a
related graph called the conditional-twin, we prove graphical conditions under
which the two policy types coincide in optimality. We also provide an
estimation procedure for the distribution under the counterfactual-
intervention, and connect it with the counterfactual distribution.

##  1 Introduction

The canonical goal of a multi-armed bandit problem is to find $x\in X$ that
maximizes reward $Y$. This means finding $x^{*}\in X$ such that

$x^{*}=\operatorname*{arg\,max}\limits_{x}E[Y\mid do(x)]$

Algorithms like UCB or Thompson Sampling find $x^{*}$ by keeping an empirical
distribution over reward for each arm. They explore arms with fewer samples
and exploit arms with higher averages. If the empirical average over arms is
about equal after many trials, it is tempting to conclude that the arms are
about equal. In this paper, we give graphical conditions for when this type of
experimentation may not correctly identify the optimal policy.

Past work has optimized the effect of the treatment on the treated to
differentiate empirically equal arms.1 In MDP’s, it was shown that algorithms
that account for actions confounded with reward dominate algorithms that rely
entirely on experimentation.2 We prove conditions where such algorithms
dominate experimental algorithms for any environment. We also formally prove
why the algorithm in [1] works, and extend the results to the sequential-
action case.

The counterfactual randomization procedure described in this paper is relevant
to any experimental pursuit where the environment is not fully known.
Unobserved confounding can invalidate the conclusions of a random trial. We
criticize experiments by proving their sub-optimality, and suggest a fix.

##  2 Background

A fundamental goal of causal inference is to determine a layer 2 query, of the
form $P(Y\mid do(x))$, from layer 1 data, of the form $P(V)$.3 This is useful
when interventions, like randomized control trials, cannot be performed. Even
when they can, past work had to formalize the conditions under which the
results of the trial can be extrapolated to new environments.4

The primary contribution of this paper is to lay the theoretical foundations
for estimating a layer 3 query from layer 2 data. The idea is that a decision
confounded with reward allows inference about unobserved variables. This
inference is only available in layer 1, because in layer 2 the confounding
arrow is cut.

We formalize the conditions under which such an inference is useful by
presenting a generalization of a soft-intervention called the counterfactual
intervention $\rho$. It accounts for the ”natural predilection” of the
decision-variable as it is determined by unobservable variables. We show that
$\rho$ induces a sub-model on $G$ whose distribution is equivalent to the
distribution induced by a soft-intervention $\pi$ in the conditional-twin of
$G$. We then provide two examples of an estimation procedure in a realistic
scenario, and use this procedure to formally explain the results in [1]. We
also give graphical conditions for the advantage of the optimal
counterfactual-intervention over the optimal soft-intervention based on the
connection between value of information and d-separation.

To ground the definitions, we consider the following causal graph implied by
the SCM $M=<F,V,U,P(U)>$.

Figure 1: Example Graph G

where
$A\leftarrow f_{A}(u_{A})$
$B\leftarrow f_{B}(a,u_{B})$
$Y\leftarrow f_{Y}(a,b,u_{Y})$
and $P(U)$ is arbitrary

We refer to the twin graph of $G$ as $G^{\prime}$ and note that $Y$ is a
reward variable. That is, the objective of the intervention is to estimate the
distribution over $Y$.

##  3 Counterfactual Interventions

Let $N\in V$ be an observable node with natural value $f_{N}(pa(N),U_{N})$.
Let $\rho_{N}$ be a counterfactual intervention if $\rho_{N}:N\rightarrow N$
maps $f_{N}(pa(N),U_{N})\rightarrow P(n\in N)$. That is, $\rho_{N}$ maps the
natural value of $N$ under a setting of $U$ to a distribution over the domain
of $N$.

The key difference from a soft intervention $\pi_{N}:A\in An(N)\rightarrow
P(n\in N)$ is that $\rho$ maps information that depends on $f_{N}$ and
$U_{N}$, whereas $\pi_{N}$ can only account for $An(N)$.

We can extend the definition to more than one variable by defining a
counterfactual intervention on a set of variables as a set of counterfactual
interventions on each variable in the set. Let $I\subseteq V$ be a set of
”intuition” variables and $\rho_{I}$ be a set of counterfactual interventions
$\rho_{I}:=\\{\rho_{i}\mid\rho_{I}:f_{I}(U)\rightarrow I\\}$ then $\rho_{I}$
is a set of counterfactual interventions.

Consider $\rho_{I}$ for $I=\\{A,B\\}$ on $G$

Figure 2: $G_{\rho_{I}}$

which induces the functional form
$A\leftarrow\rho_{A}(f_{A}(u_{A}))$
$B\leftarrow\rho_{B}(f_{B}(\rho_{A},u_{B}))$
$Y\leftarrow f_{Y}(\rho_{A},\rho_{B},u_{Y})$

Note two salient features: (1) the counterfactual intervention does not cut
incoming arrows like atomic or soft interventions, and (2) the natural value
$f_{B}$ that $\rho_{B}$ changes is dependent on $\rho_{A}$. Fact (2) motivates
the definition of a conditional twin graph.

##  4 Conditional Twin

Before motivating the conditional-twin, it is important to motivate a soft-
intervention on the twin graph as it relates to the counterfactual
intervention. Then we prove a theorem equivocating the distribution in $G$
under a counterfactual-intervention with the distribution in the conditional-
twin of $G$ under a soft-intervention.

###  4.1 Motivation

In the single-action case with action $A$, the counterfactual intervention on
$G$ is equivalent to a soft-intervention on $G^{\prime}$. Consider
$G_{\rho_{A}}$, the sub-model induced by $\rho_{I}=\\{\rho_{A}\\}$ on $G$:

$A\leftarrow\rho_{A}(f_{A}(U_{A}))$
$B\leftarrow f_{B}(A,U_{B})$
$Y\leftarrow f_{Y}(A,B,U_{Y})$

The value of $A$ that is input to $B$ and $Y$ is $\rho_{A}(f_{A}(U_{A}))$. The
value of $B$ that is input to $Y$ is $f_{B}(\rho_{A}(f_{A}(U_{A})),U_{B})$. No
variables after $A$ in the topological order ’see’ $f_{A}$.

Consider the sub-model induced by $\pi_{A}:a\in A\rightarrow P(a\in
A^{\prime})$ on $G^{\prime}$, a soft-intervention on the twin graph of $G$.

Figure 3: $G^{\prime}_{\\{\pi_{A}\\}}$

$A\leftarrow f_{A}(U_{A})$
$B\leftarrow f_{B}(A,U_{B})$
$Y\leftarrow f_{Y}(A,B,U_{Y})$

$A^{\prime}\leftarrow\pi_{A}(f_{A}(U_{A}))$
$B^{\prime}\leftarrow f_{B}(A^{\prime},U_{B})$
$Y^{\prime}\leftarrow f_{Y}(A^{\prime},B^{\prime},U_{Y})$

Let’s call $A,B,Y$ row0. The distribution over variables in row0 is the same
as the distribution over variables in $G$ with no intervention. Let’s call
$A^{\prime},B^{\prime},Y^{\prime}$ row1. The distribution over variables in
row1 is the same as the distribution over variables in $G_{\rho_{A}}$ when
$\pi_{A}=\rho_{A}$. This is simply because their sub-models are equivalent.
The sense in which $G_{\rho_{A}}$ and $G^{\prime}_{\pi_{A}}$ are equivalent is
that any distribution induced in $G$ is also induced in one of the rows of
$G^{\prime}$.

The motivation for the conditional twin comes from trying to simulate
$\rho_{I}$ for $I=\\{A,B\\}$. The sub-model induced by $\rho_{I}$ on $G$ is
the graph in figure 2:

$A\leftarrow\rho_{A}(f_{A}(U_{A}))$
$B\leftarrow\rho_{B}(f_{B}(\rho_{A}(f_{A}(U_{A})),U_{B}))$
$Y\leftarrow f_{Y}(A,B,U_{Y})$

In $G^{\prime}$, it is impossible to design a soft intervention that both sets
$A\leftarrow\rho_{A}$ and $B\leftarrow\rho_{B}$. If it were possible, it would
have to include $\pi_{A}$ to make $A^{\prime}\leftarrow\pi_{A}(f_{A}(U_{A}))$.
Now, $\pi_{B}$ must take into account the value of $f_{B}$. Any soft-
intervention on $B^{\prime}$ will cut the arrow from $A^{\prime}$ to
$B^{\prime}$, making it impossible to get $f_{B}(A^{\prime})$. The only way to
simulate $G_{\rho_{I}}$ in $G^{\prime}_{\pi_{A}}$ is to perform a
counterfactual intervention $\rho_{B}$ on $B^{\prime}$.

We already know that we can simulate a single counterfactual intervention with
a soft-intervention on the twin graph. Since $\rho_{B}$ inputs $A^{\prime}$
and by necessity of $\rho_{B}$ accounting for $\pi_{A}$ which accounts for
$f_{A}(U_{A}))$, we create the twin with respect to the sub-graph
$G^{\prime}_{B^{\prime}Y^{\prime}}$. Conceptually, the direct effect of
$A^{\prime}$ on $Y^{\prime}$ has been decided. Only the value of $B^{\prime}$
is being intervened on. Thus, we can simulate the distribution of $Y^{\prime}$
in $G^{\prime}_{\pi_{A},\rho_{B}}$ with a soft-intervention on
$G^{\prime\prime}_{B^{\prime}Y^{\prime}}$, the twin graph of the sub-graph of
$G^{\prime}$ containing only the nodes $B^{\prime},Y^{\prime}$.

Figure 4: $G^{\prime\prime}=twin(G^{\prime}_{B^{\prime}Y^{\prime}}\mid
A^{\prime}=\pi_{A})$

Consider the soft-intervention $\pi_{B}=\rho_{B}$ on this graph

Figure 5: $G^{\prime\prime}_{\pi_{A}\pi_{B}}$

Now $\pi_{B}$ gets to see the natural value of $B$ conditional on $\pi_{A}$,
which was impossible before. Indeed, the distribution over $Y^{\prime\prime}$
in $G^{\prime\prime}$ is the same as the distribution over $Y_{\rho_{I}}$ for
$\rho_{I}=\pi_{I}$.

$Y^{\prime\prime}\leftarrow
f_{Y}(\pi_{A}(A),\pi_{B}(f_{B}(\pi_{A},U_{B})),U_{Y})$
is equivalent to
$Y_{\rho_{I}}\leftarrow
f_{Y}(\rho_{A}(A),\rho_{B}(f_{B}(\rho_{A},U_{B})),U_{Y})$

It should be further noted that neither $Y$ not $Y^{\prime}$ simulate any
distribution that cannot be simulated with $Y^{\prime\prime}$. So we could
simulate $Y_{\rho_{AB}}$ with the same $G^{\prime\prime}$ but having removed
the nodes $B,Y,Y^{\prime}$.

What remains is to formalize the construction of the conditional twin, so that
we can prove that the analog of $Y^{\prime\prime}$ for the general case can
simulate $Y_{\rho_{I}}$ for any $I$ on any SCM.

###  4.2 Formal Construction

A graph $G^{c}$ is the conditional twin of input $G,I$
$\iff$ it is the output of algorithm 1.

Input: $G$ and $I=\\{I_{1},...,I_{k}\\}\subseteq(V\setminus Y)$ s.t.
$i<j\implies I_{i}\notin An(I_{j})$ (Topological Order)

Output: a graph $G^{c}$ and a soft-intervention

$\pi_{I}=\\{\pi_{I^{\prime}_{j}}:i\in I_{j}\rightarrow\rho_{I_{j}}(i)\text{
for }I^{\prime}_{j}\in I^{\prime c}\\}$

such that $P_{G_{\rho_{I}}}(Y)=P_{G^{c}_{\pi_{I}}}(Y)$

In words, input a graph $G$ and a set of variables $I$ on which some
counterfactual-intervention $\rho_{I}$ can take place. We do not specify the
functional form of $\rho_{I}$. Output a conditional-twin graph $G^{c}$ and a
soft-intervention $\pi_{I}$. The sub-model $G^{c}_{\pi_{I}}$ has the same
distribution over variables as the sub-model $G_{\rho_{I}}$, regardless of the
functional form of $\rho_{I}$.

Algorithm 1 ConditionalTwin(G, I)

1\. Require $I=I_{1},\ldots,I_{k}$ in topological order
2\. if $I=\emptyset$: return G
3\. create node $I_{1}^{\prime}$ in G
4\. $I_{1}\xrightarrow{i_{1}}$ becomes
$I_{1}\xrightarrow{\pi_{I_{1}}(i_{1})}I_{1}^{\prime}\xrightarrow{i_{1}^{\prime}}$
5\. ConditionalTwin(G, $I=I_{2},\ldots,I_{k}$)

explanation:
(1) input $I$ in topological order w.r.t $G$.
(2) handle all intuition variables.
(3) add a node $I_{1}^{\prime}$ to $G$.
(4) In the functional forms of children of $I_{1}$, replace $I_{1}$ with
$I_{1}^{\prime}$. $I_{1}$ retains its parents, its only child is
$I_{1}^{\prime}$, and $I_{1}^{\prime}\leftarrow\pi_{I_{1}}(i_{1}\in I_{1})$ in
$F$. Once $\rho_{I}$ is defined, $\pi_{I_{1}}$ goes from the identity function
to $\pi_{I_{1}}=\rho_{I_{1}}$.
(5) recurse on $I$ with $I_{1}$ removed. In the jth iteration iteration,
$I_{j}$ will be $I_{1}$.

The conditional twin returned on our example $G$ is the following:

Figure 6: $G^{c}=\text{ConditionalTwin}(G,I=\\{A,B\\}$)

$G^{c}$ is similar to the graph $G^{\prime\prime}$ in figure 5 in that
$P_{G^{\prime\prime}}(Y^{\prime\prime})=P_{G^{c}}(Y)$. This is because they
have the same inputs in $F$. ConditionalTwin() does not include the
superfluous variables $B,Y,Y^{\prime}$, whose distributions can be simulated
by other variables in $G^{c}$. For example, simulate
$Y^{\prime}_{G^{\prime\prime}}$ with $Y_{G^{c}}$ by leaving $\pi_{B}(b)=b$ and
letting $\pi_{A}=\rho_{A}$.

In the next section, we show that Algorithm1 generalizes to any $G,I$. A
conditional twin and corresponding $\pi$ can always simulate the
counterfactual intervention.

###  4.3 Theorem 1: Counterfactual-Interventional Equivalence

Let $M:=<V,U,F,P(U)>$ be an arbitrary SCM with corresponding $G$.

$I:=\\{I_{1},...,I_{k}\\}\subseteq V\setminus Y$
$\rho_{I}:=\\{\rho_{I_{j}}:I_{j}\rightarrow I_{j}\\}$
$G^{c}:=\text{ConditionalTwin}(G,I)$
$\pi_{I}:=\\{\pi_{I_{j}}:I_{j}\rightarrow
I_{j}\mid\pi_{I_{j}}(i_{j})=\rho_{I_{j}}(i_{j})\\}$

Denote a distribution in $G$ under $\rho_{I}$ as $P_{\rho}(\dot{)}$ and a
distribution in $G^{c}$ under $\pi$ as $P_{\pi}()$. Denote a variable $N$ in
$G$ as $N$ and a variable $N$ in $G^{c}$ as $N^{c}$. The ’counterfactual copy’
of a variable $I_{j}\in I$ that exist in $G^{c}$ only, created by step 3 of
algorithm 1, is referred to as $I_{j}^{\prime}$. Lemma1
$P_{\rho}(I)=P_{\pi}(I^{\prime})$ for any $G,\rho_{I}$

Proof

Base Case

let $I=\\{I_{1}\\}$

Lemma1 is implied if $I_{1}$ has the same inputs as $I^{\prime}_{1}$ because
if they have the same inputs, they take the same value under any setting of
$U$.

$I_{1}\leftarrow\rho_{I_{1}}(f_{I_{1}}(Pa(I_{1}),U_{I_{1}}))$ by definition of
$\rho$

$I_{1}^{c}\leftarrow f_{I_{1}}(Pa(I_{1}),U_{I_{1}})$
$I^{\prime}_{1}\leftarrow\pi_{I_{1}}(I_{1})$
by construction of $G^{c}$

$\pi_{I_{1}}=\rho_{I_{1}}$ by definition of $\pi$
thus $I_{1}^{\prime}\leftarrow\rho_{I_{1}}(f_{I_{1}}(Pa(I_{1}),U_{I_{1}})$

Since their functional inputs are the same, the distributions are the same for
any $U$.

induction

let $k\geq 1$
$I=\\{I_{1},\ldots,I_{k}\\}\;$
$J=\\{I_{1},\ldots,I_{k},I_{j}\\}$
$I_{j}\in V$ and $I_{j}\notin An(I)$

Prove:
$P_{\rho_{I}}(I)=P_{\pi_{I}}(I^{\prime})\implies
P_{\rho_{J}}(J)=P_{\pi_{J}}(J^{\prime})$

let $GI^{c}$ = ConditionalTwin(G, I)
let $GJ^{c}$ = ConditionalTwin(G, J)

$GJ^{c}=\text{ConditionalTwin}(GI^{c},\\{I_{j}\\})$
because $I_{j}$ is the last element of topologically sorted $J$.

Consider the base case, where $G=GI^{c},I=\\{I_{j}\\}$. Since $I_{j}\notin
An(I)$, the intervention on $I_{j}$ cannot affect the distribution over $I$.
Thus, $P_{\rho_{J}}(J)=P_{\pi_{J}}(J^{\prime})$.

The distributions are equal for the first step of algorithm1 on arbitrary
$G,I$. It is a recursive algorithm, so the distributions remain equal for each
step. Theorem
$P_{\rho}(V)=P_{\pi}(V^{c}\setminus I_{1})$

Proof

For an arbitrary $I_{j}\in I$,
$P_{\rho}(I_{j})=P_{\pi}(I^{\prime}_{j})$ by lemma1
$De(I_{j})=De(I^{\prime}_{j})$ by construction of $G^{c}$.
Thus, $P_{\rho}(De(I_{j}))=P_{\pi}(De(I^{\prime}_{j}))$

Ancestors of $I$ and variables not connected to $I$ on any undirected path are
not affected by the intervention. By construction of $G^{c}$, they take the
same values in $G^{c}_{\pi}$ as they do in $G_{\rho}$.

##  5 Estimating A Counterfactual

We can calculate distributions under $\rho$ if we have the conditional twin.
We argue that realistic scenarios described by $G$ exist where $G^{c}$ can be
induced. We further show that a counterfactual distribution can be estimated
by the counterfactual intervention in the single-action case. We formulate but
leave open the question of whether a counterfactual distribution can be
estimated in the multi-action case.

###  5.1 Inducing the Conditional Twin

Doc is driving a car. He can turn the wheel left or right, represented by
variable $A\in\\{0,1\\}$. He gets reward $Y$ for not crashing. Both $A$ and
$Y$ are affected by environmental conditions $U_{AY}$.

Figure 7: $H$: Driving with Doc

Rob is a computer in the wheel who senses Doc’s choice and has the final say
of which direction the car goes. Sometimes he changes it, and sometimes he
doesn’t. Rob’s choice is represented by the node $A^{\prime}$, and his
decision-making algorithm is represented by $\pi_{A}$.

Figure 8: $H^{c}$: Driving with Doc and Rob

$H^{c}$ is the conditional twin of $H$. The assumptions are that road
conditions $U$ do not change in the time it takes to intervene on Doc’s
decision, and that Doc’s decision can be accurately sensed. In the single-
action case represented by graph $H$, we can show that estimating
$P(Y_{\rho_{A}})$ is the same as estimating $P(Y_{a^{\prime}}\mid a)$.

###  5.2 Single-Action

We can estimate $P(Y_{A^{\prime}=\pi_{A}}=1\mid A=a)$ in the standard way.

$P(Y_{\pi}=1)$ $=\frac{\displaystyle\text{frequency with which Y=1 under
}\pi}{\displaystyle\text{number of trials}}$

thus,

$\hat{P}_{H}(Y_{\rho_{A}}=1)$ $=\hat{P}_{H^{c}}(Y_{A^{\prime}=\pi_{A}}=1\mid
A=a)$ $=\frac{\displaystyle 1_{A=a,A^{\prime}=\pi_{A},Y=1}}{\displaystyle
1_{A=a,A^{\prime}=\pi_{a}}}$ (1) $\approx\sum\limits_{u\mid
A(u)=a,Y_{a^{\prime}}(u)=1}P(u)$ $=P(Y_{a^{\prime}}=1\mid a)$

Which is the counterfactual. The counterfactual is the natural regime when
$A^{\prime}=A$. By equation (1),

$P(Y_{A\neq a}=1\mid A=a)$ $\approx\frac{\displaystyle 1_{A=a,A^{\prime}\neq
a,Y=1}}{\displaystyle 1_{A=a,A^{\prime}\neq a}}$

We can estimate a counterfactual probability of $Y=1$ in $H$ by estimating the
frequency with which switching the value of $A$ in $H^{c}$ caused $Y=1$. This
is because the soft-intervention in $H^{c}$ is equivalent to the
counterfactual-intervention in $H$, and the counterfactual-intervention in $H$
is equivalent to the counterfactual distribution in $H$. The last part is open
is the multi-action case.

###  5.3 Multi-Action

Consider a similar story in $G$. Let’s say that $A$ is the turn-signal and $B$
is the wheel. Rob can intervene with $\pi=\\{\pi_{A},\pi_{B}\\}$.

Consider the familiar counterfactual

$P(Y_{A\neq a,B\neq b}=1\mid a,b)$ (2) $=\sum\limits_{u\mid
A=a,B=b,Y_{a^{\prime}b^{\prime}}(u)=1}P(u)$ $\neq\frac{\displaystyle
1_{A=a,A^{\prime}\neq a,B=b,B^{\prime}\neq b,Y=1}}{\displaystyle
1_{A=a,A^{\prime}\neq a,B=b,B^{\prime}\neq b}}$
$=\hat{P}_{H^{c}}(Y_{A^{\prime}\neq a,B^{\prime}\neq b}=1\mid A=a,B=b)$

The issue is that we can only observe $B$ after $A$ has a value. Formally,

Let $u_{ab}\in U_{ab}\subseteq U$ be an arbitrary element in the domain of $U$
that induces in $G$
$f_{A}(u_{ab})=a$
$f_{B}(u_{ab},b)=b$

The observation of $A=a,B=b$ in the natural regime is proof that the setting
of $u$ is a member of $U_{ab}$. Under $\rho_{I}$ however, the observation of
$B$ depends on the value of $\rho_{A}$. Thus, $A=a,B=b$ is not evidence that
$u\in U_{ab}$, unless $\rho_{A}(a)$ is always equal to $a$. This is because
$A$ is an ancestor of $B$, so we can only observe $B$ conditional on the value
of $\rho_{A}$.

However, we are not without recourse. Consider the derivation of the
probability of $Y_{\rho}$:

$P(Y_{\rho_{I=\\{AB\\}}}=1)$ $=\sum\limits_{a}P(Y_{\rho_{I}}=1\mid\
A=a)P(A=a)$ $=\sum\limits_{a}P(Y_{A\neq a,\rho_{B}}=y\mid\ A=a)P(A=a)$
$=\sum\limits_{ab}P(Y_{A\neq a,B\neq b}=1\mid A=a,B_{a^{\prime}}=b)$
$P(B_{a^{\prime}}=b\mid A=a)P(A=a)$
$=\bigg{[}\sum\limits_{u_{ab}}P(u)\bigg{]}\bigg{[}\sum\limits_{u_{b}}P(u)\bigg{]}\bigg{[}\sum\limits_{u_{a}}P(u)\bigg{]}$

where

$u_{ab}\mid A(u)=a\wedge B_{a^{\prime}}(u)=b\wedge
Y_{a^{\prime}b^{\prime}}(u_{3})=1$ $u_{b}\mid A(u)=a\wedge
B_{a^{\prime}}(u)=b$ $u_{a}\mid A(u)=a$

Each of the three pieces can be estimated.

$P(Y_{A\neq a,B\neq b}=1\mid A=a,B_{a^{\prime}}=b)$ $=\frac{\displaystyle
1_{A=a,A^{\prime}\neq a,B=b,B^{\prime}\neq b,Y=1}}{\displaystyle
1_{A=a,A^{\prime}\neq a,B=b,B^{\prime}\neq b}}$ $P(B_{a^{\prime}}=b\mid
A=a)=\frac{\displaystyle\mathds{1}\\{A=a,A\neq
a,B=b\\}}{\displaystyle\mathds{1}\\{A=a,A\neq a\\}}$
$P(A=a)=\frac{\displaystyle\mathds{1}\\{A=a\\}}{\displaystyle\mathds{1}\\{\text{True}\\}}$

These are estimators of the counterfactual intervention. Future work could
determine how to connect them to a counterfactual distribution.

##  6 Optimality Conditions for $\rho$

The computational costs associated with computing $\rho$ are strictly higher
than computing $\pi$ because the search space is bigger. For each observation,
$\rho$ decides on an intervention, whereas $\pi$ is merely an intervention. It
is therefore desirable to have graphical conditions for when $\rho$ could be
superior.

Consider an arbitrary graph $G$ and a variable $N$. We will discuss three
types of interventions:
$\rho$ denotes a counterfactual intervention in $G$
$\pi$ denotes the corresponding soft-intervention in $G^{c}$
$\sigma$ denotes a soft-intervention in $G$.

In general, $E[Y_{\rho}]\geq E[Y_{\sigma}]$ because $\rho$ has access to more
information than $\sigma$. We want to determine when
$E[Y_{\rho}]>E[Y_{\sigma}]$ because we want to know when the counterfactual
intervention is better than an experiment.

Let

$\rho:f_{N}\rightarrow P(N)$
$\rho^{*}=\operatorname*{arg\,max}\limits_{\rho}E_{G_{\rho}}[Y]$
$\pi:N\rightarrow P(N^{\prime})\text{ in }G^{c}\text{ mimic }\rho$
$\pi^{*}=\operatorname*{arg\,max}\limits_{\rho}E_{G^{c}_{\pi}}[Y]$

Theorem 1 implies Corollary 1

$E_{G_{\rho^{*}}}[Y]=E_{G_{\pi^{*}}^{c}}[Y]$

Let

$\sigma:\emptyset\rightarrow P(n\in N)\text{ in }G$
$\sigma^{*}=\operatorname*{arg\,max}\limits_{\sigma}E_{G_{\sigma}}[Y]$
$\rho_{\emptyset}:\emptyset\rightarrow P(N)$
$\pi_{\emptyset}:\emptyset\rightarrow P(N^{\prime})\text{ in }G^{c}\text{
mimic }\rho_{\emptyset}$

The counterfactual intervention $\rho_{\emptyset}$ completely ignores $f_{N}$.
It inputs $f_{N}$ but does not use it to construct $P(N)$. The will be no
arrow between $I$ and $I^{\prime}$ in the conditional-twin under
$\pi_{\emptyset}$.

Theorem 1 implies Corollary 2

$E_{G_{\rho^{*}_{\emptyset}}}[Y]=E_{G^{c}_{\pi^{*}_{\emptyset}}}[Y]$

By the Corollaries,

$E_{G_{\rho^{*}}}[Y]=E_{G^{c}_{\pi^{*}}}[Y]$
$E_{G_{\sigma^{*}}}[Y]=E_{G_{\rho_{\emptyset}^{*}}}[Y]=E_{G^{c}_{\pi^{*}_{\emptyset}}}[Y]$

Thus

$E_{G_{\rho^{*}}}[Y]>E_{G_{\sigma^{*}}}[Y]\iff$
$E_{G^{c}_{\pi^{*}}}[Y]>E_{G^{c}_{\pi^{*}_{\emptyset}}}[Y]$ (3)

In words, the optimal counterfactual intervention is better than the optimal
experiment if and only if the optimal $\pi$ in the conditional-twin is better
than the optimal experiment in the conditional-twin.

$\pi$ inputs strictly more information than $\pi_{\emptyset}$ because $\pi$
inputs $N$. Thus, (3) holds when the $\textit{increase in E[Y] of observing
}N>0$.

Definition: Value of Observation (VO)
Let $\pi_{I}$ be a soft-intervention on a set of variables $I$ in a causal
graph $G$.

$\text{VO}(N):=E[Y\ ;\ \pi_{I}]-E[Y\ ;\ \pi_{I\setminus N}]$

Thus d-separation is a sufficient condition for $VO(N)$ to be zero.

$P(Y_{\pi}\mid N)=P(Y_{\pi})\implies VO(N)=0$

Note that the reverse is not true: the value of a $N$ may be zero and be
d-connected with $Y$. For example, when $N$ points to $Y$ but $f_{Y}=1$. Thus,
this condition only tells us when the counterfactual intervention could be
better than an experiment.

This result extends to the multi-action case because of the recursive
construction of the conditional twin. If the $VO$ of a single variable is not
0, then the counterfactual intervention will be better than the empty-soft-
intervention. Only when the $VO$ of all variables is 0 does (3) have equality.

##  7 Conclusion and Future Work

We define $\rho$ and give conditions under which it could be superior to
$\sigma$. The point is that an agent that employs an experimental procedure
cannot be sure that they incur sub-linear regret, even after many samples, if
the conditions hold. These environments require a different policy-space that
accounts for the natural state of the system, which we call the
counterfactual-intervention $\rho$. In the sequential-action case, $\rho$ can
be understood as a soft-intervention on a graph called the condition-twin.
This observation provides the theoretical basis for estimating counterfactuals
using layer 2 data.

Future work should try to connect $\rho$ with counterfactual distributions. If
that can be done, then we will have a pipeline for computing counterfactuals
with layer 2: $\pi$ on $G^{c}\rightarrow\rho$ on $G\rightarrow$?
counterfactual distribution. A good starting place would be to prove that any
single-intervention counterfactual distribution can be estimated in the
conditional-twin. Extensions of the $\rho$ policy-space to account for
ancestors would also be a good idea.

## References

  * [Elias Bareinboim and Judea Pearl2015]  [1] Elias Bareinboim and Judea Pearl  2015\.  Bandits with Unobserved Confounders. Advances in Neural Information Processing Systems 28 (NIPS 2015).
  * [Junzhe Zhang and Elias Bareinboim2022]  [2] Junzhe Zhang and Elias Bareinboim  2022\.  Can Humans be out of the Loop? CLeaR 2022.
  * [ Judea Pearl2009]  [3] Judea Pearl  2009\.  Causality: Models, Reasoning, and Inference (Cambridge Univ Press, New York), 2nd Ed
  * [Elias Bareinboim and Judea Pearl2015]  [4] Elias Bareinboim and Judea Pearl  2015\.  Causal Inference and the Data-Fusion Problem Proceedings of the National Academy of Sciences 2015
  * [Juan Correa and Elias Bareinboim2020]  [5] Juan Correa and Elias Bareinboim  2020\.  A Calculus for Stochastic Interventions: Causal Effect Identification and Surrogate Experiments Association for the Advancement of Artificial Intelligence


# A lower bound for the $n$-queens problem

Zur Luria  Software Department, Azrieli College of Engineering, Jerusalem,
Israel<EMAIL_ADDRESS>and  Michael Simkin  Harvard University Center of
Mathematical Sciences and Applications, Cambridge, MA, USA.
<EMAIL_ADDRESS>
###### Abstract.

The $n$-queens puzzle is to place $n$ mutually non-attacking queens on an
$n\times n$ chess board. We present a simple randomized algorithm to construct
such configurations. We first use a random greedy algorithm to construct an
approximate toroidal $n$-queens configuration. In this well-known variant the
diagonals wrap around the board from left to right and from top to bottom. We
show that with high probability this algorithm succeeds in placing $(1-o(1))n$
queens on the board. Furthermore, by making only a small number of
modifications one can obtain a solution to the non-toroidal problem. By
counting the number of choices available at each step of the random greedy
algorithm we conclude that there are more than
$\left(\left(1-o(1)\right)ne^{-3}\right)^{n}$ solutions to the $n$-queens
problem. This proves a conjecture of Rivin, Vardi, and Zimmerman in a strong
form.

##  1\. Introduction

An $n$-queens configuration is a placement of $n$ mutually non-threatening
queens on an $n\times n$ chessboard. Equivalently, this is an order-$n$
permutation matrix in which the sum of each diagonal is at most $1$.

Let ${\mathcal{Q}}(n)$ be the number of solutions to the $n$-queens puzzle.
The problem of determining ${\mathcal{Q}}(n)$ was posed in 1848 by German
chess enthusiast Max Bezzel (specifically for $n=8$). It soon attracted the
attention of several eminent mathematicians including Gauss. For more on the
history of the problem, as well as a survey of results and a list of open
problems, we refer the reader to Bell and Stevens [1].

To date, the best known upper bound on ${\mathcal{Q}}(n)$ is due to the first
author [8, Theorem 1.4]: for $\alpha=1.587$, it holds that
${\mathcal{Q}}(n)\leq\left(\left(1+{o\left(1\right)}\right)ne^{-\alpha}\right)^{n}$.

As for lower bounds, it is not immediately obvious that ${\mathcal{Q}}(n)>0$
for all (large enough) $n$. Pauls [10, 11] showed that this holds for all
$n\geq 4$. Thus, ${\mathcal{Q}}(n)=\Omega(1)$, and to our knowledge this is
the best known general lower bound. Rivin, Vardi, and Zimmerman [12, Theorem
1] gave an exponential lower bound on ${\mathcal{Q}}(n)$ that holds for a
dense set of integers, and the first author [8, Theorem 1.1] showed that for
infinitely many $n$, the superexponential bound ${\mathcal{Q}}(n)\geq
n^{n/16-o(n)}$ holds. It is interesting to note that these lower bounds are
actually due to constructions of solutions to the toroidal $n$-queens puzzle,
in which the diagonals wrap around the board from left to right and from top
to bottom. In this paper we show the following lower bound on
${\mathcal{Q}}(n)$.

######  Theorem 1.1.

For all natural numbers $n$,

${\mathcal{Q}}(n)\geq\left(\left(1-{o\left(1\right)}\right)\frac{n}{e^{3}}\right)^{n}.$

As a consequence of Theorem 1.1 and the trivial bound ${\mathcal{Q}}(n)\leq
n!$, we conclude that

$\lim_{n\to\infty}\frac{\log{\mathcal{Q}}(n)}{n\log n}=1.$

This proves, in a strong form, a conjecture of Rivin, Vardi, and Zimmerman
[12, Conjecture 1] who conjectured that the limit above is positive.

We prove Theorem 1.1 by describing a probabilistic algorithm to construct
solutions to the $n$-queens puzzle. We formally describe the algorithm in
Section 2, and we give a brief overview here. The algorithm has two phases.
The first is a random greedy algorithm that constructs an approximate toroidal
$n$-queens configuration, where the diagonals wrap around the board from left
to right and from top to bottom. We call such diagonals toroidal diagonals.
Beginning with an empty board, we repeatedly place queens uniformly at random
subject to the constraint that they may share a row, column, or toroidal
diagonal. We show that with high probability this algorithm succeeds in
placing ${(1-o(1))n}$ queens on the board. This phase of the algorithm, which
is analyzed in Section 3, also gives the enumeration used to prove Theorem
1.1. In the second phase of the algorithm we use absorbers to perform a small
number of modifications and obtain a complete solution. The absorbing phase is
analyzed in Section 4.

Random greedy algorithms have proved to be a powerful tool when constructing
constrained combinatorial objects. To name just a few examples, they have been
used to construct regular graphs [13], triangle Ramsey graphs [2], and high-
girth approximate Steiner triple systems [5, 3]. Combined with absorbers, they
also played important roles in the recent constructions of combinatorial
designs [6, 4]. In the latter example, a random greedy algorithm was the key
to obtaining lower bounds on the count of the associated objects [7].

In the random greedy phase of the algorithm it would be natural to choose each
queen uniformly at random subject to the constraint that it may not share a
row, column, or (non-toroidal) diagonal with a previously placed queen.
However, we have found this algorithm challenging to analyze. The difficulty
is due to the fact that the lengths of the diagonals vary, leading to a non-
uniform distribution of the queens. In contrast, toroidal diagonals all have
the same length. This simplifies the analysis of the random greedy algorithm.
However, this likely means that the bound in Theorem 1.1 is not tight.

###  1.1. Notation and terminology

We adopt the standard notation $[n]:=\\{1,...,n\\}$. Also, we write $a=b\pm c$
as a shorthand for $b-|c|\leq a\leq b+|c|$.

Throughout, all asymptotics are with $n\to\infty$ and the other parameters
fixed. Since we are concerned only with asymptotic statements we assume that
$n$ is sufficiently large for relevant inequalities to hold. For example, we
may write $n^{2}-n>n$ without explicitly requiring $n>2$.

We say that a sequence of events occurs with high probability (w.h.p.) if the
probabilities of their occurrence tend to $1$. Typically, we will abuse
terminology and say that a specific event occurs w.h.p. while leaving the
sequential statement to be inferred from context.

To formally define the classical and toroidal $n$ queens problems, we identify
the $n\times n$ chessboard with $[n]^{2}$. In the classical problem, a queen
at $(x,y)$ attacks all squares $(x^{\prime},y^{\prime})$ such that either
$x^{\prime}=x$, $y^{\prime}=y$, $x^{\prime}+y^{\prime}=x+y$, or
$x^{\prime}-y^{\prime}=x-y$. In the toroidal problem, these equations are
replaced by equalities modulo $n$. The toroidal diagonals containing the
square $(x,y)$ are
$\\{(x^{\prime},y^{\prime})\in[n]^{2}:x^{\prime}+y^{\prime}=x+y\bmod n\\}$ and
$\\{(x^{\prime},y^{\prime})\in[n]^{2}:x^{\prime}-y^{\prime}=x-y\bmod n\\}$.
Note that there are $n$ toroidal diagonals of each type, all of size $n$. A
partial (toroidal) $n$-queens configuration is a set $Q\subset[n]^{2}$ such
that every row, column, and (toroidal) diagonal contains at most one element
of $Q$. A (toroidal) $n$-queens configuration is a partial (toroidal)
$n$-queens configuration of size $n$. Note that in the toroidal case, this
implies that every toroidal diagonal contains exactly one queen.

##  2\. A randomized construction of $n$-queens configurations

In this section we formally introduce the algorithm we use to construct
$n$-queens configurations. As mentioned in the introduction, the we begin by
using a random greedy algorithm to construct a partial toroidal $n$-queens
configuration.

Fix (a sufficiently large) $n\in\mathbb{N}$, and set

$\alpha=10^{-4},\quad T=\lfloor(1-n^{-\alpha})n\rfloor.$

######  Algorithm 2.1.

  * •

Set $Q(0)=\emptyset$.

  * •

For each $0\leq t<T$, let ${\mathcal{A}}(t)\subseteq[n]^{2}$ be the set of
available positions, i.e., those positions lying in a row, column, and
toroidal diagonals unoccupied by $Q(t)$.

  * •

If ${\mathcal{A}}(t)=\emptyset$, abort.

  * •

Otherwise, choose $(x_{t},y_{t})\in{\mathcal{A}}(t)$ uniformly at random and
independently of previous choices and set
$Q(t+1)=Q(t)\cup\\{(x_{t},y_{t})\\}$.

For technical reasons, if the algorithm aborts at time $t$, then for every
$t<s\leq T$ we set $Q(s)=Q(t)$.

In Proposition 3.1 we show that w.h.p. Algorithm 2.1 does not abort. In the
next phase of the algorithm we hope to remove a small number of queens from
the board, and then complete the puzzle. The key is the idea of absorption,
which we now illustrate: Suppose $Q\subseteq[n]^{2}$ is a partial $n$-queens
placement that does not cover row $r$ and column $c$. We wish to obtain a
partial $n$-queens placement $Q^{\prime}$ that covers all rows and columns
covered by $Q$, and also covers row $r$ and column $c$. We might try adding
$(r,c)$ to $Q$, but if either of the diagonals running through $(r,c)$ is
occupied this will not work. Instead, we will look for a queen $(x,y)\in Q$
that satisfies:

  1. (a)

$(r,y)$ and $(x,c)$ do not share a diagonal (equivalently, $(r,c)$ and $(x,y)$
do not share a diagonal),

  2. (b)

none of the diagonals containing $(r,c)$ or $(x,y)$ are occupied.

Supposing such a queen exists, we observe that
$Q^{\prime}\coloneqq\left(Q\setminus\\{(x,y)\\}\right)\cup\\{(r,y),(x,c)\\}$
is a partial $n$-queens configuration satisfying the conditions above. In this
way, we have absorbed row $r$ and column $c$ into our configuration. We call
such a queen an absorber for $(r,c)$ in $Q$. We denote the set of absorbers
for $(r,c)$ in $Q$ by ${\mathcal{B}}_{Q}(r,c)$.

The following algorithm attempts to use absorbers to complete $Q(T)$ (the
outcome of Algorithm 2.1).

######  Algorithm 2.2.

  * •

Let $L_{R}$ and $L_{C}$ be, respectively, the sets of rows and columns not
covered by $Q(T)$. Note that $|L_{R}|=|L_{C}|\eqqcolon k$.

  * •

Let $M=(r_{1},c_{1}),(r_{2},c_{2}),\ldots,(r_{k},c_{k})$ be an arbitrary
matching of $L_{R}$ and $L_{C}$.

  * •

Set $R(0)\coloneqq Q(T)$.

  * •

For $i=1,2,\ldots,k$:

    * –

If ${\mathcal{B}}_{i}\coloneqq{\mathcal{B}}_{R(i-1)}(r_{i},c_{i})=\emptyset$
abort.

    * –

Otherwise, choose some $(x_{i},y_{i})\in{\mathcal{B}}_{i}$ and set
$R(i)\coloneqq\left(Q(i-1)\setminus\\{(x_{i},y_{i})\\}\right)\cup\\{(x_{i},c_{i}),(r_{i},y_{i})\\}$.

Clearly, if Algorithm 2.2 does not abort then $R(k)$ is an $n$-queens
configuration. In Section 4 we show that w.h.p. $Q(T)$ satisfies a
combinatorial condition that guarantees the success of Algorithm 2.2.

##  3\. Random queens on a torus

In this section we analyze Algorithm 2.1.

For $0\leq t\leq T$ define the functions

$p(t)=1-\frac{t}{n},\quad\varepsilon(t)=n^{0.51}\left(p(t)^{-50}-1\right).$

We refer to rows, columns, and toroidal diagonals collectively as lines. Let
${\mathcal{L}}$ be the set of lines. We note that $|{\mathcal{L}}|=4n$ and
that each line has length $n$. For each $\ell\in{\mathcal{L}}$ and $0\leq
t\leq T$, let $S_{\ell}(t)$ denote the number of available elements in line
$\ell$ at time $t$. We say that a line is occupied at time $t$ if $Q(t)$
contains a position in the line.

######  Proposition 3.1.

The following holds with probability
$1-\exp\left(-\Omega\left(n^{0.01}\right)\right)$. For every
$\ell\in{\mathcal{L}}$ and $0\leq t\leq T$, as long as line $\ell$ is
unoccupied, it holds that

$S_{\ell}(t)=np(t)^{3}\pm\varepsilon(t).$

Additionally, with probability
$1-\exp\left(-\Omega\left(n^{0.01}\right)\right)$, for every $0\leq t\leq T$,
it holds that $|{\mathcal{A}}(t)|=n^{2}p(t)^{4}\pm np(t)\varepsilon(t)$.

A particular consequence of this proposition is that with probability
$1-\exp\left(-\Omega\left(n^{0.01}\right)\right)$ the algorithm does not
abort. This is because for large enough $n$, for every $0\leq t\leq T$ there
holds $n^{2}p(t)^{4}-np(t)\varepsilon(t)>0$.

Proposition 3.1 can be interpreted as follows: For every $t$ and every line
$\ell\in{\mathcal{L}}$, the probability that line $\ell$ is unoccupied at time
$t$ is $p(t)$. If we adopt the heuristic that for every position, the events
that the four lines containing it are unoccupied at time $t$ are independent,
then the probability that it is available is $p(t)^{4}$. Hence, the expected
number of available positions is $n^{2}p(t)^{4}$. If we condition on a
specific line being unoccupied, then the expected number of available
positions in it is $np(t)^{3}$.

We will use the following version of the Azuma-Hoeffding inequality.

######  Theorem 3.2 ([15, Lemma 1]).

Let $X_{0},X_{1},\ldots$ be a supermartingale with respect to a filtration
${\mathcal{F}}_{0},{\mathcal{F}}_{1},\ldots$. For every $i\in\mathbb{N}$, let
$a_{i}$ satisfy $a_{i}\geq|X_{i}-X_{i-1}|$. Then, for every $\lambda>0$ and
$t\geq 0$, it holds that

${\mathbb{P}}\left[X_{t}\geq
X_{0}+\lambda\right]\leq\exp\left(-\frac{\lambda^{2}}{2\sum_{i=1}^{t}a_{i}^{2}}\right).$

###### Proof of Proposition 3.1.

For convenience, we define the function

$s(t)=np(t)^{3}.$

Let the stopping time $\tau$ be the smallest time $t\leq T$ at which there
exists some $\ell\in{\mathcal{L}}$ that is unoccupied and
$\left|S_{\ell}(t)-s(t)\right|>\varepsilon(t)$. Set $\tau=T+1$ if there is no
such time. It suffices to show that $\tau=T+1$ with sufficiently high
probability.

Note that for $t<\tau$, there are $n-t=np(t)$ unoccupied rows. In each, there
are $s(t)\pm\varepsilon(t)=np(t)^{3}\pm\varepsilon(t)$ available positions
(where we have used the fact that $\tau>t$). Thus,

(1)
$|{\mathcal{A}}(t)|=np(t)\left(np(t)^{3}\pm\varepsilon(t)\right)=n^{2}p(t)^{4}\pm
np(t)\varepsilon(t).$

For every $\ell\in{\mathcal{L}}$, we also define the time $\tau_{\ell}$ as the
minimum between $\tau$ and the last time at which line $\ell$ is unoccupied.
For every $\ell\in{\mathcal{L}}$, we define the shifted random variables

$S_{\ell}^{+}(t)=\begin{cases}S_{\ell}(t)-s(t)-\frac{1}{2}\varepsilon(t)&\tau_{\ell}\geq
t\\\ S_{\ell}^{+}(t-1)&\text{otherwise}\end{cases}$

and

$S_{\ell}^{-}(t)=\begin{cases}s(t)-S_{\ell}(t)-\frac{1}{2}\varepsilon(t)&\tau_{\ell}\geq
t\\\ S_{\ell}^{-}(t-1)&\text{otherwise}\end{cases}.$

The motivation of freezing the random variables at time $\tau$ is to ease the
calculation of the expected one-step change: On the one hand, if $t<\tau$,
then $Q(t)$ has a regularity that facilitates this calculation. On the other,
if $t\geq\tau$, then the one-step change is definitionally zero. Additionally,
at the moment $\ell$ becomes occupied, $S_{\ell}$ jumps to $0$. Thus, we
cannot expect $S_{\ell}$ itself to follow a smooth trajectory. This is the
reason we freeze the random variables at time $\tau_{\ell}$.

We note that $\tau\leq T$ only if for some $\ell\in{\mathcal{L}}$ and some
$0\leq t\leq T$ one of $S_{\ell}^{+}(t)$ or $S_{\ell}^{-}(t)$ is greater than
$\varepsilon(t)/2$. This is the event whose probability we will bound.

We now show that $\\{S_{\ell}^{+}(t)\\}_{t=0}^{T}$ and
$\\{S_{\ell}^{-}(t)\\}_{t=0}^{T}$ are supermartingales with respect to the
filtration $\\{Q(t)\\}_{t=0}^{T}$ induced by the random greedy algorithm. We
first observe that for every $t<T$ it holds that
$|S_{\ell}^{+}(t+1)-S_{\ell}^{+}(t)|,|S_{\ell}^{-}(t+1)-S_{\ell}^{-}(t)|=O(1)$.
Indeed, when placing a queen on the board, it occupies exactly four lines.
Each of these intersects a given line in exactly one position. Thus,
$|S_{\ell}(t+1)-S_{\ell}(t)|\leq 4$. Additionally, by their definitions,
$s(t)$ and $\varepsilon(t)$ change by only $O(1)$ in each time step.

Next, we calculate expected one-step changes. If $t\geq\tau_{\ell}$ then, by
definition, the expected change is $0$. It remains to show that, conditioning
on $\tau>t$ and line $\ell$ remaining unoccupied at time $t+1$, the expected
one-step change is non-positive. Consider a position $(r,c)$ in line $\ell$
that is available at time $t$. It becomes unavailable at time $t+1$ if and
only if one of the four lines containing it is occupied at time $t$. Since
$\tau>t$, each of these lines contains $s(t)\pm\varepsilon(t)$ available
positions, and they intersect only at $(r,c)$. Let $B$ be the event that line
$\ell$ is unoccupied at time $t+1$. Observe that conditioning on $\tau>t$ and
$B$ implies that $(x_{t+1},y_{t+1})$ is chosen uniformly from among

$|{\mathcal{A}}(t)|-S_{\ell}(t)\stackrel{{\scriptstyle\text{\eqref{eq:total
available},
$t<\tau$}}}{{=}}n^{2}p(t)^{4}-np(t)^{3}\pm\left(np(t)\varepsilon(t)+\varepsilon(t)\right)=n^{2}p(t)^{4}\pm
3np(t)\varepsilon(t)$

positions. Finally, since we condition on $B$, there are
$3(s(t)\pm\varepsilon(t))\pm O(1)=3s(t)\pm 4\varepsilon(t)$ positions that, if
chosen at time $t+1$, make $(r,c)$ unavailable. Thus:

${\mathbb{P}}\left[(r,c)\notin{\mathcal{A}}(t+1){|}\tau>t,B\right]=\frac{3s(t)\pm
4\varepsilon(t)}{n^{2}p(t)^{4}\pm
3np(t)\varepsilon(t)}=\frac{3}{np(t)}\left(1\pm\frac{5\varepsilon(t)}{np(t)^{3}}\right).$

Therefore

$\displaystyle{\mathbb{E}}\left[S_{\ell}(t+1)-S_{\ell}(t){|}\tau>t,B\right]$
$\displaystyle=-S_{\ell}(t)\frac{3}{np(t)}\left(1\pm\frac{5\varepsilon(t)}{np(t)^{3}}\right)$
$\displaystyle\stackrel{{\scriptstyle\tau>t}}{{=}}-\left(s(t)\pm\varepsilon(t)\right)\frac{3}{np(t)}\left(1\pm\frac{5\varepsilon(t)}{np(t)^{3}}\right)$
$\displaystyle=-3p(t)^{2}\left(1\pm\frac{7\varepsilon(t)}{np(t)^{3}}\right)=-3p(t)^{2}\pm\frac{21\varepsilon(t)}{np(t)}.$

We also observe that

$s(t+1)-s(t)=-\frac{3np(t)^{2}}{n}\pm\frac{6}{n}=-3p(t)^{2}\pm\frac{\varepsilon(t)}{np(t)}$

and that

$\frac{1}{2}\left(\varepsilon(t+1)-\varepsilon(t)\right)=\frac{50\varepsilon(t)}{2np(t)}\pm\frac{\varepsilon(t)}{np(t)}.$

Therefore:

${\mathbb{E}}\left[S_{\ell}^{+}(t+1)-S_{\ell}^{+}(t){|}{\mathcal{F}}_{t}\right]=-3p(t)^{2}+3p(t)^{2}-\frac{50\varepsilon(t)}{2np(t)}\pm\frac{23\varepsilon(t)}{np(t)}\leq
0$

and

${\mathbb{E}}\left[S_{\ell}^{-}(t+1)-S_{\ell}^{-}(t){|}{\mathcal{F}}_{t}\right]=3p(t)^{2}-3p(t)^{2}-\frac{50\varepsilon(t)}{2np(t)}\pm\frac{23\varepsilon(t)}{np(t)}\leq
0.$

We conclude that $\\{S_{\ell}^{+}(t)\\}_{t=0}^{T}$ and
$\\{S_{\ell}^{-}(t)\\}_{t=0}^{T}$ are supermartingales with maximal one-step
change $O(1)$.

We now apply Theorem 3.2 with $\lambda=\varepsilon(t)/2$ to conclude that for
every $0\leq t\leq T$:

$\displaystyle{\mathbb{P}}\left[S_{\ell}^{+}(t)\geq
S_{\ell}^{+}(0)+\varepsilon(t)/2\right]$
$\displaystyle\leq\exp\left(-\Omega\left(\frac{n^{1.02}}{np(t)^{100}}\right)\right)$
$\displaystyle\leq\exp\left(-\Omega\left(\frac{n^{1.02}}{np(T)^{100}}\right)\right)=\exp\left(-\Omega\left(n^{0.01}\right)\right).$

Similarly:

${\mathbb{P}}\left[S_{\ell}^{-}(t)\geq
S_{\ell}^{-}(0)+\varepsilon(t)/2\right]\leq\exp\left(-\Omega\left(n^{0.01}\right)\right).$

Hence:

${\mathbb{P}}\left[\tau\leq
T\right]\leq\exp\left(-\Omega\left(n^{0.01}\right)\right),$

completing the proof. ∎

##  4\. Absorbers

In this section we analyze Algorithm 2.2. We wish to show that it is unlikely
to abort. The next lemma provides a sufficient condition.

######  Definition 4.1.

Let $\ell>0$. A partial $n$-queens configuration $Q$ is $\ell$-absorbing if
for every $(r,c)\in[n]^{2}$, it holds that
$\left|{\mathcal{B}}_{Q}(r,c)\right|\geq\ell$.

######  Lemma 4.2.

Suppose $|Q(T)|=T$ and $Q(T)$ is $10(n-T)$-absorbing. Then Algorithm 2.2 does
not abort.

###### Proof.

Let $k=n-T$. Algorithm 2.2 aborts only if for some $t$ we have
$\left|{\mathcal{B}}_{R(t)}(r_{t},c_{t})\right|=0$. Thus, if for every $0\leq
t<k$ it holds that $\left|{\mathcal{B}}_{R(t)}(r_{t},c_{t})\right|\geq
10k-9t$, then the algorithm does not abort.

We prove this inductively. Let $(r,c)\in[n]^{2}$. By assumption,
$|{\mathcal{B}}_{R(0)}(r,c)|\geq 10k$. Now assume that for $0\leq t<k-1$ it
holds that $|{\mathcal{B}}_{R(t)}|\geq 10k-9t$. We wish to show that
$|{\mathcal{B}}_{R(t+1)}|\geq 10k-9t-9$. We note that $R(t+1)$ is obtained
from $R(t)$ by removing one queen and adding two queens. Thus, the conclusion
follows from the following two observations regarding partial $n$-queens
configurations $P_{1},P_{2}\subseteq[n]^{2}$:

  * •

If $P_{2}$ is obtained from $P_{1}$ by removing a queen then
$|{\mathcal{B}}_{P_{2}}(r,c)|\geq|{\mathcal{B}}_{P_{1}}(r,c)|-1$. Indeed, if
$(x,y)\in{\mathcal{B}}_{P_{1}}(r,c)$ then it does not share a diagonal with
$(r,c)$ and the four diagonals passing through $(r,y),(x,c)$ are unoccupied.
Since $P_{2}\subseteq P_{1}$, these facts hold in $P_{2}$ as well. Thus, if
$(x,y)\in P_{2}$ then $(x,y)\in{\mathcal{B}}_{P_{2}}(r,c)$. Since
$|P_{1}\setminus P_{2}|=1$, the conclusion follows.

  * •

If $P_{2}$ is obtained from $P_{1}$ by adding a queen then
$|{\mathcal{B}}_{P_{2}}(r,c)|\geq|{\mathcal{B}}_{P_{1}}(r,c)|-4$. Indeed,
suppose
$(x,y)\in{\mathcal{B}}_{P_{1}}(r,c)\setminus{\mathcal{B}}_{P_{2}}(r,c)$. Let
$(q_{r},q_{c})$ be the additional queen that is present in $P_{2}$. By
assumption, $(x,y)$ does not share a diagonal with $(r,c)$ and $(x,y)\in
P_{2}$. Since $(x,y)\notin{\mathcal{B}}_{P_{2}}(r,c)$, this means that one of
the diagonals containing $(r,y)$ or $(x,c)$ is occupied by $(q_{r},q_{c})$.
Therefore, one of the following holds:

$q_{r}+q_{c}=r+y,\quad q_{r}+q_{c}=x+c,\quad q_{r}-q_{c}=r-y,\quad
q_{r}-q_{c}=x-c.$

Since $r,c,q_{r},q_{c}$ are fixed, each equality has at most one solution in
$[n]$. Now, for each $x$ that solves one of the equations, there is at most
one $y$ such that $(x,y)\in P_{1}$ (since $P_{1}$ contains at most one queen
in each column). Similarly, for each $y$ solving one of the equations there is
at most one $x$ such that $(x,y)\in P_{1}$. Therefore there are at most $4$
absorbers $(x,y)\in{\mathcal{B}}_{P_{1}}(r,c)$ for which one of the equalities
holds.

∎

The next lemma asserts that w.h.p. $Q(T)$ contains $\Omega(n)$ absorbers for
every position. By Proposition 3.1, w.h.p. $n-|Q(T)|=n-T=o(n)$. Thus, it then
follows from Lemma 4.2 that Algorithm 2.2 succeeds in constructing an
$n$-queens configuration.

######  Lemma 4.3.

There exists a constant $\beta>0$ such that w.h.p. $Q(T)$ is $(\beta
n)$-absorbing.

The intuition is that $Q(T)$ contains approximately $n$ queens, each occupying
a single diagonal of each type (that is, one diagonal from upper-left to
lower-right and one from upper-right to lower-left). However, the grid
$[n]^{2}$ contains approximately $2n$ diagonals of each type. Therefore, if
one chooses a diagonal uniformly at random the probability that it is
unoccupied is approximately $1/2$. If we fix $(r,c)$ and choose $(x,y)\in
Q(T)$ uniformly at random, we might imagine that the (four) diagonals
containing $(r,y)$ and $(x,c)$ are distributed uniformly at random, which
would imply that with constant probability they are unoccupied.

One approach to proving Lemma 4.3 is to track $|{\mathcal{B}}_{Q(t)}(r,c)|$
for each $(r,c)\in[n]^{2}$ and each $0\leq t\leq T$. This would give a precise
count of $|{\mathcal{B}}_{Q(t)}(r,c)|$ but at the cost of significant
technical work. We take a different tack, giving a shorter proof at the
expense of a suboptimal $\beta$. We show that already at an early stage of the
process w.h.p. there are $\Omega(n)$ absorbers for each position. Furthermore,
each of these absorbers is guaranteed to be present in $Q(T)$. We begin by
identifying a combinatorial property that ensures an absorber survives
throughout the random greedy process.

We will need the following notation: Let $(r,c)\in[n]^{2}$. Let
${\ell_{1}^{\text{tor}}}(r,c)\coloneqq\\{(x,y)\in[n]^{2}:r+c=x+y\bmod
n\\},{\ell_{2}^{\text{tor}}}(r,c)\coloneqq\\{(x,y)\in[n]^{2}:r-c=x-y\bmod
n\\}$ be the two toroidal diagonals incident to $(r,c)$, and let
$\ell_{1}(r,c)\subseteq{\ell_{1}^{\text{tor}}}(r,c),\ell_{2}(r,c)\subseteq{\ell_{2}^{\text{tor}}}(r,c)$
be the two non-toroidal diagonals incident to $(r,c)$. For $i=1,2$ we also
define
${\ell_{i}^{\text{far}}}(r,c)\coloneqq{\ell_{i}^{\text{tor}}}(r,c)\setminus\ell_{i}(r,c)$.

######  Definition 4.4.

Let $Q\subseteq[n]^{2}$ be a partial $n$-queens configuration. Let
$(r,c)\in[n]^{2}$. An absorber $(x,y)\in{\mathcal{B}}_{Q}(r,c)$ is safe if the
four toroidal diagonals containing $(r,y)$ and $(x,c)$ are all occupied by
$Q$. Equivalently, $(x,y)\in{\mathcal{B}}_{Q}(r,c)$ is safe if there exist
$a_{1}\in{\ell_{1}^{\text{far}}}(r,y),a_{2}\in{\ell_{2}^{\text{far}}}(r,y),b_{1}\in{\ell_{1}^{\text{far}}}(x,c),b_{2}\in{\ell_{2}^{\text{far}}}(x,c)$
such that $a_{1},a_{2},b_{1},b_{2}\in Q$. (see Figure 1).

More generally, if $R\subseteq[n]^{2}$ (i.e., $R$ is not necessarily a partial
queens configurations) and $(r,c)\in[n]^{2}$, we say that $(x,y)\in R$ is a
safe absorber for $(r,c)$ if $(x,y)$ does not share a diagonal with $(r,c)$,
there exist
$a_{1}\in{\ell_{1}^{\text{far}}}(r,y),a_{2}\in{\ell_{2}^{\text{far}}}(r,y),b_{1}\in{\ell_{1}^{\text{far}}}(x,c),b_{2}\in{\ell_{2}^{\text{far}}}(x,c)$
such that $(x,y),a_{1},a_{2},b_{1},b_{2}\in R$ and no other element of $R$
shares a line with any of $(x,y),a_{1},a_{2},b_{1},b_{2}\in R$.

We denote the set of safe absorbers for $(r,c)$ in $R$ by
${\mathcal{S}}_{R}(r,c)$.

[ showmover=false,labelbottomformat=0, setwhite=qa4, qb7, qc1,
qg3,addblack=qh8]

Figure 1. In the above partial $8$-queens configuration, the black queen at
$(8,8)$ is a safe absorber for the square $(5,4)$. The four white queens
occupy the toroidal diagonals incident to $(5,8)$ and $(8,4)$, while the (non-
toroidal) diagonals incident to those squares are unoccupied.

The crucial property of safe absorbers is the following.

######  Observation 4.5.

Let $Q_{1}\subseteq Q_{2}\subseteq[n]^{2}$ be partial toroidal $n$-queens
configurations. Then, for every $(r,c)\in[n]^{2}$, it holds that
${\mathcal{S}}_{Q_{1}}(r,c)\subseteq{\mathcal{S}}_{Q_{2}}(r,c)$.

###### Proof.

Since $Q_{2}$ is a partial toroidal $n$-queens configuration, every toroidal
diagonal contains at most a single queen. Since $Q_{1}\subseteq Q_{2}$, if a
toroidal diagonal is occupied in $Q_{1}$ then it will contain no additional
queens in $Q_{2}$.

Let $(r,c)\in[n]^{2}$ and suppose $(x,y)\in{\mathcal{S}}_{Q_{1}}(r,c)$. Then,
by definition, the toroidal diagonals incident to $(r,y)$ and $(x,c)$ are
occupied in $Q_{1}$, while the (non-toroidal) diagonals incident with these
positions are unoccupied. Hence, this remains so in $Q_{2}$ as well, implying
$(x,y)\in{\mathcal{S}}_{Q_{2}}(r,c)$. ∎

In order to prove Lemma 4.3 we will show that for some $0\leq t\leq T$, $Q(t)$
contains $\Omega(n)$ safe absorbers for every $(r,c)\in[n]^{2}$. In order to
gain a heuristic understanding we consider the situation in a random binomial
subset of $[n]^{2}$. This calculation will also be used in the proof of Lemma
4.3.

######  Claim 4.6.

Let $R\subseteq[n]^{2}$ be a random binomial subset where each position is
present with probability $p\in[0,1]$, independently of other positions. Let
$(r,c),(x,y)\in[n]^{2}$ be two positions that do not share a line. Then:

${\mathbb{P}}[(x,y)\in{\mathcal{S}}_{R}(r,c)]\geq|{\ell_{1}^{\text{far}}}(r,y)||{\ell_{2}^{\text{far}}}(r,y)||{\ell_{1}^{\text{far}}}(x,c)||{\ell_{2}^{\text{far}}}(x,c)|p^{5}(1-p)^{20n}-O\left(\frac{1}{n^{2}}\right).$

###### Proof.

Instead of asking for the probability that $(x,y)\in{\mathcal{S}}_{R}(r,c)$,
we will instead estimate the probabilities of the following events.

  * •

Let $A$ be the event that $(x,y)\in R$ and no other position sharing a line
with $(x,y)$ is in $R$. Then

${\mathbb{P}}[A]=p(1-p)^{4n-1}\geq p(1-p)^{4n}.$

  * •

Let $B$ be the event that there exist distinct positions
$a_{1}\in{\ell_{1}^{\text{far}}}(r,y),a_{2}\in{\ell_{2}^{\text{far}}}(r,y),b_{1}\in{\ell_{1}^{\text{far}}}(x,c),b_{2}\in{\ell_{2}^{\text{far}}}(x,c)$
such that $a_{1},a_{2},b_{1},b_{4}\in R$, and no line incident to any of these
positions contains more than one element of $R$. Since every pair of lines
intersects in at most one position, there are at least

$\displaystyle\left(|{\ell_{1}^{\text{far}}}(r,y)|-O(1)\right)$
$\displaystyle\left(|{\ell_{2}^{\text{far}}}(r,y)|-O(1)\right)\left(|{\ell_{1}^{\text{far}}}(x,c)|-O(1)\right)\left(|{\ell_{2}^{\text{far}}}(x,c)|-O(1)\right)$
$\displaystyle=|{\ell_{1}^{\text{far}}}(r,y)||{\ell_{2}^{\text{far}}}(r,y)||{\ell_{1}^{\text{far}}}(x,c)||{\ell_{2}^{\text{far}}}(x,c)|-O(n^{3})$

choices of distinct
$a_{1}\in{\ell_{1}^{\text{far}}}(r,y),a_{2}\in{\ell_{2}^{\text{far}}}(r,y),b_{1}\in{\ell_{1}^{\text{far}}}(x,c),b_{2}\in{\ell_{2}^{\text{far}}}(x,c)$
that do not share a line with each other or with $(x,y)$. Therefore:

$\displaystyle{\mathbb{P}}[B]$
$\displaystyle\geq\left(|{\ell_{1}^{\text{far}}}(r,y)||{\ell_{2}^{\text{far}}}(r,y)||{\ell_{1}^{\text{far}}}(x,c)||{\ell_{2}^{\text{far}}}(x,c)|-O(n^{3})\right)\left(p(1-p)^{4n}\right)^{4}$
$\displaystyle\geq|{\ell_{1}^{\text{far}}}(r,y)||{\ell_{2}^{\text{far}}}(r,y)||{\ell_{1}^{\text{far}}}(x,c)||{\ell_{2}^{\text{far}}}(x,c)|\left(p(1-p)^{4n}\right)^{4}-O\left(\frac{1}{n}\right).$

Note that if both $A$ and $B$ occur then $(x,y)\in{\mathcal{S}}_{R}(r,c)$. We
observe that $(x,y)$ is not contained in any of the lines
${\ell_{1}^{\text{far}}}(r,y),{\ell_{2}^{\text{far}}}(r,y),{\ell_{1}^{\text{far}}}(x,c),{\ell_{2}^{\text{far}}}(x,c)$.
Therefore ${\mathbb{P}}[B{|}A]\geq{\mathbb{P}}[B]$. Hence

$\begin{split}{\mathbb{P}}&[(x,y)\in{\mathcal{S}}_{R}(r,c)]\geq{\mathbb{P}}\left[A\cap
B\right]={\mathbb{P}}[A]{\mathbb{P}}[B{|}A]\geq{\mathbb{P}}[A]{\mathbb{P}}[B]\\\
&\geq
p(1-p)^{4n}\left(|{\ell_{1}^{\text{far}}}(r,y)||{\ell_{2}^{\text{far}}}(r,y)||{\ell_{1}^{\text{far}}}(x,c)||{\ell_{2}^{\text{far}}}(x,c)|\left(p(1-p)^{4n}\right)^{4}-O\left(\frac{1}{n}\right)\right)\\\
&\geq|{\ell_{1}^{\text{far}}}(r,y)||{\ell_{2}^{\text{far}}}(r,y)||{\ell_{1}^{\text{far}}}(x,c)||{\ell_{2}^{\text{far}}}(x,c)|p^{5}(1-p)^{20n}-O\left(\frac{1}{n^{2}}\right).\end{split}$

∎

The preceding calculation suggests that we should consider positions $(x,y)$
such that
$|{\ell_{1}^{\text{far}}}(r,y)|,|{\ell_{2}^{\text{far}}}(r,y)|,|{\ell_{1}^{\text{far}}}(x,c)|,|{\ell_{2}^{\text{far}}}(x,c)|,=\Omega(n)$.
As we will apply Claim 4.6 with $p=\Omega(1/n)$, this condition would imply
that ${\mathbb{P}}[(x,y)\in{\mathcal{S}}_{R}(r,c)]=\Omega(1/n)$. This
motivates the next definition.

######  Definition 4.7.

A position $(x,y)\in[n]^{2}$ is balanced if
$|{\ell_{1}^{\text{far}}}(x,y)|,|{\ell_{2}^{\text{far}}}(x,y)|\geq n/10$.

We will now show that for every $(r,c)\in[n]^{2}$ there are $\Omega(n^{2})$
positions $(x,y)\in[n]^{2}$ such that $(r,c)$ and $(x,y)$ do not share a line
and $(r,y)$ and $(x,c)$ are both balanced. Let $S\subseteq[n]^{2}$ be the set
of positions $(x,y)$ such that neither of

$x-n/10\leq y\leq x+n/10,\quad\frac{9}{10}n-x\leq y\leq\frac{11}{10}n-x$

holds (see Figure 2).

Figure 2.  Roughly speaking, balanced means not too close to the main
diagonals. In the $20\times 20$ array above the set $S$ of balanced positions
is shaded.

######  Claim 4.8.

Let $(x,y)\in S$. Then $(x,y)$ is balanced.

###### Proof.

For every $(x,y)\in[n]^{2}$, we have
$|{\ell_{1}^{\text{far}}}(x,y)|=|x+y-(n+1)|$ and
$|{\ell_{2}^{\text{far}}}(x,y)|=|x-y|$.

Let $(x,y)\in S$. Then, by definition, either $y>x+n/10$ or $x>y+n/10$. Both
imply $|{\ell_{2}^{\text{far}}}(x,y)|=|x-y|>n/10$. Similarly, either
$x+y>11n/10$ or $x+y<9n/10$. In the first case, $x+y-(n+1)>n/10-1$. In the
second, $x+y-(n+1)<-n/10-1$. Both imply
$|{\ell_{1}^{\text{far}}}(x,y)|=|x+y-(n+1)|\geq n/10$. ∎

######  Claim 4.9.

Each row and each column in $[n]^{2}$ intersects $S$ on at least $n/2$
positions.

###### Proof.

Since $S$ is invariant under reflection along the $y=x$ axis it suffices to
prove the claim for rows. $S$ is also invariant under the reflection
$(r,c)\mapsto(n+1-r,c)$, so it suffices to prove the claim for rows
$r\leq(n+1)/2$.

Let $r\in[n]$ be at most $(n+1)/2$. We will show that row $r$ contains at
least $n/2$ positions in $S$. Indeed, if $1\leq r\leq n/10$ then for every
$2n/10<c<8n/10$, it holds that $(r,c)\in S$. Otherwise, $n/10<r\leq(n+1)/2$.
In this case every $c$ satisfying one of $n/10+r<c<9n/10-r$, $c<r-n/10$, or
$c>11n/10-r$ will also satisfy $(r,c)\in S$. In any case, there are more than
$n/2$ elements $c\in[n]$ such that $(r,c)\in S$. ∎

######  Claim 4.10.

For every $(r,c)\in[n]^{2}$ there are at least $n^{2}/5$ positions
$(x,y)\in[n]^{2}$ such that $(r,y)$ and $(x,c)$ are balanced and $(r,c)$ and
$(x,y)$ do not share a line.

###### Proof.

Let $(r,c)\in[n]^{2}$. Let $S_{r}\coloneqq\\{y:(r,y)\in S,y\neq c\\}$ and
$S_{c}\coloneqq\\{x:(x,c)\in S,x\neq r\\}$. By Claim 4.9, $|S_{r}|,|S_{c}|\geq
n/2-1$. Now, let

$S_{(r,c)}\coloneqq\left(S_{c}\times
S_{r}\right)\setminus\left(\ell_{1}(r,c)\cup\ell_{2}(r,c)\right).$

We note that $|S_{(r,c)}|\geq(n/2-1)^{2}-2n\geq n^{2}/5$. Also, by definition,
if $(x,y)\in S_{(r,c)}$ then it does not share a line with $(r,c)$. Next, we
argue that for every $(x,y)\in S_{(r,c)}$, it holds that $(r,y)$ and $(x,c)$
are both balanced. Indeed, if $(x,y)\in S_{(r,c)}$, then (again by definition)
$x\in S_{c}$. Therefore $(x,c)\in S$ and so by Claim 4.9 is balanced.
Similarly, $(r,y)\in S$ and hence is balanced as well. ∎

In order to prove Lemma 4.3 we will use the following bounded-differences
inequality.

######  Theorem 4.11 ([14] Corollary 1.4).

Let $X_{1},\ldots,X_{N}$ be i.i.d. Bernoulli random variables with
${\mathbb{P}}[X_{1}=1]=p$. Assume that for $K>0$ the function
$f:\\{0,1\\}^{N}\to\mathbb{R}$ satisfies the Lipschitz condition
$\left|f(\omega)-f(\omega^{\prime})\right|\leq K$ whenever
$\omega,\omega^{\prime}\in\\{0,1\\}^{N}$ differ by a single coordinate. Then,
for all $t>0$:

${\mathbb{P}}\left[\left|f(X_{1},\ldots,X_{N})-{\mathbb{E}}\left[f(X_{1},\ldots,X_{N})\right]\right|\geq
t\right]\leq 2\exp\left(-\frac{t^{2}}{2N(1-p)pK^{2}+2Kt/3}\right).$

Theorem 4.11 applies to functions of Bernoulli random variables. In order to
apply it to our situation, we introduce a coupling of $\\{Q(t)\\}_{t=0}^{T}$
to a binomial random subset of $[n]^{2}$. For every $x\in[n]^{2}$, let
$x_{\alpha}\in[0,1]$ be i.i.d. uniformly random. Observe that for every
$q\in[0,1]$, $R(q)\coloneqq\\{x\in[n]^{2}:x_{\alpha}<q\\}$ is a binomial
random subset of $[n]^{2}$ with density $q$.

Now consider the random process $\tilde{Q}(0),\tilde{Q}(1),\ldots$, defined as
follows: ${\tilde{Q}}(0)=\emptyset$. Suppose that for $t<n$ we have defined
${\tilde{Q}}(t)$. Let $x\in[n]^{2}$ be the position that minimizes
$x_{\alpha}$ which is also available in $\tilde{Q}(t)$ (by “available” we mean
not sharing a row, column, or toroidal diagonal with a previously chosen
position). Set $\tilde{Q}(t+1)=\tilde{Q}(t)\cup\\{x\\}$. If there is no such
position, set ${\tilde{Q}}(t+1)={\tilde{Q}}(t)$. Observe that
$\\{\tilde{Q}(t)\\}_{t=0}^{T}$ and $\\{Q(t)\\}_{t=0}^{T}$ have the same
distribution. Thus we may (and do) identify them. We remark, however, that the
process ${\tilde{Q}}(t)$ is defined also for $T<t\leq n$. This will be useful
in the proof of the next claim.

Set $p=1/(4n)$ and let $R=R(p)$. Let ${\tilde{R}}\subseteq R$ be the set of
positions $x\in R$ that are not threatened by any other element of $R$ (that
is, they are the only positions in their row, column, and toroidal diagonals).

######  Claim 4.12.

With probability $1-\exp\left(-\Omega(n)\right)$ it holds that
${\tilde{R}}\subseteq Q(T)$.

###### Proof.

We note that by Chernoff’s inequality we have
${\mathbb{P}}\left[|R|>T\right]=\exp\left(-\Omega(n)\right)$.

Let $x\in{\tilde{R}}$. By definition of the process, it holds that
$x_{\alpha}<y_{\alpha}$ for every $y$ that threatens $x$. Thus, there exists
some $t$ (possibly greater than $T$) such that $x\in{\tilde{Q}}(t)$. Let
$t_{x}$ be the smallest $t$ such that $x\in{\tilde{Q}}(t)$. It suffices to
show that $t_{x}\leq T$. This clearly holds if $|R|\leq T$. The latter event
holds with probability $1-\exp\left(-\Omega(n)\right)$, as desired. ∎

Due to Observation 4.5 and Claim 4.12, with probability
$1-\exp\left(-\Omega(n)\right)$ we have
${\mathcal{S}}_{{\tilde{R}}}(r,c)\subseteq{\mathcal{S}}_{Q(T)}(r,c)$ for every
$(r,c)\in[n]^{2}$. Therefore, Lemma 4.3 follows from the following claim.

######  Claim 4.13.

There exists a constant $\beta>0$ such that w.h.p. ${\tilde{R}}$ is $(\beta
n)$-absorbing.

We will apply Theorem 4.11 to prove Claim 4.13. We will use the following
Lipschitz condition.

######  Claim 4.14.

Let $Q_{1},Q_{2}\subseteq[n]^{2}$ be partial toroidal $n$-queens
configurations such that $|Q_{1}\Delta Q_{2}|=1$. Then, for every
$(r,c)\in[n]^{2}$, we have
$||{\mathcal{S}}_{Q_{1}}(r,c)|-|{\mathcal{S}}_{Q_{2}}(r,c)||\leq 5$.

###### Proof.

Let $(r,c)\in[n]^{2}$. It suffices to show that if $R_{2}$ is obtained from
$R_{1}$ by adding a queen $(x,y)$, then
$||{\mathcal{S}}_{Q_{1}}(r,c)|-|{\mathcal{S}}_{Q_{2}}(r,c)||\leq 5$.

Since $Q_{1}\subseteq Q_{2}$, Observation 4.5 implies that
${\mathcal{S}}_{Q_{1}}(r,c)\subseteq{\mathcal{S}}_{Q_{2}}(r,c)$. Hence, it is
enough to show that

$|{\mathcal{S}}_{Q_{2}}(r,c)\setminus{\mathcal{S}}_{Q_{1}}(r,c)|\leq 5.$

We observe that overall, $R_{2}$ contains at most one more (not necessarily
safe) absorber for $(r,c)$ than $R_{1}$. Indeed, the only candidate for a new
absorber in $R_{2}$ is $(x,y)$ itself. In this way,
${\mathcal{S}}_{R_{2}}(r,c)$ may contain at most one absorber that is not in
${\mathcal{B}}_{R_{1}}(r,c)$. Any other elements of
${\mathcal{S}}_{Q_{2}}(r,c)\setminus{\mathcal{S}}_{Q_{1}}(r,c)$ must have the
following form: There exists some
$(x^{\prime},y^{\prime})\in{\mathcal{B}}_{Q_{1}}(r,c)\setminus{\mathcal{S}}_{Q_{1}}(r,c)$
and $(x^{\prime},y^{\prime})\in{\mathcal{S}}_{Q_{2}}(r,c)$. This occurs only
if $(x,y)\in{\ell_{i}^{\text{far}}}(x^{\prime},y^{\prime})$ for some $i=1,2$
and some $(x^{\prime},y^{\prime})\in{\mathcal{B}}_{Q_{1}}(r,c)$. In this case
$(x,y)$ shares a toroidal diagonal with one of $(r,y^{\prime})$ and
$(x^{\prime},c)$. Hence, one of the following hold modulo $n$:

$x+y=r+y^{\prime},\quad x-y=r-y^{\prime},\quad x+y=x^{\prime}+c,\quad
x-y=x^{\prime}-c.$

For each $x^{\prime}$ that solves one of these equations, there is at most one
$y^{\prime}$ such that $(x^{\prime},y^{\prime})\in Q_{1}$. Similarly, for each
$y^{\prime}$ solving an equation there is at most one $x^{\prime}$ such that
$(x^{\prime},y^{\prime})\in Q_{1}$. Therefore, in this way, adding $(x,y)$ to
$Q_{1}$ may contribute at most $4$ absorbers to ${\mathcal{S}}_{Q_{2}}(r,c)$.
In summary:

$|{\mathcal{S}}_{Q_{2}}(r,c)\setminus{\mathcal{S}}_{Q_{1}}(r,c)|\leq 5,$

as desired. ∎

###### Proof of Claim 4.13.

We will now show that for $\beta\coloneqq(40e)^{-5}$ with high probability
${\tilde{R}}$ contains at least $\beta n$ safe absorbers for every position.

Let $(r,c)\in[n]^{2}$. We will show that

${\mathbb{P}}\left[|{\mathcal{S}}_{{\tilde{R}}}(r,c)|<\beta
n\right]\leq\exp\left(-\Omega(n)\right).$

A union bound over the $n^{2}$ positions will then imply that w.h.p. this
holds simultaneously for all positions.

Let $X_{(r,c)}\coloneqq|{\mathcal{S}}_{{\tilde{R}}}(r,c)|$. We will apply
Theorem 4.11 to $X_{(r,c)}$. For $(x,y)\in[n]^{2}$, let $Y_{(x,y)}$ indicate
the event $(x,y)\in R$. Then the random variables
$\\{Y_{(x,y)}\\}_{(x,y)\in[n]^{2}}$ are independent. Furthermore, each
$Y_{(x,y)}$ has Bernoulli distribution with parameter $p$. Additionally,
$R,{\tilde{R}}$, and hence $X_{(r,c)}$ are determined by these random
variables. Therefore $X_{(r,c)}$ is a function of the i.i.d. Bernoulli random
variables $\\{Y_{(x,y)}\\}_{(x,y)\in[n]^{2}}$.

We note that adding a queen $(x,y)$ to $R$ changes ${\tilde{R}}$ by at most
$4$. Indeed, if $(x,y)$ is the unique queen in the lines incident to it in
$R$, then $|{\tilde{R}}|$ increases by one. On the other hand, $(x,y)$
occupies four lines. If any of these contains a queen from ${\tilde{R}}$, then
that queen will be removed from ${\tilde{R}}$ once $(x,y)$ is added to $R$.
Hence, $|{\tilde{R}}|$ may decrease by at most $4$. Hence, By Claim 4.14,
changing the value of some $Y_{(x,y)}$ can change the value of $X_{(r,c)}$ by
at most $20$.

Next we bound ${\mathbb{E}}X_{(r,c)}$ from below, with the goal of showing
that ${\mathbb{E}}X_{(r,c)}-\beta n=\Omega(n)$. By Claim 4.10 there are at
least $n^{2}/5$ positions $(x,y)$ such that $(r,c)$ and $(x,y)$ do not share a
line and $(r,y),(x,c)$ are balanced. Let $P$ be the set of these positions.
For each $(x,y)\in P$ let $Z_{(x,y)}$ indicate the event that
$(x,y)\in{\mathcal{S}}_{{\tilde{R}}}(r,c)$. Then

$X_{(r,c)}\geq\sum_{(x,y)\in P}Z_{(x,y)}.$

By Claim 4.6:

${\mathbb{E}}Z_{(x,y)}={\mathbb{P}}[Z_{(x,y)}=1]\geq|{\ell_{1}^{\text{far}}}(r,y)||{\ell_{2}^{\text{far}}}(r,y)||{\ell_{1}^{\text{far}}}(x,c)||{\ell_{2}^{\text{far}}}(x,c)|p^{5}(1-p)^{20n}-O\left(\frac{1}{n^{2}}\right).$

If $(x,y)\in P$ then $(r,y)$ and $(x,c)$ are balanced. Thus:

$|{\ell_{1}^{\text{far}}}(r,y)||{\ell_{2}^{\text{far}}}(r,y)||{\ell_{1}^{\text{far}}}(x,c)||{\ell_{2}^{\text{far}}}(x,c)|\geq\left(\frac{n}{10}\right)^{4}.$

Hence

${\mathbb{E}}Z_{(x,y)}\geq\left(\frac{n}{10}\right)^{4}p^{5}(1-p)^{20n}-O\left(\frac{1}{n^{2}}\right)\stackrel{{\scriptstyle
p=1/(4n)}}{{=}}\frac{1}{(4e)^{5}10^{4}n}-O\left(\frac{1}{n^{2}}\right).$

Therefore:

${\mathbb{E}}X_{(r,c)}\geq\sum_{(x,y)\in
P}{\mathbb{E}}Z_{(x,y)}\geq\frac{|P|}{(4e)^{5}10^{4}n}-O\left(\frac{|P|}{n^{2}}\right)\geq\frac{n}{5(4e)^{5}10^{4}}-O(1)=2\beta
n-O(1).$

Let $\lambda\coloneqq{\mathbb{E}}X_{(r,c)}-\beta n$. Then $\lambda\geq\beta
n-O(1)=\Omega(n)$. By Theorem 4.11:

$\displaystyle{\mathbb{P}}\left[X_{(r,c)}<\beta
n\right]={\mathbb{P}}\left[X_{(r,c)}<{\mathbb{E}}X_{(r,c)}-\lambda\right]$
$\displaystyle\leq
2\exp\left(-\frac{\lambda^{2}}{2n^{2}(1-p)p20^{2}+40\lambda/3}\right)$
$\displaystyle\leq\exp\left(-\Omega(n)\right).$

This completes the proof of Claim 4.13, and hence also of Lemma 4.3. ∎

##  5\. Proof of Theorem 1.1

In this section we use the results of Sections 3 and 4 to prove the
enumeration in Theorem 1.1. The idea is to bound, from below, the number of
successful outcomes of the random process. Then, we divide this by (an upper
bound on) the number of ways in which each particular $n$-queens configuration
can be constructed by the process. The result is a lower bound on
${\mathcal{Q}}(n)$.

We begin by counting the number of outcomes in the random greedy phase
(Algorithm 2.1). We have shown that w.h.p. this algorithm succeeds in
constructing a partial $n$-queens configuration with
$T=\lfloor(1-n^{-\alpha})n\rfloor$ queens. Furthermore, w.h.p. for every
$0\leq t<T$, the number of available positions at time $t$ satisfies
$|{\mathcal{A}}(t)|=\left(1\pm n^{-0.4}\right)n^{2}(1-t/n)^{4}$. Thus, the
number of outcomes of the random greedy phase is at least

$X\coloneqq\prod_{t=0}^{T-1}\left(1\pm
n^{-0.4}\right)n^{2}(1-t/n)^{4}\geq\left(\left(1-n^{-\alpha}\right)n^{2}\right)^{T}\exp\left(4\sum_{t=0}^{T-1}\log\left(1-t/n\right)\right).$

Turning our attention to the sum, we have:

$\sum_{t=0}^{T-1}\log\left(1-t/n\right)=n\frac{1}{n}\sum_{t=0}^{T-1}\log\left(1-t/n\right)\geq
n\int_{0}^{T/n}\log(1-x)dx\geq-n\left(1+{\tilde{O}}(n^{-\alpha})\right).$

Hence:

$X\geq\left(\left(1-{\tilde{O}}(n^{-\alpha})\right)n^{2}\right)^{T}\exp\left(-4n-{\tilde{O}}(n^{1-\alpha})\right)\geq\left(\left(1-{\tilde{O}}(n^{-\alpha})\right)\frac{n^{2}}{e^{4}}\right)^{n}.$

Furthermore, by Lemma 4.3 all but a vanishing fraction of these outcomes are
$10(n-T)$-absorbing, and therefore can be completed to a complete
configuration by Algorithm 2.2.

We now wish to bound, from above, the number of ways in which a specific
$n$-queens configuration can be constructed by the algorithm. Given such a
configuration, $2(n-T)$ of its queens were placed by the absorbing stage.
Given $2(n-T)$ queens, there are $(2(n-T))!!=(2(n-T))!/(2^{n-T}(n-T)!)$ ways
to partition them into $n-T$ pairs. For each pair, there are (at most) $2$
ways it might have been obtained as an absorber. Finally, there are now $T!$
orders in which the remaining queens might have been placed on the board.
Thus, the number of ways to obtain the configuration is at most

$\displaystyle Y\coloneqq\binom{n}{2(n-T)}(2(n-T))!!\times 2^{n-T}\times T!$
$\displaystyle\leq n^{2(n-T)}(2(n-T))^{2(n-T)}2^{n-T}n!$
$\displaystyle\leq\left(1+{\tilde{O}}(n^{-\alpha})\right)^{n}n!.$

Applying Stirling’s approximation:

$Y\leq\left(\left(1+{\tilde{O}}(n^{-\alpha})\right)\frac{n}{e}\right)^{n}.$

Therefore, the number of $n$-queens configurations satisfies

${\mathcal{Q}}(n)\geq\frac{X}{Y}\geq\frac{\left(\left(1-{\tilde{O}}(n^{-\alpha})\right)\frac{n^{2}}{e^{4}}\right)^{n}}{\left(\left(1+{\tilde{O}}(n^{-\alpha})\right)\frac{n}{e}\right)^{n}}\geq\left(\left(1-{\tilde{O}}(n^{-\alpha})\right)\frac{n}{e^{3}}\right)^{n},$

as desired.

##  6\. Concluding remarks

  * •

We have established that
$\liminf_{n\to\infty}\frac{{\mathcal{Q}}(n)^{1/n}}{n}\geq e^{-3}$. In [8] the
first author proved that for $\alpha\approx 1.587$,
$\limsup_{n\to\infty}\frac{{\mathcal{Q}}(n)^{1/n}}{n}\leq e^{-\alpha}$. It
would be interesting to close this gap. In particular, [16] provides numerical
evidence that for $\beta\approx 1.944$,
$\lim_{n\to\infty}\frac{{\mathcal{Q}}(n)^{1/n}}{n}=e^{-\beta}$.

  * •

A curious feature of our algorithm is that although, ultimately, it constructs
a non-toroidal configuration, the random greedy algorithm actually constructs
an approximate toroidal configuration.

As mentioned in the introduction the toroidal algorithm has a regularity which
makes its analysis more amenable than its non-toroidal counterpart.
Nevertheless, in computer simulations we have found the non-toroidal algorithm
extremely successful at constructing approximate configurations. Furthermore,
(for $n\geq 100$ and as large as $10^{7}$) we have never seen Algorithm 2.2
fail to obtain a complete configuration.

Ours is not the first random greedy algorithm used to construct $n$-queens
configurations: In [9] configurations were generated by proceeding through the
board’s rows from top to bottom, where in each row a queen was placed
uniformly at random among the available positions. Finally, a min-conflicts
algorithm was used to modify the board and find a complete solution. This
algorithm was found to construct complete configurations with ease, but it was
not analyzed formally. We have found this algorithm to possess a non-
uniformity making its analysis challenging as well.

Conversely, we wonder if the output of Algorithm 2.1 can be completed to a
toroidal configuration (assuming $n=1,5\bmod 6$, which is a necessary
condition). If so, this would give a lower bound of
$((1-{o\left(1\right)})ne^{-3})^{n}$ on such configurations, matching an upper
bound of the first author [8, Theorem 1.2]. The difficulty we have encountered
is that in an approximate toroidal configuration nearly all toroidal diagonals
are occupied. This makes absorbers like those in our proof difficult to find.

  * •

The list of conjectures at the end of [1] contains several generalizations of
the $n$-queens problem, for example to boards with different topologies and
higher dimensions. It would be interesting if these problems could be attacked
with techniques similar to the one in this paper.

## References

  * [1] Jordan Bell and Brett Stevens, _A survey of known results and research areas for n-queens_ , Discrete Mathematics 309 (2009), no. 1, 1–31.
  * [2] Tom Bohman, _The triangle-free process_ , Advances in Mathematics 221 (2009), no. 5, 1653–1677.
  * [3] Tom Bohman and Lutz Warnke, _Large girth approximate Steiner triple systems_ , Journal of the London Mathematical Society 100 (2019), no. 3, 895–913.
  * [4] Stefan Glock, Daniela Kühn, Allan Lo, and Deryk Osthus, _The existence of designs via iterative absorption_ , arXiv preprint arXiv:1611.06827 (2016).
  * [5] by same author, _On a conjecture of Erdős on locally sparse Steiner triple systems_ , Combinatorica 40 (2020), no. 3, 363–403.
  * [6] Peter Keevash, _The existence of designs_ , arXiv preprint arXiv:1401.3665 (2014).
  * [7] by same author, _Counting designs_ , Journal of the European Mathematical Society 20 (2018), no. 4, 903–927.
  * [8] Zur Luria, _New bounds on the number of $n$-queens configurations_, arXiv preprint arXiv:1705.05225 (2017).
  * [9] Steven Minton, Mark D Johnston, Andrew B Philips, and Philip Laird, _Solving large-scale constraint-satisfaction and scheduling problems using a heuristic repair method._ , AAAI, vol. 90, 1990, pp. 17–24.
  * [10] E Pauls, _Das Maximalproblem der Damen auf dem Schachbrete_ , Deutsche Schachzeitung 29 (1874), 261–263.
  * [11] by same author, _Das Maximalproblem der Damen auf dem Schachbrete, II_ , Deutsche Schachzeitung 29 (1874), 257–267.
  * [12] Igor Rivin, Ilan Vardi, and Paul Zimmermann, _The n-queens problem_ , The American Mathematical Monthly 101 (1994), no. 7, 629–639.
  * [13] Andrzej Ruciński and Nicholas C Wormald, _Random graph processes with degree restrictions_ , Combinatorics, Probability and Computing 1 (1992), no. 2, 169–180.
  * [14] Lutz Warnke, _On the method of typical bounded differences_ , Combinatorics, Probability and Computing 25 (2016), no. 2, 269–299.
  * [15] Nicholas C Wormald et al., _Differential equations for random processes and random graphs_ , The annals of applied probability 5 (1995), no. 4, 1217–1235.
  * [16] Cheng Zhang and Jianpeng Ma, _Counting solutions for the $N$-queens and Latin-square problems by Monte Carlo simulations_, Physical Review E 79 (2009), no. 1, 016703.


* Velmurugan et al. [2020] M. Velmurugan, C. Ouyang, C. Moreira, R. Sindhgatta,  Evaluating explainable methods for predictive process analytics: A functionally-grounded approach,  in: Proceedings of the 33rd International Conference on Advanced Information Systems Engineering Forum, 2020\.
  * van der Waa et al. [2021] J. van der Waa, E. Nieuwburg, A. Cremers, M. Neerincx,  Evaluating xai: A comparison of rule-based and example-based explanations,  Artificial Intelligence 291 (2021) 103404.
  * Hoque and Mueller [2021] M. N. Hoque, K. Mueller, Outcome-explorer: A causality guided interactive visual interface for interpretable algorithmic decision making, 2021\. arXiv:2101.00633.
  * Völkel et al. [2020] S. T. Völkel, C. Schneegass, M. Eiband, D. Buschek,  What is "intelligent" in intelligent user interfaces? a meta-analysis of 25 years of iui,  in: Proceedings of the 25th International Conference on Intelligent User Interfaces, 2020, p. 477–487.