Solve an 0h n0 board
Haskell, 224 bytes

Not fully tested, because it's so slow (at least O(n*2^n^2)). 

t=1&lt;2
x!p|p&lt;0=0|t=mod(div x$2^p)2
l#x=[[sum$map(p&amp;)[-1,1,l+1,-l-1]|p&lt;-[q..q+l]]|q&lt;-[0,l..l*l],let i&amp;v|x!i&lt;1=0|t=x!(i+v)+(i+v)&amp;v]
b%v|b&lt;1=t|t=b==v
s b|l&lt;-length b-1=[l#x|x&lt;-[0..2^l^2],and.map and$zipWith(zipWith(%))b(l#x)]!!0


Explanation:

Basic idea is to represent a board of Red, Blue pieces as a list of lists of 0, 1, where the list of lists is packed into a single integer for easier enumeration. All such integers for the board size are generated and converted to a form with neighbor counts. The first such board that is a valid solution of the input is returned.

-- integer x at position p with out of bounds defined to be 0 (so no bounds checking)
(!) :: (Integral b, Integral r) =&gt; r -&gt; b -&gt; r
x ! p | p &lt; 0     = 0 
      | otherwise = mod (div x (2^p)) 2


-- Sum of values from position p along vector v (x is implicit)
-- Note that a cartesian vector (x,y) in this representation is (l*x + y)
(&amp;) :: (Integral a, Integral b) =&gt; b -&gt; b -&gt; a
p &amp; v | x ! p == 0 = 0
      | otherwise  = x ! (p+v)  +  (p+v) &amp; v


-- Value of board at position p (implicit x, l)
value :: Integral a =&gt; a -&gt; a
value p = sum $ map (p&amp;) [-1, 1, l+1, -l-1]


-- Integer to board, where l is length, x is input integer
(#) :: (Integral t, Integral a) =&gt; a -&gt; t -&gt; [[t]]
l # x = [[sum $ map (p&amp;) [-1,1,l+1,-l-1] | p &lt;- [q..q+l-1]] | q &lt;- [0,l..l*l]]


-- Comparison operator, to see whether a solved board is a solution of the input
(%) :: (Num a, Ord a) =&gt; a -&gt; a -&gt; Bool
b % v | b == 0    = True
      | otherwise = b == v


-- Check one possible solution
check :: Integral a =&gt; [[a]] -&gt; Int -&gt; [[a]] -&gt; Bool
check b l x = (and . (map and)) zipWith(zipWith (%)) b (l # x)

-- Solver
solve :: Integral t =&gt; [[t]] -&gt; [[t]]
solve b = [l # x | x &lt;- [0..2^l^2], check b l x]
  where
    l = length b


The part that could probably be most golfed is: and.map and$zipWith(zipWith(%)). Otherwise, I caught a few off-by-one errors that added length and could probably be golfed more.