Einführung

Seit vielen Jahrhunderten gibt es einen bestimmten Fluss, der nie kartiert wurde. Die Gilde der Kartographen möchte eine Karte des Flusses erstellen, es ist ihnen jedoch nie gelungen - aus irgendeinem Grund wurden alle Kartographen, die sie zur Kartierung des Flusses geschickt haben, von wilden Tieren in der Gegend gefressen. Ein anderer Ansatz ist erforderlich.

Eingabebeschreibung

Die Fläche ist ein rechteckiges Gitter aus Zellen mit Länge mund Breite n. Die Zelle links unten 0,0und die Zelle rechts oben wäre m-1,n-1. mund nwerden in der Eingabe als Tupel bereitgestellt m,n.

Mit Hilfe von geografischen Fernerkundungstechniken wurde der Standort von Inseln am Fluss identifiziert. Die Größe der Inseln (dh wie viele Zellen die Insel belegt) wurde ebenfalls identifiziert, die Form jedoch nicht. Wir liefern diese Informationen in einem Tupel, s,x,yin dem sdie Größe der Insel xund ydie x- und y-Position einer bestimmten Zelle dieser Insel angegeben sind. Jedes Tupel in der Eingabe ist durch Leerzeichen getrennt. Hier ist ein Beispiel für eine Eingabe:

7,7 2,0,0 2,3,1 2,6,1 2,4,3 2,2,4 8,0,6 1,2,6 3,4,6

Zur besseren Veranschaulichung sehen Sie hier die Eingabe in einem Diagramm:

 y 6|8 1 3
   5|
   4|  2
   3|    2
   2|
   1|   2  2
   0|2  
     =======
     0123456
     x

Ausgabebeschreibung

Geben Sie eine Karte mit ASCII-Zeichen aus, um Teile des Bereichs darzustellen. Jede Zelle wird entweder #(Land) oder .(Wasser) sein. Die Karte sollte diese Regeln befolgen:

1. Definition. Eine Insel ist eine orthogonal zusammenhängende Gruppe von Landzellen, die vollständig von Flusszellen und / oder der Grenze des Gebiets begrenzt wird.
2. Definition. Ein Fluss ist eine orthogonal zusammenhängende Gruppe von Wasserzellen, die vollständig von Landzellen und / oder der Grenze des Gebiets begrenzt ist und keine "Seen" enthält (2x2 Gebiete von Wasserzellen).
3. Regel . Die Karte muss genau einen Fluss enthalten.
4. Regel . Jede nummerierte Zelle in der Eingabe muss Teil einer Insel sein, die genau sZellen enthält.
5. Regel . Jede Insel in der Karte muss genau eine der nummerierten Zellen in der Eingabe enthalten.
6. Regel . Für jede Eingabe gibt es eine einzige eindeutige Zuordnung.

Hier ist die Ausgabe der Beispieleingabe:

#.#.##.
#....#.
#.##...
##..##.
###....
...##.#
##....#

Hier ist ein weiterer Ein- und Ausgang.

Eingang:

5,5 3,0,1 1,4,1 2,0,4 2,2,4 2,4,4

Ausgabe:

#.#.#
#.#.#
.....
###.#
.....

C + PicoSAT , 2345 995 952 Bytes

#include<picosat.h>
#define f(i,a)for(i=a;i;i--)
#define g(a)picosat_add(E,a)
#define b calloc(z+1,sizeof z)
#define e(a,q)if(a)A[q]^A[p]?l[q]++||(j[++k]=q):s[q]||(i[q]=p,u(q));
z,F,v,k,n,h,p,q,r,C,*x,*A,*i,*l,*s,*j,*m;u(p){s[m[++n]=p]=1;e(p%F-1,p-1)e(p%F,p+1)e(p>F,p-F)e(p<=F*v-F,p+F)}t(){f(q,k)l[j[q]]=0;f(q,n)s[m[q]]=0;k=n=0;i[p]=-1;u(p);}main(){void*E=picosat_init();if(scanf("%d,%d",&F,&v)-2)abort();z=F*v;for(x=b;scanf("%d,%d,%d",&r,&p,&q)==3;g(p),g(0))x[p=F-p+q*F]=r;f(p,F*v-F)if(p%F)g(p),g(p+1),g(p+F),g(p+F+1),g(0);for(A=b,i=b,l=b,s=b,j=b,m=b;!C;){picosat_sat(E,C=h=-1);f(p,F*v)A[p]=picosat_deref(E,p)>0,i[p]=0;f(p,F*v)if(x[p])if(i[q=p]){for(g(-q);i[q]+1;)q=i[q],g(-q);g(C=0);}else if(t(),r=n-x[p]){f(q,r<0?k:n)g(r<0?j[q]:-m[q]);g(C=0);}f(p,F*v)if(!i[p])if(t(),A[p]){g(-++z);f(q,k)g(j[q]);g(C=0);f(q,n)g(-m[q]),g(z),g(0);}else{C&=h++;f(q,k)g(-j[q]);g(++z);g(++z);g(0);f(q,F*v)g(s[q]-z),g(q),g(0);}}f(p,F*v)putchar(A[p]?35:46),p%F-1||puts("");}

Probieren Sie es online!

(Warnung: Bei diesem TIO-Link handelt es sich um eine 30-Kilobyte-URL, die eine verkleinerte Kopie von PicoSAT 965 enthält. Daher können Sie diese möglicherweise in einigen Browsern nicht laden, sie wird jedoch in mindestens Firefox und Chrome geladen.)

Wie es funktioniert

Wir initialisieren den SAT-Löser mit einer Variablen für jede Zelle (Land oder Wasser) und nur den folgenden Einschränkungen:

1. Jede nummerierte Zelle ist Land.
2. Jedes 2 × 2-Rechteck hat mindestens ein Land.

Die restlichen Einschränkungen lassen sich nur schwer direkt in SAT codieren. Stattdessen führen wir den Solver aus, um ein Modell zu erhalten, führen eine Folge von Tiefensuchen durch, um die verbundenen Bereiche dieses Modells zu finden, und fügen zusätzliche Einschränkungen wie folgt hinzu:

3. Fügen Sie für jede nummerierte Zelle in einer Landregion, die zu groß ist, eine Einschränkung hinzu, dass mindestens eine Wasserzelle unter den aktuellen Landzellen in dieser Region vorhanden sein sollte.
4. Fügen Sie für jede nummerierte Zelle in einer Landregion, die zu klein ist, eine Einschränkung hinzu, dass sich mindestens eine Landzelle unter den aktuellen Wasserzellen befinden sollte, die an diese Region grenzen.
5. Fügen Sie für jede nummerierte Zelle in derselben Landregion wie für eine andere nummerierte Zelle eine Einschränkung hinzu, dass sich mindestens eine Wasserzelle entlang des Pfades der aktuellen Landzellen zwischen ihnen befinden sollte (ermittelt durch Gehen der übergeordneten Zeiger, die bei der Tiefensuche übrig geblieben sind ).
6. Fügen Sie für jede Landregion, die keine nummerierten Zellen enthält, die entsprechenden Einschränkungen hinzu
   • Alle diese derzeitigen Landzellen sollten Wasser sein, oder
   • Mindestens eine der derzeitigen Wasserzellen, die an diese Region angrenzen, sollte Land sein.
7. Fügen Sie für jede Wasserregion Einschränkungen hinzu
   • Alle diese derzeitigen Wasserzellen sollten an Land sein oder
   • jede andere Zelle als diese aktuellen Wasserzellen sollte landen oder
   • Mindestens eine der derzeitigen Landzellen, die an diese Region angrenzen, sollte Wasser sein.

Dank der inkrementellen Schnittstelle zur PicoSAT-Bibliothek können wir den Solver einschließlich der hinzugefügten Einschränkungen sofort erneut ausführen, wobei alle vorherigen Schlussfolgerungen des Solvers erhalten bleiben. PicoSAT gibt uns ein neues Modell und wir wiederholen die obigen Schritte, bis die Lösung gültig ist.

Das ist bemerkenswert effektiv; Es löst 15 × 15 und 20 × 20 Instanzen in einem winzigen Sekundenbruchteil.

(Vielen Dank an Lopsy , der diese Idee vorgeschlagen hat, verbundene Bereiche in einem inkrementellen SAT-Solver vor einiger Zeit interaktiv einzuschränken .)

Einige größere Testfälle von puzzle-nurikabe.com

Eine zufällige Seite mit 15 × 15 Puzzles ( 5057541 , 5122197 , 5383030 , 6275294 , 6646970 , 6944232 ):

15,15 1,5,1 3,9,1 5,4,2 1,6,2 2,11,2 2,2,3 3,9,3 2,4,4 1,10,4 5,12,4 3,1,5 1,3,5 3,8,5 1,13,5 5,5,6 1,12,6 1,2,8 2,9,8 1,1,9 2,6,9 6,11,9 3,13,9 5,2,10 2,4,10 4,10,10 1,5,11 2,12,11 2,3,12 2,8,12 5,10,12 1,5,13 1,9,13 1,6,14 1,8,14
15,15 4,2,0 2,5,0 1,3,1 2,14,2 1,3,3 2,11,3 1,13,3 1,5,4 11,7,4 1,9,4 1,4,5 1,8,5 2,10,5 12,14,5 3,5,6 1,4,7 2,10,7 3,9,8 4,0,9 1,4,9 1,6,9 3,10,9 1,5,10 1,7,10 8,9,10 1,1,11 10,3,11 2,11,11 6,0,12 1,11,13 2,9,14 1,12,14
15,15 2,2,0 8,10,0 2,3,1 2,14,2 2,3,3 3,5,3 3,9,3 2,11,3 5,13,3 6,0,4 3,7,4 3,3,5 2,11,5 2,6,6 1,8,6 1,4,7 2,10,7 1,6,8 2,8,8 5,3,9 2,11,9 2,7,10 7,14,10 2,1,11 4,3,11 2,5,11 1,9,11 2,11,11 2,0,12 4,6,13 1,11,13 3,4,14 1,12,14
15,15 2,0,0 2,4,0 3,6,1 2,10,1 1,13,1 2,5,2 2,12,2 3,0,3 2,2,3 4,7,3 2,9,3 1,14,3 1,4,4 1,8,4 2,12,5 4,2,6 3,4,6 1,14,6 7,7,7 1,10,8 2,12,8 3,2,9 2,14,9 2,0,10 2,6,10 1,10,10 2,5,11 4,7,11 2,12,11 1,14,11 3,2,12 3,9,12 1,1,13 2,4,13 3,8,13 2,10,14 5,14,14
15,15 1,3,0 1,14,0 3,7,1 3,10,1 2,13,1 3,1,2 4,5,2 2,12,3 3,3,4 1,8,4 1,1,5 3,5,5 1,9,5 5,13,5 3,3,6 1,8,6 2,2,7 2,12,7 1,6,8 1,8,8 2,11,8 2,1,9 4,5,9 2,9,9 2,13,9 2,6,10 4,11,10 1,2,11 3,9,12 2,13,12 3,1,13 2,4,13 3,7,13 1,0,14
15,15 2,8,0 2,4,1 2,7,1 1,10,1 6,4,3 1,1,4 12,5,4 3,11,4 5,13,4 3,10,5 3,0,6 1,6,6 2,8,6 4,13,7 2,3,8 1,6,8 3,8,8 2,14,8 2,4,9 5,1,10 4,3,10 1,9,10 6,13,10 3,8,11 1,10,11 3,4,13 2,7,13 3,10,13 1,6,14 1,14,14

Eine zufällige Seite mit 20 × 20 normalen Puzzles ( 536628 , 3757659 ):

20,20 1,0,0 3,2,0 2,6,0 1,13,0 3,9,1 3,15,1 2,7,2 3,13,2 3,0,3 2,3,3 3,18,3 3,5,4 2,9,4 2,11,4 2,16,4 1,0,5 2,7,5 1,10,5 1,19,5 3,2,6 1,11,6 2,17,6 2,0,7 3,4,7 5,6,7 2,9,7 4,13,7 3,15,7 1,3,8 1,10,8 1,14,9 2,18,9 3,1,10 2,4,10 1,8,10 1,10,10 3,12,10 3,16,10 1,9,11 1,17,11 2,19,11 2,0,12 2,2,12 1,4,12 4,6,12 2,13,12 2,15,12 1,14,13 2,17,13 1,3,14 2,5,14 4,7,14 2,15,14 3,0,15 1,2,15 2,13,15 3,18,15 3,7,16 7,10,16 1,17,16 2,0,17 2,3,17 2,5,17 3,11,17 3,15,17 1,0,19 1,2,19 1,4,19 2,6,19 5,8,19 1,11,19 1,13,19 3,15,19 2,18,19
20,20 1,0,0 1,4,0 5,8,0 1,17,0 1,19,0 2,17,2 3,6,3 2,10,3 2,12,3 4,14,3 6,0,4 3,4,4 4,7,4 1,11,4 1,18,4 1,6,5 3,12,5 4,15,5 4,4,6 2,16,6 2,19,6 6,0,7 3,10,7 2,12,8 2,17,8 3,3,9 2,5,9 4,8,9 2,10,9 3,0,10 1,2,10 5,14,10 2,16,10 2,19,10 7,7,11 3,12,12 2,17,12 2,2,13 4,4,13 3,6,13 4,14,13 3,0,14 1,3,14 1,5,14 3,16,14 1,2,15 1,9,15 2,11,15 5,13,15 3,19,15 1,4,16 3,6,16 1,3,17 1,12,17 1,14,17 1,16,17 6,0,19 2,2,19 3,5,19 2,7,19 5,9,19 1,11,19 2,13,19 1,15,19 4,17,19

GLPK , (nicht konkurrierend) 2197 Bytes

Dies ist ein nicht konkurrierender Eintrag

• Ich folge nicht dem Eingabedatenformat (da GLPK nur Eingabedaten aus Dateien lesen kann) und
• GLPK scheint auf RIO nicht verfügbar zu sein.

Ich werde hier eine noch unbespielte, aber funktionierende Version retten. Je nach Feedback kann ich versuchen, es zu verkürzen und eine Erklärung hinzuzufügen, wenn Interesse besteht. Bisher dienen die Einschränkungsnamen als In-Place-Dokumente.

Die Hauptidee besteht darin, die Einschränkung "zusammenhängende Inseln" zu codieren, indem eine beibehaltene Flussvariable eingeführt wird, die eine vordefinierte Quelle an der Hinweisposition hat. Die Entscheidungsvariable is_islandspielt dann die Rolle von platzierbaren Senken. Durch die Minimierung der Gesamtsumme dieses Flusses werden die Inseln gezwungen, im Optimum verbunden zu bleiben. Die anderen Einschränkungen implementieren die verschiedenen Regeln eher direkt. Was mich verwirrt, dass ich noch zu brauchen scheine island_fields_have_at_least_one_neighbor.

Die Leistung dieser Formulierung ist jedoch nicht großartig. Wenn Sie die gesamte Komplexität mit einer großen Anzahl von Einschränkungen direkt verarbeiten, benötigt der Solver für das 15 x 15-Beispiel fast 15 Sekunden.

Code (noch nicht bespielt)

# SETS
param M > 0, integer; # length
param N > 0, integer; # width
param P > 0, integer; # no. of islands

set X := 0..N-1;  # set of x coords
set Y := 0..M-1;  # set of y coords
set Z := 0..P-1;  # set of islands

set V := X cross Y;
set E within V cross V := setof{
  (sx, sy) in V, (tx, ty) in V :

  ((abs(sx - tx) = 1) and (sy = ty)) or 
  ((sx = tx) and (abs(sy - ty) = 1))
} 
  (sx, sy, tx, ty);


# PARAMETERS
param islands{x in X, y in Y, z in Z}, integer, default 0;
param island_area{z in Z} := sum{x in X, y in Y} islands[x, y, z];

# VARIABLES
var is_river{x in X, y in Y}, binary;
var is_island{x in X, y in Y, z in Z}, binary;
var flow{(sx, sy, tx, ty) in E, z in Z} >= 0;

# OBJECTIVE
minimize obj: sum{(sx, sy, tx, ty) in E, z in Z} flow[sx, sy, tx, ty, z];

# CONSTRAINTS
s.t. islands_are_connected{(x, y) in V, z in Z}:

    islands[x, y, z] 
  - is_island[x, y, z]
  + sum{(sx, sy, tx, ty) in E: x = tx and y = ty} flow[sx, sy, x, y, z]
  - sum{(sx, sy, tx, ty) in E: x = sx and y = sy} flow[x, y, tx, ty, z]
  = 0;


s.t. island_contains_hint_location{(x, y) in V, z in Z}:

    is_island[x, y, z] >= if islands[x, y, z] > 0 then 1 else 0;


s.t. each_square_is_river_or_island{(x, y) in V}:

    is_river[x, y] + sum{z in Z} is_island[x, y, z] = 1;


s.t. islands_match_hint_area{z in Z}:

    sum{(x, y) in V} is_island[x, y, z] = island_area[z];


s.t. river_has_no_lakes{(x,y) in V: x > 0 and y > 0}:

  3 >= is_river[x, y] + is_river[x - 1, y - 1]
     + is_river[x - 1, y] + is_river[x, y - 1];


s.t. river_squares_have_at_least_one_neighbor{(x, y) in V}:

    sum{(sx, sy, tx, ty) in E: x = tx and y = ty} is_river[sx, sy] 
 >= is_river[x, y];


s.t. island_fields_have_at_least_one_neighbor{(x, y) in V, z in Z: island_area[z] > 1}:

    sum{(sx, sy, tx, ty) in E: x = tx and y = ty} is_island[sx, sy, z]
 >= is_island[x, y, z];


s.t. islands_are_separated_by_water{(x, y) in V, z in Z}:

    sum{(sx, sy, tx, ty) in E, oz in Z: x = sx and y = sy and z != oz} is_island[tx, ty, oz]
 <= 4 * P * (1 - is_island[x, y, z]);

solve;

for{y in M-1..0 by -1}
{
    for {x in X} 
    {
        printf "%s", if is_river[x, y] = 1 then "." else "#";
    }
    printf "\n";
}

Problemdaten

5 x 5

data;
param M := 5;
param N := 5;
param P := 5;
param islands :=
# x,y,z,area
  0,1,0,3
  4,1,1,1
  0,4,2,2
  2,4,3,2
  4,4,4,2;
end;

7 x 7

data;
param M := 7;
param N := 7;
param P := 8;
param islands :=
# x,y,z,area
  0,0,0,2 
  3,1,1,2 
  6,1,2,2 
  4,3,3,2 
  2,4,4,2 
  0,6,5,8 
  2,6,6,1 
  4,6,7,3;
end;

15 x 15

data;
param M := 15;
param N := 15;
param P := 34;
param islands :=
# x,y,   z,area
5,  1,   0, 1
9,  1,   1, 3
4,  2,   2, 5
6,  2,   3, 1
11, 2,   4, 2
2,  3,   5, 2
9,  3,   6, 3
4,  4,   7, 2
10, 4,   8, 1
12, 4,   9, 5
1,  5,  10, 3
3,  5,  11, 1
8,  5,  12, 3
13, 5,  13, 1
5,  6,  14, 5
12, 6,  15, 1
2,  8,  16, 1
9,  8,  17, 2
1,  9,  18, 1
6,  9,  19, 2
11, 9,  20, 6
13, 9,  21, 3
2,  10, 22, 5
4,  10, 23, 2
10, 10, 24, 4
5,  11, 25, 1
12, 11, 26, 2
3,  12, 27, 2
8,  12, 28, 2
10, 12, 29, 5
5,  13, 30, 1
9,  13, 31, 1
6,  14, 32, 1
8,  14  33, 1;
end;

Verwendung

Haben glpsolinstalliert, Modell als eine Datei (zB river.mod), Eingangsdaten in separater Datei (en) (zB 7x7.mod). Dann:

glpsol -m river.mod -d 7x7.mod

Dies und etwas Geduld werden die Lösung im angegebenen Ausgabeformat (zusammen mit "einigen" Diagnoseausgaben) ausgeben.

Python 3 , 1295 Bytes

Dies ist eine reine Python-Lösung. Es verwendet keine Bibliotheken und lädt die Karte über die Standardeingabe. Weitere Erklärung zu kommen. Dies ist mein erster Versuch, einen so großen Golf zu spielen. Unten befindet sich ein Link zum kommentierten und nicht golfenen Code.

L,S,O,R,F=len,set,None,range,frozenset
U,N,J,D,I=S.update,F.union,F.isdisjoint,F.difference,F.intersection
def r(n,a,c):
 U(c,P)
 if L(I(N(Q[n],C[n]),a))<2:return 1
 w=D(P,N(a,[n]));e=S();u=S([next(iter(w))])
 while u:n=I(Q[u.pop()],w);U(u,D(n,e));U(e,n)
 return L(e)==L(w)
def T(a,o,i,c,k):
 s,p,m=a
 for _ in o:
  t=s,p,N(m,[_]);e=D(o,[_])
  if t[2] in c:o=e;continue
  c.add(t[2]);n=D(Q[_],m);U(k,n)
  if not J(i,n)or not r(_,N(m,i),k):o=e
  elif s==L(t[2]):yield t
  else:yield from T(t,N(e,n),i,c,k)
s,*p=input().split()
X,Y=eval(s)
A=[]
l=1,-1,0,0
P=F((x,y)for y in R(Y)for x in R(X))
exec("Q%sl,l[::-1]%s;C%s(1,1,-1,-1),l[:2]*2%s"%(('={(x,y):F((x+i,y+j)for i,j in zip(',')if X>x+i>-1<y+j<Y)for x,y in P}')*2))
for a in p:a,x,y=eval(a);k=x,y;A+=[(a,k,F([k]))]
A.sort(reverse=1)
k=F(a[1]for a in A)
p=[O]*L([a for a in A if a[0]!=1])
g,h=p[:],p[:]
i=0
while 1:
 if g[i]is O:h[i]=S();f=O;g[i]=T(A[i],Q[A[i][1]],D(N(k,*p[:i]),[A[i][1]]),S(),h[i])
 try:p[i]=g[i].send(f)[2]
 except:
  f=I(N(k,*p[:i]),h[i]);g[i]=p[i]=O;i-=1
  while J(p[i],f):g[i]=p[i]=O;i-=1
 else:
  i+=1
  if i==L(p):
   z=N(k,*p)
   if not any(J(z,F(zip([x,x+1]*2,[y,y,y+1,y+1])))for x in R(X-1)for y in R(Y-1)):break
   for c in h:U(c,z)
b=[X*['.']for i in R(Y)]
for x,y in z:b[y][x]='#'
for l in b[::-1]:print(''.join(l))

Probieren Sie es online!

Schauen Sie sich den Code ohne Golf an .