Connect the Three Kingdoms

Question

You are a medieval overlord tasked with designing a road network between three kingdoms placed on a \$9 \times 9\$ grid. A sample placement of kingdoms might look like this:

^{Non-commercial use of tileset by douteigami. Thanks!}

The kingdoms make the following three demands:

1. The road network must be connected: for any tile on the road network, you must be able to reach any other tile on the road network by just moving horizontally or vertically only along road tiles.
2. The kingdoms must be connected: Every kingdom has at least one road tile immediately adjacent horizontally or vertically.
3. The road network must be thin: No block of \$2\times2\$ squares can all be road tiles.

Both of the following road networks satisfy all three criteria:

    

The following setups fail to satisfy one of the three criteria:

        

Challenge

Take input of a \$9\times9\$ grid with three kingdoms in any format. This may be a multiline string with spaces and characters, a list of single-line strings, a list of zeros and ones, a matrix, or any other reasonable format for your language.

As output, add a road network to the input (indicated in any suitable way) that satisfies the above three criteria. Note that:

• The kingdoms will never be horizontally or vertically adjacent.
• There is no requirement that your road network be minimal in any sense, just that it follows the three rules.
• You may not place roads on top of kingdoms.
• A \$2\times2\$ block where three tiles are road and a single tile is a kingdom is OK; the third restriction only concerns four road tiles.

Test Cases

The test cases use . for an empty space, k for a kingdom and # for a road, but you may take inputs in other formats/use any three distinct characters or integers as described in the previous section.

Input     -> Possible output

.........    .........
....k....    ....k....
.........    ....#....
.........    ....#....
.k....... -> .k####...
.........    .....#...
.....k...    .....k...
.........    .........
.........    .........

k.k......    k#k...... 
.........    .#.......
k........    k#.......
.........    .........
......... -> .........
.........    .........
.........    .........
.........    .........
.........    .........

.k.......    .k....... 
k........    k#.......
.k.......    .k.......
.........    .........
......... -> .........
.........    .........
.........    .........
.........    .........
.........    .........

.........    ......... 
.........    .........
k........    k#.......
.........    .#.......
k........ -> k#.......
.........    .#.......
k........    k#.......
.........    .........
.........    .........

........k    ...#####k 
....k....    ...#k....
.........    ...#.....
.........    ...#.....
......... -> ...#.....
.........    ####.....
.........    ...#.....
....k....    ...#k....
.........    ...#.....

.........    ......... 
.........    .........
.........    .........
.........    .........
......... -> .........
.........    .........
k........    k........
.k.......    #k.......
..k......    ##k......

Here's the inputs as a list of list of lists, should you prefer that:

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

Scoring

Shortest code in bytes wins.

Answer 1

JavaScript (ES7),  166 153 149  137 bytes

Slower and even less subtle than my first answer, but also shorter. This simply looks for a path touching all kingdoms without generating any \$2\times 2\$ road blocks.

Takes input as a flat list of 81 entries, with \$0\$ for an empty cell and \$2\$ for a kingdom. Returns another list with \$0\$ for an empty cell, \$1\$ for a road and \$3\$ for a kingdom.

f=(a,X)=>+(z=/.*1,1.{15}1,1|2/.exec(a))?a.some((v,x)=>(a[x]++,(d=(x-X)**2)-1|x/9^X/9&&d-81?0:v?1/X&&v==2?f(a,X):0:f(a,x))||!a[x]--)&&a:!z

Try it online!

How?

We use the regular expression /.*1,1.{15}1,1|2/ to detect either a \$2\times 2\$ block of roads or a remaining kingdom. We get null if nothing is matched, a string that is coerced to NaN by the unary + if a block is matched, or a string that is coerced to \$2\$ if a kingdom is matched.

Because the left and right boundaries are ignored, the condition on the road block is a little more restrictive than it really should, as it will also match something like that:

.........
........X
X.......X
X........
.........

However, we have plenty of room to find a path that will work even without including that kind of pattern.

---

JavaScript (ES7),  243 236  226 bytes

I'm not very happy with this method, as it heavily relies on a brute-force search. There must exist more elegant and more straightforwards ways of solving this. But it does work!

Expects a matrix with \$0\$ for an empty cell and \$3\$ for a kingdom. Returns another matrix with \$0\$ for an empty cell, \$2\$ for a kingdom and \$4\$ for a road.

f=(m,k)=>(M=m.map((r,y)=>r.map((v,x)=>x^k%8&&x^k%8+2+k/8%8&&y^(q=k/64&7)&&y^q+2+k/512?v:v?3:(X=x,Y=y,1))),g=(X,Y)=>M.map((r,y)=>r.map((v,x)=>(x-X)**2+(y-Y)**2-1?0:v-1?v-3?0:r[x]=2:g(x,y,r[x]=4))))(X,Y)|/1|3/.test(M)?f(m,-~k):M

Try it online!

How?

All puzzles can be solved¹ by putting at most 2 horizontal roads and at most 2 vertical roads across the entire grid, either next to or 'over' the kingdoms.

^{1: this was empirically verified}

Example:

Given \$k\ge 0\$, we compute:

$$x_0=k\bmod 8$$ $$x_1=x_0+2+(\lfloor k/8\rfloor \bmod 8)$$ $$y_0=\lfloor k/64\rfloor \bmod 8$$ $$y_1=y_0+2+\lfloor k/512\rfloor$$

We put vertical roads at \$x_0\$ and \$x_1\$ and horizontal roads at \$y_0\$ and \$y_1\$. If any value is greater than \$8\$, it's simply ignored.

Because \$x_1\ge x_0+2\$ and \$y_1\ge y_0+2\$, we will never end up we a \$2\times 2\$ block of roads.

Starting from a road cell, we flood-fill the grid to make sure that the two other criteria are fulfilled.

Answer 2

Perl 5, 251 317 298 258 bytes

sub f{eval'forP(0..80){forT(0,1){my@r;forK(@_){X=intP/9;Y=P%9;I=intK/9;J=K%9;push@r,X*9+Y andT&&Y-J?Y-=Y<=>J:X-I?X-=X<=>I:Y-J?Y-=Y<=>J:0 whileX.Y neI.J}D="."x81;substrD,$_,1,1for@_;substrD,$_,1,0for@r;3==D=~y/1/1/&&D!~/00.{7}00/&&returnD}}'=~s/[A-Z]/\$$&/gr}

Try it online!

Somewhat ungolfed:

sub f {
  for$p(0..80){              #loop through all possible starting points p,
                             #... the crossroads in the 9x9 board
                             #... from which each road to each kingdom starts
   for$t(0,1){               #for each starting point, try two strategies
                             #...of movement: vertical first or horizontal first
    my @r;                   #init list of road tiles to empty
    for(@_){                 #loop through all the three kingdoms from input
      $x=int$p/9; $y=$p%9;   #x,y = start roads at current starting point p
      $X=int$_/9; $Y=$_%9;   #X,Y = current kingdom

      push @r, $x*9+$y       #register road tile while x,y not yet reached X,Y
      and                          # move x,y towards X,Y
      $t && $y-$Y ? $y-=$y<=>$Y :
            $x-$X ? $x-=$x<=>$X :
            $y-$Y ? $y-=$y<=>$Y :0 # move horizontally or vertically first
                                   # ...depending on current strategy t=0 or 1
        while $x.$y ne $X.$Y   # continue towards current kingdom unless there
    }
    $d='.'x81;                 # init current board string of 81 dots
    substr $d,$_,1,1 for @_;   # put 1's at kingdoms
    substr $d,$_,1,0 for @r;   # put 0's at road tiles
    3==$d=~s/1/1/g             # if board has 3 kingdoms (none overrun by road)
      && $d!~/00.{7}00/        # and current board has no 2x2 road tiles
      && return $d             # then the board is valid and is returned
                               # otherwise try the next of the 81 starting points
  }
 }
}

Can run like this:

@test=( [[1,4], [4,1], [6,5]],
        [[0,0], [0,2], [2,0]],
        [[0,1], [1,0], [2,1]],
        [[2,0], [4,0], [6,0]],
        [[0,8], [1,4], [7,4]],
        [[6,0], [7,1], [8,2]] );
for(@test){
    my @kingdom = map $$_[0]*9+$$_[1], @$_;
    print display( f(@kingdom) );
}
sub display{join('',map join(' ',split//)."\n",pop=~y/10/k#/r=~/.{9}/g).('-'x17)."\n"}

First lines of output: (see 'Try it online' link above for more)

# . . . . . . . .
# # # # k . . . .
# . . . . . . . .
# . . . . . . . .
# k . . . . . . .
# . . . . . . . .
# # # # # k . . .
. . . . . . . . .
. . . . . . . . .

Answer 3

Brachylog, ⁹⁷ 93 bytes

This actually is fast – brute force in Brachylog! You can't believe how surprised I was when I kept upping the board size. However, this assumes that a road doesn't need to fork. If anyone finds a counterexample – be warned, the other version will not run in time on TIO! :-)

Takes castles as 2, and returns roads as 1.

∧ċ{Ċℕᵐ≤ᵛ⁹}ᵐ{s₂{;.\-ᵐȧᵐ+1∧}ᵈ}ᵇP{,1↻₁}ᵐX&{iiʰgᵗc}ᶠT{ṗʰb}ˢ{,.≠&↰₃ᵐ∈ᵛ}P∧T,X≜bᵍtᵐhᵐḍ₉.¬{s₂\s₂c=₁}∧

Try it online! or Try all testcases!

How the original version works

Many bytes got lost for getting the output into a matrix form, as I didn't find a neat way to go from list of coordinates to its matrix representation. The rough story is:

ċ{l₂ℕᵐ≤ᵛ⁹}ᵐ

We are looking for a path: a list of coordinates, each 0 ≤ X ≤ 9.

s₂ᵇ{\-ᵐȧᵐ+}ᵛ¹hᵐ

And every pair of consecutive coordinates has a distance of 1.

P{,1↻₁}ᵐX

We'll store the path as P, and a version with a 1 before every coordinate as X.

&{iiʰgᵗc}ᶠT

Transform the matrix to a list of [Type, Y, X] and store it as T.

{ṗʰb}ˢ

However, we are only interested in cities for now, so the Type must be prime (that's why they are marked with 2).

C,P≠

The city and path coordinates must all be different to each other.

∧C{;.↰₂1∧}ᵐ∈ᵛP≜

Every city coordinate, shifted by a distance of 1, must be in the path.

∧T,Xbᵍtᵐhᵐḍ₉

To the tiles T append X (the path with Type = 1 prepended), group the tiles by their coordinates and take the last one – so roads will overwrite empty tiles. Reduce the list to the Type and split it into a 9x9 matrix.

.¬{s₂\\s₂c=₁}∧

This is already the output, but make sure there is no 2x2 submatrix of roads.

Answer 4

R, 248 257 251 264 250 245 bytes

Edit: +9 bytes to fix corner-case (literally; see #1 below), then some golfing, then +13 bytes to fix another corner-case (#2, below), then some more golfing...

function(g,s=setdiff,S=0:8%/%3-1,`^`=`%in%`){k=which(g>0,T);v=k[,1];w=k[,2]
g[r<-max(s(v+S,v)%%9),]=g[,c<-max(s(w+S,w)%%9)]=1
for(i in 1:3){x=v[i];y=w[i]
if(!(x^(r+S)|y^(c+S)))`if`(F|x^v[-i],g[x:r,y--y^w[-i]**(y<2)]<-1,g[x,y:c]<-F<-1)}
g[k]=2;g}

Try it online!

This is a 'constructive' rather than 'brute-force' solution: we build a single set of roads in such a way that the conditions will be satisfied, rather than trying-out various possibilities and checking whether-or-not we've violated one or more of the conditions.

Input is a matrix with non-zero elements representing the three kingdoms. Output is a matrix with roads represented by 1, and the kingdoms by 2.

How?

First we construct 'main' roads in the form of a '+' from north-to-south and from east-to-west across empty elements of the grid, and touching at least one of the 3 kingdoms (take care: corner-case 2 was when all kingdoms are in edge rows/columns, so we need to make sure that our 'adjacent' roads are still in the grid).
Now there at most 2 kingdoms left that still need to be connected.
For each kingdom that isn't already connected to the 'main' roads, we construct an 'access road' from the kingdom to one of the 'main' roads.
We need to be careful that the 'access road' won't be split by one of the kingdoms: therefore, we check whether the unconnected kingdom is on the same row as another kingdom, and, if it isn't, we construct an east-west access road. If the unconnected kingdom shares its row with another kingdom, we check if it also shares its column: if not, we build a north-south access road. If it does (and it also shared a row), then we can be sure that the adjacent columns are empty, so we build a north-south access road in a column adjacent to the kingdom (corner case 1: for this, we need to check if the kingdom is in column 1: if it is, we build the access road in column 2, otherwise in column y-1).

Here are the roads (orange) built for each of the 6 test cases (kingdoms indicated in whiteish):

Commented code:

function(g,                     # g=input grid with kingdoms
 s=setdiff,                     # s=alias to 'setdiff()' function
 S=0:8%/%3-1,                   # S=defines adjacent indices 
 `^`=`%in%`){                   # ^=alias to '%in%' function
 k=which(g>0,T)                 # k=get indices of the kingdoms
 v=k[,1];w=k[,2]                # v=x-coordinates, w=y-coordinates of kingdoms
 r<-max(s(v+S,v)%%9)            # r=empty row next-to a kingdom
                                # (elements of v±1 that are different to v, avoiding zero and >8)
 c<-max(s(w+S,w)%%9)            # c=first empty column next-to a kingdom
 g[r,]=g[,c]=1                  # build the 'main' roads
 for(i in 1:3){                 # loop through each of the 3 kingdoms:
  x=v[i];y=w[i]                 #  (x,y=x- and y-coordinates of current kingdom)
  if(!(xin%(r+S)|y%in%(c+S)))   #  if x or y are not adjacent to r or s 
                                #  (so this kingdom isn't connected to the 'main' roads)
   `if`(F|x%in%v[-i],           #  if x is shared with the row of another kingdom, or
                                #  'F' indicates that we've already built an east-west 'access road':
    g[x:r,y                     #   build an north-south 'access road' from x to r
    -                           #   (either on the same row, y, or on an adjacent row
    (-(y%in%w[-i]))**(y<2)<-1,  #   if y is shared with the col of another kingdom);
    g[x,y:c]<-F<-1)             #  otherwise build an east-west 'access road' from y to c
  }
 g[k]=2;                        # mark the kingdoms on the grid
 g                              # and return the grid
}

Answer 5

Charcoal, 196 bytes

≔Ｅ⁹ＳθＦ⁹Ｆ⌕Ａ§θιk⊞υ⟦ικ⟧ＦυＦ⁴Ｆ⁴«θＪ§ι¹§ι⁰Ｍ✳⊗λ≔⁰ζＷ⁼ＫＫ.«✳⊗κ#≦⊕ζ»≔ωηＦ⁻υ⟦ι⟧Ｆ⁴Ｆ⁴«Ｊ§μ¹§μ⁰Ｍ✳⊗ξ≔ＫＤ⁹✳⊗νδＭ⌕δ#✳⊗ν¿∧№δ#¬№…δ⌕δ#¦k¿⁼⌕υμ¬⌕υι≔⟦μⅈⅉν⌕δ#ξ⟧η¿∧η⊖ΣＥ⟦ⅈⅉ⟧↔⁻π§η⊕ρ≔⟦⟦ικζλ⟧η⟦μν⌕δ#ξ⟧⟧ε»⎚»θＦε«Ｊ⊟§ι⁰⊟§ι⁰Ｍ✳⊗⊟ι✳⊗⊟ι×#⊟ι

Try it online! Link is to verbose version of code. Works by drawing a line from a square adjacent to one kingdom to the edge of the grid, then drawing lines from squares adjacent to each of the other kingdoms to intersect the first line, except not allowing the two lines to be exactly one row apart. Explanation:

≔Ｅ⁹Ｓθ

Input the grid.

Ｆ⁹Ｆ⌕Ａ§θιk⊞υ⟦ικ⟧

Locate all of the kingdoms.

ＦυＦ⁴Ｆ⁴«

Loop through each direction from each square adjacent to each kingdom.

θ

Print the grid.

Ｊ§ι¹§ι⁰Ｍ✳⊗λ

Jump to the selected kingdom and move to the selected adjacent square.

≔⁰ζ

Count the number of empty squares.

Ｗ⁼ＫＫ.«

Repeat while the current square is empty...

✳⊗κ#

... mark it with a #...

≦⊕ζ

... and increment the count.

»≔ωη

Start with no line for the second kingdom.

Ｆ⁻υ⟦ι⟧

Loop through the remaining kingdoms.

Ｆ⁴Ｆ⁴«

Loop through each direction from each square adjacent to this kingdom.

Ｊ§μ¹§μ⁰Ｍ✳⊗ξ

Jump to this kingdom and move to the selected adjacent square.

≔ＫＤ⁹✳⊗νδ

Grab the line in the selected direction.

Ｍ⌕δ#✳⊗ν

Move to where the line would intersect if it was valid.

¿∧№δ#¬№…δ⌕δ#¦k

Does this line cross the first kingdom's line? If so:

¿⁼⌕υμ¬⌕υι

If this is the second kingdom's line...

≔⟦μⅈⅉν⌕δ#ξ⟧η

... then save this as its line.

¿∧η⊖ΣＥ⟦ⅈⅉ⟧↔⁻π§η⊕ρ

Otherwise if the second kingdom's line does not intersect exactly one square away...

≔⟦⟦ικζλ⟧η⟦μν⌕δ#ξ⟧⟧ε

... then save this as a solution.

»⎚

Clear the canvas ready for the first kingdom's next adjacent square or the final output.

»θ

Print the grid.

Ｆε«

Loop over the kingdoms in the last solution found.

Ｊ⊟§ι⁰⊟§ι⁰Ｍ✳⊗⊟ι

Jump to the position of the kingdom and move to the found adjacent square.

✳⊗⊟ι×#⊟ι

Print the found line.

Note that this code tries all combinations of kingdoms and directions. It's probably unnecessary to try them all, for instance I think it's likely that you can always draw a line up from one of three sides of the bottommost kingdom and connecting the other two kingdoms to that line. If this is true then the code can be simplified, currently saving 10 24 bytes: Try it online! Link is to verbose version of code. Explanation:

≔Ｅ⁹ＳθＦ⁹Ｆ⌕Ａ§θιk⊞υ⟦ικ⟧

Input the grid and locate all of the kingdoms.

≔⊟υτ

Get the bottommost kingdom.

Ｆ³«

Check the squares to its right, above and left.

θＪ§τ¹§τ⁰Ｍ✳⊗ι

Print the grid and jump to the selected adjacent square.

≔⁰ζＷ⁼ＫＫ.«↑#≦⊕ζ»

Draw a line up as far as possible.

≔ωη

Start with no line for the second kingdom.

ＦυＦ⁴Ｆ⁴«

Loop over the other two kingdoms, considering all lines for all four adjacent squares. (I could just do left and right lines but it turns out that all lines is golfier.)

Ｊ§κ¹§κ⁰Ｍ✳⊗μ

Jump to this kingdom's adjacent square.

≔ＫＤ⁹✳⊗λδ

Grab the line in the selected direction.

¿∧№δ#¬№…δ⌕δ#¦k

Does this line cross the first kingdom's line? If so:

¿⌕υκ«

If this is the third kingdom's line, then...

¿∧η⊖↔⁻ⅉ§η¹

... if the second kingdom's line isn't exactly one row away, then...

≔⟦⟦τ¹ζι⟧η⟦κλ⌕δ#μ⟧⟧ε

... save this as a solution.

»≔⟦κⅉλ⌕δ#μ⟧η

Otherwise for the second kingdom save this as its line.

»⎚

Clear the canvas ready for the first kingdom's next adjacent square or the final output.

»θＦε«Ｊ⊟§ι⁰⊟§ι⁰Ｍ✳⊗⊟ι✳⊗⊟ι×#⊟ι

Print the solution.

Answer 6

Perl 5 -00ap, 114, 109 bytes

$_|=substr'iiiiiiiii
iaiaiaiai
'x5,10*!(grep/k/,@F[1,7]),90;1while s/(?<!i.{9})(?<!ii)i(?!iii|.{9}i.{9}i)/a/s

6 bytes saved thanks to @DomHastings, but 1 lost to fix a case.

Try it online!

Another perl answer, with a different approach, I've also upvoted the other perl answer.

I had to fix several times because of some cases (in addition to those of the question) for which it didn't work.

Solution

The idea is to start from the grid of roads which almost works and fix for the different cases. If there's a kingdom in the square region of os rows: 1 or 7 (after golfing), the grid is aligned on (0,0), otherwise on (0,1)

.........      #########      # # # # #
ooooooooo      # # # # #      #########
.........      #########      # # # # #
.........      # # # # #      #########
.........  ?   #########  :   # # # # #
.........      # # # # #      #########
.........      #########      # # # # #
ooooooooo      # # # # #      #########
.........      #########      # # # # #

Then the remaining roads can be fixed by removing squares when all the squares in the four directions, empirically (haven't a proof yet), at a distance of 3 (right), 2 (left, bottom) or 1 (up), are not a road (or are out of the map).

  ?
??#???
  ?
  ?

Justification

Looking for a counter-example. Starting from a grid of roads and putting kingdoms so that road a kingdom could be disconnected.

Because of the symmetries only the first corner is shown. For grid 1, the only case which causes a problem:

k.k###
. # # 
k#####
# # # 

and as there is no kingdom in the region described in solution it can't occur.

For grid 2, one example but other configurations exist:

k # #
..k###
k # #
######

One of the 2 kingdoms that cut the roads must be in the region described in solution, so this can't occur.

Answer 7

J, ¹³⁹ 127 bytes

Starting from [0,1] or [0,2] forming two grids

#XX#… and .X.#…
#.#.…     ####…
####…     .#.#…
#.#.…     ####…

at least one of the 3 attempts will succeed (based on a hacked together J script.) For some byte saving, this tries some more grids:

+u({.@\:#@~.@,"3)0|:(d|.!.0]*1+i.@$)*"2/u=:(}:"2}:"{d|.10$#:1023 682)(2=_(d=:(,-)#:i.3)&(*@]*[:>./|.!.0)(9 9$!.1]1 2 2)*1=+)"2]

Try it online!

How it roughly works

There should still be some bytes golfable. But for now:

(}:"2}:"{d|.10$#:1023 682)

The grid – first as a 10x10 matrix so we can easily shift via the 4 directions, we'll define later. Drawback: we have to cut it down to 9x9. Now, for every grid:

(9 9$!.1]1 2 2)*1=+

Whenever a castle is on a road, set the tile to empty. Also, give the roads at [0,1] and [0,2] value 2 (if they exist). From there we'll find the biggest connected road network now:

 2=_(d=:(,-)#:i.3)&(*@]*[:>./|.!.0)

Until the map does not change: shift it around and give each road a new road number: the maximum of the current number and the ones of the connected roads (but keep 0 as 0). Finally, keep the roads marked with 2 – those are connected to the starting nodes

(d|.!.0]*1+i.@$)*"2/

Now to check that all castles are connected: Take the original input, and shift it into the 4 directions. Give each castle a unique number.

 +u({.@\:#@~.@,"3)0|:

Sort the grids by the number of connected castle (the unique numbers after the shifted castle numbers are multiplied with the 1's of the road network.) Take the best one, add the castles back in – et voilà, a kingdom for you!

Answer 8

Charcoal, 67 bytes

Ｆ⁹Ｆ⌕ＡＳk⊞υ⟦ικ⟧Ｂ⁹ψＦ⁹Ｆ⁹«Ｊκι¿¬№﹪⟦ικ⟧²﹪ΠＥυΠ⊕λ² »Ｆυ«Ｊ⊟ι⊟ιk»Ｆ³Ｆ³«Ｊ⁺³κ⁺³ι¤#

Try it online! Link is to verbose version of code. Outputs using spaces for empty tiles, but anything except k serves as empty on input. This is an entirely different approach to my previous answer, so I thought it deserved a separate answer. It relies on the observation that the grid with 16 holes solves all problems except those with three kingdoms near the corners. The one thing those problems have in common is that all three kingdoms lie on even rows and columns. In such cases the grid is offset diagonally resulting in a grid with 25 holes. Explanation:

Ｆ⁹Ｆ⌕ＡＳk⊞υ⟦ικ⟧

Read in the grid and save the coordinates of the kingdoms.

Ｂ⁹ψ

Prepare an empty area for the grid.

Ｆ⁹Ｆ⁹

Loop through each square on the grid.

«Ｊκι

Jump to that position.

¿¬№﹪⟦ικ⟧²﹪ΠＥυΠ⊕λ² »

If both the row and column have the same parity as the bitwise OR of all of the coordinates, then place an explicit space at that position, preventing it from being flood filled. Since I don't have a good way of taking the bitwise OR of a list, I use De Morgan's laws to check whether neither row nor column contain have the parity of the bitwise AND of the complement of the list, noting that for the purposes of parity, product is equivalent to bitwise AND and increment is equivalent to complement.

Ｆυ«Ｊ⊟ι⊟ιk»

Place the kingdoms on the grid.

Ｆ³Ｆ³«Ｊ⁺³κ⁺³ι¤#

Try to flood fill starting at each of the nine centre squares. This guarantees that the result is a single connected road. It's not possible for only three kingdoms to disconnect the centre of the grid, so this is always safe.

Answer 9

Python3, 425 bytes

E=enumerate
M=[(1,0),(0,1),(-1,0),(0,-1)]
def P(x,y,t,d):
 q=[(x,y,[])]
 for x,y,s in q:
  if(x,y)in t:return s[:-1]
  for X,Y in M:
   if(d.get(U:=(x+X,y+Y))==0 or U in t)and U not in s and 0==any(all((x+X,y+Y)in s+[U]+t for X,Y in[(0,0),(1,1)]+M[:2])for x,y in s+[U]+t):q+=[(*U,s+[U])]
def f(b):
 d={(x,y):v for x,r in E(b)for y,v in E(r)}
 a,b,*r=[i for i in d if d[i]]
 p=P(*a,[b],d)
 while r:p+=P(*r.pop(),p,d)
 return p

Try it online!