Place a Carcassonne tile The board game

In the board game "Carcassonne" players place tiles by matching their edges and earn the highest scores through creating large contiguous areas of terrain. The following are (roughly) the types and quantities of tiles included in the game:

#01 x4 
 #02 x5 
 #03 x8 
 #04 x2 

#05 x9 
 #06 x4  
 #07 x1  
 #08 x3 

#09 x3  
 #10 x3 
 #11 x4  
 #12 x5 

#13 x3 
 #14 x3 
 #15 x2 
 #16 x5   

#17 x5  
 #18 x2 
 #19 x3 
 #20 x1 

#21 x5  
 #22 x2 
 #23 x1 
 #24 x1 

#25 x1 

The Task

You must place a tile by matching edges, while trying to maintain the largest possible contiguous areas of terrain.

Placement


Tiles can only be placed in one of the (up to 4) blank spaces adjacent to any existing tile (or tiles) in the play area.
Tiles can be rotated 90, 180 or 270 degrees.


Edge-matching


Edges of a placed tile must match the touching edges of the (up to 4) neighbouring tiles, i.e. touching pixels are the same colour.


Contiguous terrain


"Closing an area of terrain" refers to placing a tile such that any contiguous area of colour could not then be continued with further tile placements.
If an alternative placement is possible, it must be chosen over any tile placement that would close an area of terrain. 
If you have to choose between a number of closing placements, choose any. If you have to choose between a number of non-closing placements, choose any.
Disregard #ff00ff (the corner pixels) when calculating contiguous areas. Also disregard buildings, i.e. areas of colour already fully enclosed within a tile.


Input


Input is two images: 


The play area. 


The initial play area consists of tile #11 (a single tile).
The augmented play area created as output must also be supported as input.

The tile to be placed.


All of the example tiles must be supported as input.


Determine matching edges/contiguous terrain using this image data alone. No hardcoding.


Output


Output is an image showing the resultant play area after placing the tile.
The image must be compatible with your own program,  i.e. it can be used as play area input.
If it's impossible to place a tile, return an error.


You can assume that


Tiles are always 55 px by 55 px 
Tiles will only ever feature the colours currently used in the example tiles.


Notes


Your answer must feature example output after at least 2 passes (more is encouraged).
This is a partial and inaccurate rendering of the original board game, you don't need to apply any of the rules or tactics not mentioned here. 


Score


Your score is your submission's byte count.
Image data isn't included in your score.
Lowest score wins.




Playing a full game

You may wish to write a script that uses your submissison to play a full game, which might consist of:


Placing a tile chosen pseudorandomly from the full set of 85.
Returning the tile to the set if it can't be placed.
Repeating until every tile has been placed - or until two tiles in a row can't be placed.


It won't be included in your byte count, or improve your score, but I'll likely offer a bounty to this kind of answer.
Common Lisp, 2650 2221 1992 1186 1111 bytes

Update: "Easy" golfing now done, further gains will require bigger changes.

Update 2: With the competition getting fiercer, the new version no longer favors positions inside the current playing field rectangle (that would be 57 bytes extra). This option, as well as a simple speed optimization, is by enabled by default in the downloadable version with the simulator, but not in the official answer below.

Update 3: Minor interface changes for major byte count gains.

I created a simple Web UI as well. The full package (a single LISP file and the tile images) can be downloaded here. To try it, install hunchentoot, zpng and png-read with quiclisp, load in carcassonne.lisp, and connect to localhost:8080. The code has been tested on CCL/Windows and SBCL/Linux. The above mentioned libraries are only needed for the UI/simulator part; the solution itself is plain ANSI Common Lisp.

(defun c(f p &amp;aux b a s z(c 55))
  (macrolet((d(v l &amp;body b)`(dotimes(,v,l),@b))
            (b(b c)`(d i c(d j c(setf,b,c))))
            (r(&amp;rest p)`(aref,@p))
            (n(u v i j)`(and(setf l(*(f,u,v)l))
                            (find(r f(+,u,i)(+,v,j))`(0,(r f,u,v))))))
    (labels((p(p w)(d y(ceiling w 2)(d x(- w y y)(rotatef(r p y #6=(+ x y))(r p #6##7=(- w y))(r p #7##8=(- w x y))(r p #8#y)))))
            (a(y x)(or(if(= 0(r f y x))1 #4=(and(= 1(incf(r s y x)))(=(r f y x)z)(push`(,y,x)a)0))0))
            (f(y x)(setf z(r f y x))(if #4#(loop for((y x))= a while(pop a)maximize(+(a(1- y)x)(a y(1- x))(a(1+ y)x)(a y(1+ x))))1)))
      (d i 8(when(d x #1=(array-dimension f 0)(or(= 0(r f(- #1#52 i)x))(return t)))(setf f(adjust-array f`(#2=,(+ #1#c)#2#))))(p f(1- #1#)))
      (d i 4(d u #9=(/ #1#c)(d v #9#
        (let((y(* u c))(x(* v c))(l 9e9))
          (when(= 0(r f y x))
            (b #10=(r f(+ y i)(+ x j))(r p i j))
            (setf s(make-array`(,#1#,#1#))a())
            (ignore-errors(if(&gt; #11=(*(loop for d from 1 to 53
                                            sum(+(n y #3=(+ x d)-1 0)(n #5=(+ y d)(+ 54 x)0 1)(n(+ 54 y)#3#1 0)(n #5#x 0 -1)))
                                      (1+ l))
                                (or(car b)0))
                             (setf b`(,#11#,i,y,x))))
            (b #10#0)))))
         (p p 54))
      (when b(d j(cadr b)(p p 54))(b(r f(+(third b)i)(+(nth 3 b)j))(r p i j)))
      `(,f,b))))


All line feeds and line-starting spacing are for cosmetics only, to ensure legibility, and not counted into the total sum.

You should call the function c with two arguments: The current play field, and the tile to place. Both should be 2D arrays; the tile 55x55 and the field a multiple of that. Additionally, the field array must be adjustable. The function returns a two-element list with the new field as its first argument. The second element is NIL if the tile cannot be placed, or otherwise a list containing the top-left coordinates and rotation of the latest tile on that array and the score for that tile. This information can be used for visualization purposes.

Note that in further calls, you must use the new field returned by c even if the second list element is NIL (the original array may have been adjust-arrayed and thus invalidated).

The code is now a bit on the slow side, byte count optimization resulting in redundant calculations. The example below completed in about three minutes on my system.

Example run for all 85 tiles:



Web UI screenshot: