Solve an 0h n0 board

Question

0h n0 is a very simple and enjoyable game, a bit like Sudoku or minesweeper.

Game rules

(I recommend using the tutorial in the game if you can, it is very simple and useful)

The puzzle starts with an n * n board containing some fixed pieces and some empty cells, and the solver must find a way to fill the empty cells with pieces and satisfy all of the constraints imposed by the fixed pieces. Here are the piece types we will be using with the abbreviation:

• # Red piece (blocks view of a blue piece)
• O Blue piece
• . Empty location
• number Numbered blue piece (number is a one digit number >0)

All the numbered pieces must see exactly the same amount of blue pieces as the number. For example:

#1O#O
...O.

The 1 piece can see only one other blue piece.

How pieces see each other

Two blue pieces can see each other if they are in the same row or column and no red piece is between them. Example:

(S is a location that the O piece can see, X can't be seen)

   S
   S
X#SOSS
   #
   X

Each blue piece must see at least one other blue piece:

#O#

Wont work, but:

#OO

Or:

###

Do work.

Demo board solve

.1..
..1.
....
22#2

The right bottom 2 can only see above itself, so they must be blue, and the top right must be red.

.1.#
..1O
...O
22#2

Since the 1 is filled, we can surround it with red pieces.

.1##
.#1O
..#O
22#2

The top left 1 can only see in one direction now, so we can fill it in.

O1##
.#1O
..#O
22#2

Now about those last 2s. We can put 2 blue pieces over them.

O1##
.#1O
OO#O
22#2

The last one will be filled with #

O1##
##1O
OO#O
22#2

Input

Input is a multi-line string. The size will be 9x9 without trailing space. It has the following piece types:

• . Empty
• # Preset red, cannot be changed
• number Preset number, cannot be changed

(Note that blue will not ever be in the input)

Output

Output is the same as input, with the change that empty (.) is replaced with either a red or a blue to solve the board, and numbers are replaced with blue pieces (O).

Examples

(Note that multiple solutions may be possible for each puzzle, but you only need to show one of them)

Input:
........4
...3.1...
45...2.3.
..9......
1..6#44..
....4..5.
....4.36.
2.......6
1....4...

Output:
OOO###OOO
OOOO#O#OO
OOO#OO#OO
#OOOO#O##
O#OO#OOOO
O#OOOO#OO
#OOOO#OOO
OO#O#OOOO
O#OOOO#O#

Input:
..7..#...
#...8..11
2....5...
..5...48.
...#...4.
.5...6...
...1.2...
2.....6.8
.7..#....

Output:
OOOOO####
##OOOO#OO
O#OOOO###
OOO#OOOOO
OO##O##O#
#O##OOOOO
#O#O#O#OO
OO#OOOOOO
OOO###O#O

Input:
5.3..33..
...4...23
.6.6.34..
...3#....
....5..4.
.5....3..
7.98.6#.3
.5.6..2..
..6...2..

Output:
OOOOO####
##OOOO#OO
O#OOOO###
OOO#OOOOO
OO##O##O#
#O##OOOOO
#O#O#O#OO
OO#OOOOOO
OOO###O#O

_{Thanks to @PeterTaylor and @apsillers for all their help in the sandbox!}

Answer 1

Haskell, 224 bytes

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

t=1<2
x!p|p<0=0|t=mod(div x$2^p)2
l#x=[[sum$map(p&)[-1,1,l+1,-l-1]|p<-[q..q+l]]|q<-[0,l..l*l],let i&v|x!i<1=0|t=x!(i+v)+(i+v)&v]
b%v|b<1=t|t=b==v
s b|l<-length b-1=[l#x|x<-[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) => r -> b -> r
x ! p | p < 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)
(&) :: (Integral a, Integral b) => b -> b -> a
p & v | x ! p == 0 = 0
      | otherwise  = x ! (p+v)  +  (p+v) & v


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


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


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


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

-- Solver
solve :: Integral t => [[t]] -> [[t]]
solve b = [l # x | x <- [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.