Complete the landscape

Question

Carcassonne is a tile-based game, where the objective is to construct Roads, Cities and Monasteries, in order to score points. The game works by players taking turns to draw and place tiles to construct a landscape, then claiming roads, cities and monasteries. An example landscape is:

There are \$19\$ distinct tiles (ignoring rotations), each of which contains at least one feature (Road, City or Monastery):

Also, notice that the landscape must be consistent. This means that roads must connect to other roads, city edges must connect to other city edges and fields must connect to fields. Therefore, these tiles are inconsistent:

To avoid this challenge being about image processing, we can translate each tile into a list containing \$5\$ values, according to this legend:

[North edge, East edge, South edge, West Edge, # of cities]

0: Field
1: Road
2: City

For instance, this tile can be described as [2, 0, 1, 1, 1]. Using this legend, we can describe each tile uniquely, and it's rotations are rotations of the first four elements. The entire grid can be described as a rectangular matrix, with a \$20^\text{th}\$ distinct value for an empty square. Translating the first landscape into this format, we get:

[
 [             [],              [], [1, 1, 0, 0, 0], [1, 1, 2, 1, 1], [0, 1, 0, 1, 0],              [],              []],
 [[1, 0, 1, 0, 0],              [], [0, 0, 0, 0, 0], [2, 0, 2, 0, 2],              [], [0, 2, 2, 2, 1], [0, 0, 0, 2, 1]],
 [[1, 1, 0, 1, 0], [0, 0, 1, 1, 0], [0, 0, 0, 0, 0], [2, 2, 0, 0, 1], [2, 2, 0, 2, 1], [2, 0, 0, 2, 1],              []]
]

using [] to represent an empty square. The complete list of tiles (ignoring rotations) in the same grid as the second image is

[1, 0, 1, 0, 0] [0, 0, 1, 1, 0] [2, 1, 1, 1, 1] [0, 1, 1, 1, 0] [2, 0, 0, 0, 1]
[2, 2, 0, 2, 1] [0, 0, 0, 0, 0] [2, 2, 2, 2, 1] [2, 2, 0, 0, 1] [2, 1, 1, 2, 1]
[2, 2, 0, 0, 2] [0, 0, 1, 0, 0] [2, 0, 1, 1, 1] [2, 1, 1, 0, 1] [0, 2, 0, 2, 1]
[1, 1, 1, 1, 0] [2, 1, 0, 1, 1] [2, 2, 1, 2, 1] [2, 0, 2, 0, 2]

---

Your task is to take in a rectangular matrix where every element save one is one of the 19 tiles given above or one of their rotations. Tiles can appear more than once, and not every tile will appear in every input. This landscape will be consistent, as defined above. You should take in this input and output the tile that could fill the empty space in the array, keeping the landscape consistent, as defined above. You may output the tile in any rotation.

As the number of cities on a tile is redundant for this task, you may choose instead to only work with 17 tiles (as 2 tiles are duplicated when ignoring cities) and take input as lists in the form [N, E, S, W] instead, giving this list of tiles

[1, 0, 1, 0] [0, 0, 1, 1] [2, 1, 1, 1] [0, 1, 1, 1] [2, 0, 0, 0] [2, 2, 0, 2]
[0, 0, 0, 0] [2, 2, 2, 2] [2, 2, 0, 0] [2, 1, 1, 2] [0, 0, 1, 0] [2, 0, 1, 1]
[2, 1, 1, 0] [0, 2, 0, 2] [1, 1, 1, 1] [2, 1, 0, 1] [2, 2, 1, 2] 

If there are multiple tiles that would work, you may output any number of valid tiles. If no such tile exists, you may produce any output/result that could not be construed as a tile (i.e. it's not in the 19 tiles specified above, nor in any of their rotations). The representation of the "empty space" in the input may be your choice, so long as its consistent, and (although I'm not sure why you would) it isn't one of the 19 tiles above or their rotations, and there will only ever be a single empty space.

This is code-golf, so the shortest code in bytes wins.

Test cases

Landscape -> Potential tiles
[[[]]] -> Any tile
[[[0, 0, 0, 0, 0], []]] -> [1, 0, 1, 0, 0], [0, 0, 1, 1, 0], [0, 1, 1, 1, 0], [2, 0, 0, 0, 1], [2, 2, 0, 2, 1], [0, 0, 0, 0, 0], [2, 2, 0, 0, 1], [2, 2, 0, 0, 2], [0, 0, 1, 0, 0], [2, 0, 1, 1, 1], [2, 1, 1, 0, 1], [0, 2, 0, 2, 1], [2, 1, 0, 1, 1], [2, 0, 2, 0, 2]
[[[], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0]]] -> [0, 0, 1, 1, 0], [1, 0, 1, 0, 0], [2, 1, 1, 2, 1], [2, 1, 0, 1, 1], [0, 1, 1, 1, 0], [2, 0, 1, 1, 1], [2, 1, 1, 1, 1], [2, 1, 1, 0, 1], [2, 2, 1, 2, 1], [0, 0, 1, 0, 0], [1, 1, 1, 1, 0]
[[0, 1, 0, 1, 0], [], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0]] -> [1, 0, 1, 0, 0], [2, 1, 0, 1, 1], [0, 1, 1, 1, 0], [2, 1, 1, 1, 1], [1, 1, 1, 1, 0]
[[[0, 1, 1, 0, 0], [0, 1, 0, 1, 0], [0, 0, 1, 1, 0]], [[1, 1, 0, 0, 0], [0, 1, 0, 1, 0], []]] -> [0, 0, 1, 1, 0], [2, 1, 1, 2, 1], [0, 1, 1, 1, 0], [2, 0, 1, 1, 1], [2, 1, 1, 1, 1], [2, 1, 1, 0, 1], [1, 1, 1, 1, 0]
[[[2, 0, 0, 0, 1], [0, 2, 2, 0, 2], [0, 2, 0, 2, 1], [0, 0, 0, 2, 1]], [[0, 2, 2, 0, 1], [2, 1, 2, 2, 1], [0, 0, 1, 1, 0], [0, 0, 0, 0, 0]], [[2, 1, 1, 2, 1], [], [1, 1, 2, 0, 1], [0, 0, 0, 1, 0]]] -> [2, 0, 1, 1, 1]

Answer 1

Charcoal, 87 bytes

Ｆθ⊞ι⟦⁷⟧⊞θ⟦⟦⁷⟧⟧≔⊟Φθ№ιυηＩΦＥ⁸¹Ｅ⁴Ｘ²﹪÷ιＸ³λ³∧∧⊖↔⁻Σιχ⊙Φιμ⊖↔⁻λ§ιμ⬤ι＆맧§θ⁺⌕θη⁻⁼첬μ⁺⌕ηυ∧μ⁻²μ⁺²μ

Try it online! Link is to verbose version of code. Takes input as a nested array of [N, E, S, W] values where 4 represents a field and outputs a double-spaced list of sets of four values representing all valid rotations of all valid tiles. Explanation:

Ｆθ⊞ι⟦⁷⟧⊞θ⟦⟦⁷⟧⟧

Add borders to the input allowing any edge.

≔⊟Φθ№ιυη

Find the row of the tile to be placed.

ＩΦＥ⁸¹Ｅ⁴Ｘ²﹪÷ιＸ³λ³

Output all rotations of all tiles, except...

∧∧⊖↔⁻Σιχ⊙Φιμ⊖↔⁻λ§ιμ⬤ι

... non-existent* tiles, and...

＆맧§θ⁺⌕θη⁻⁼첬μ⁺⌕ηυ∧μ⁻²μ⁺²μ

... tiles that don't fit.

*There are two categories of non-existent tiles:

• A tile that features all three features must have two roads and one each of the other two features. Conveniently with this input format illegal tiles would have a feature sum of either 9 or 11 and no other tiles have this sum.

• A tile that features two roads and two city edges cannot have them alternating. Conveniently with this input format illegal tiles alternate between 1 and 2 thus their cyclic consecutive absolute differences are all 1. (Note that by comparison it's possible for tiles to feature two fields and two other features and still have them be alternating.)

Answer 2

Jelly, 40 bytes

(39 if we may output each tile as many times as it will fit up to rotational symmetry - remove Q)

3ṗ4o@U,ZƊṙ2=ḢʋƝ€€ȦʋƇ⁸ṙJṂƊ€Qḟ“[^go{~Ẉ‘b4¤

A monadic Link that accepts a list of lists of tiles as lists using the no-cities format of [N,E,S,W] with Field=1, Road=2, and City=3. Yields a list of tiles that can fit.

The outputted tiles are provided rotated such that their representation is the smallest it can be lexicographical (e.g. if [3,2,2,1] fits in any orientation(s) it would be given (once) as [1,3,2,2])

Try it online! Or see the test-suite (with the IO tweaked to use 0, 1, and 2, as in the question).

How?

There are \$17\$ available tiles out of \$24\$ possible tiles (up to rotational symmetry), so we find all possible tiles that could fit in any rotation, rotate each of them to their lexicographically minimum and then filter out the \$7\$ unavailable tiles.

3ṗ4o@U,ZƊṙ2=ḢʋƝ€€ȦʋƇ⁸... - Link: Board
3ṗ4                      - {implict range 3 = [1,2,3]} Cartesian power 4
                             -> All Tiles including unavailable ones like [1,2,3,3]
                                with all of their uniquely identifiable rotations
                    ⁸    - chain's left argument -> Board
                   Ƈ     - filter {All Tiles} keeping those for which:
                  ʋ      -   last four links as a dyad - f(Potential Tile, Board):
   o@                    -     {Board} logical OR (vectorising) {Potential Tile}
                                 -> Board with Potential Tile inserted
     U,ZƊ                -     reverse all the tiles and pair with transpose
                                 (allows same logic for both E-W and S-N checks)
                €        -     for each of these two:
               €         -       for each row:
              Ɲ          -         for neighboring pairs of tiles:
             ʋ           -           last four links as a dyad - f(L, R):
         ṙ2              -             rotate {L} left two
           =             -             {that} equals (vectorising) {R}
            Ḣ            -             head -> relevant comparison
                 Ȧ       -     any an all? (0 if any comparison was falsey)
                             -> all rotations of all tiles that fit
                                (including the unavailable ones)

...ṙJṂƊ€Qḟ“[^go{~Ẉ‘b4¤   - ...continued:
       €                 - for each found tile:
      Ɗ                  -   last three links as a monad - f(T=rotated tile):
    J                    -     range of length {T} -> [1,2,3,4]
   ṙ                     -     {T} rotate left (vectorised) {[1,2,3,4]}
     Ṃ                   -     minimum -> lexicographically minimal rotation
        Q                - deduplicate -> Found Tiles (in their minimal rotation)
                     ¤   - nilad followed by link(s) as a nilad:
          “[^go{~Ẉ‘      -   code-page indices -> [91,94,103,111,123,126,187]
                   b4    -   to base four
                               -> Unavailable Tiles (in their minimal rotation) = [[1,1,2,3],[1,1,3,2],[1,2,1,3],[1,2,3,3],[1,3,2,3],[1,3,3,2],[2,3,2,3]]
         ḟ               - {Found Tiles} filter discard {Unavailable Tiles}

Answer 3

Python3, 301 bytes:

E=enumerate
def f(b):
 for x,r in E(b):
  for y,P in E(r):
   if[]==P:return[i for i in[[v//d%3for d in(1,3,9,27)]for v in b"[$)'S>QPYDZ&_<( G"]if any(all(X in(Y,[])for X,Y in zip([c and b[x+~q%(2-2//q*4)][y+q%(2-q//5*4)][q%4]for q,c in E((b*x,r[y+1:],b[x+1:],b*y),2)],i[j:]+i[:j]))for j in range(4))]

Try it online!

Answer 4

JavaScript (Node.js), 193 bytes

Expects a matrix of strings in "NESW" format (or an empty string for the missing tile).

Returns a list of strings in the same format. Only one rotation per tile is included.

m=>m.map((r,y)=>r.map((s,x)=>s||0xDB5ECDAAE7E20755344F4D6A4CEn.toString(3).replace(/..../g,s=>[...s].every((_,i,a)=>a.some((_,d)=>m[y+~-d%2]?.[x-(d-2)%2]?.[d^2]-s[d+i&3]))||o.push(s))),o=[])&&o

Attempt This Online!

Commented

m =>                        // m[] = input matrix
m.map((r, y) =>             // for each row r[] at index y in m[]:
  r.map((s, x) =>           //   for each string s at index x in r[]:
    s ||                    //     abort if this is not the missing tile
    0xDB5E..A4CEn           //     lookup BigInt encoding the 17 tiles
    .toString(3)            //     convert it to base 3
    .replace(               //     -> "2222222122202211..0000"
      /..../g,              //     split into groups of 4 characters
      s =>                  //     for each string s:
      [...s]                //       split s
      .every((_, i, a) =>   //       for i = 0 to i = 3:
        a.some((_, d) =>    //         for d = 0 to d = 3:
          m[                //           extract the cell located at
            y + ~-d % 2     //           row y + dy
          ]?.[              //           and
            x - (d - 2) % 2 //           column x + dx
          ]?.[              //           take the character corresponding
            d ^ 2           //           to the opposite direction
          ] -               //           and test whether it's defined
          s[d + i & 3]      //           and different from the character
                            //           in s at index (d + i) mod 4
        )                   //         end of some()
      )                     //       end of every()
      || o.push(s)          //       if falsy, add s to o
    )                       //     end of replace()
  ),                        //   end of map()
  o = []                    //   initialize o to an empty array
) && o                      // end of map(); return o