  A $k$-deck of a (coloured) graph is a multiset of its induced $k$-vertex
subgraphs. Given a graph $G$, when is it possible to reconstruct with high
probability a uniformly random colouring of its vertices in $r$ colours from
its $k$-deck? In this paper, we study this question for grids and random
graphs. Reconstruction of random colourings of $d$-dimensional $n$-grids from
the deck of their $k$-subgrids is one of the most studied colour reconstruction
questions. The 1-dimensional case is motivated by the problem of reconstructing
DNA sequences from their `shotgunned' stretches. It was comprehensively studied
and the above reconstruction question was completely answered in the '90s. In
this paper, we get a very precise answer for higher $d$. For every $d\geq 2$
and every $r\geq 2$, we present an almost linear algorithm that reconstructs
with high probability a random $r$-colouring of vertices of a $d$-dimensional
$n$-grid from the deck of all its $k$-subgrids for every $k\geq(d\log_r
n)^{1/d}+1/d+\varepsilon$ and prove that the random $r$-colouring is not
reconstructible with high probability if $k\leq (d\log_r n)^{1/d}-\varepsilon$.
This answers the question of Narayanan and Yap (that was asked for $d\geq 3$)
on "two-point concentration" of the minimum $k$ so that $k$-subgrids determine
the entire colouring. Next, we prove that with high probability a uniformly
random $r$-colouring of vertices of a uniformly random graph $G(n,1/2)$ is
reconstructible from its full $k$-deck if $k\geq 2\log_2 n+8$ and is not
reconstructible with high probability if $k\leq\sqrt{2\log_2 n}$. We further
show that the colour reconstruction algorithm for random graphs can be modified
and used for graph reconstruction: we prove that with high probability
$G(n,1/2)$ is reconstructible from its full $k$-deck if $k\geq 2\log_2 n+11$
while it is not reconstructible with high probability if $k\leq 2\sqrt{\log_2
n}$.
