Das Spiel

In letzter Zeit hat ein süchtig machendes Spiel namens Logic Dots auf meinem Handy viel Zeit in Anspruch genommen, das mich dazu inspiriert hat, diese Herausforderung zu schreiben. Es ist einfacher, die Regeln zu erklären, wenn ich Ihnen die Spielanzeige zeige. Hier ist ein Screenshot eines ungelösten und gelösten Puzzles:

Hier gibt es drei Hauptmerkmale.

1. Das Spielbrett (das 4x4-Gitterfeld in der Mitte)
2. Die erforderlichen Formen (die verknüpften Punkte in der zweiten Leiste von oben, unter der Partitur und im Menü usw.), die alle Linien oder a1 Rechtecke sind
3. Die Zahlen über den Zeilen und Spalten, die angeben, wie viele Punkte in der Spalte enthalten sein müssen, um eine Lösung zu finden

Das Ziel des Spiels ist es, die erforderlichen Formen in das Gitter einzupassen. Sie können die Formen drehen, sie können jedoch nicht diagonal eingehen.

Beachten Sie in der Lösung, dass alle Formen genau einmal erstellt werden (da sie nur einmal in den erforderlichen Formen vorliegen). In diesem Fall sind sie alle horizontal, können jedoch auch vertikal sein. Die rosa ausgefüllten Quadrate bezeichnen nicht verwendete Quadrate.

Hier ist ein größeres und etwas komplizierteres Raster:

Beachten Sie, dass im ungelösten Rätsel bereits einige Felder ausgefüllt sind. Die ausgegrauten Felder stehen für blockierte Felder, auf die Sie KEINEN Punkt setzen KÖNNEN. Die Punkte mit Schwänzen zeigen an, dass sich ein Punkt an diesem Punkt befindet, und er verweist auf mindestens einen weiteren Punkt in der Richtung des Schwanzes, jedoch nicht in einer anderen Richtung (einschließlich der entgegengesetzten Richtung).

Notation

Für den Rest dieses Beitrags verweise ich mit den folgenden Symbolen auf das Board:

• <,>, ^, v - Bezeichnet einen zuvor platzierten Punkt mit einem Ende, das sich in Richtung des Punkts erstreckt
• * - Bezeichnet einen Punkt. Wenn auf einem ungelösten Gitter (Eingabe) angegeben, handelt es sich um eine individuelle Form. Wenn in Ausgabe, dann ist es mit den Punkten um ihn herum verbunden.
• # - Zeigt ein blockiertes Gitterquadrat an (wo Sie keinen Punkt platzieren können)
• -, | (Bindestrich und Strich) - Bezeichnet einen Punkt mit einem rechten und einem linken Ende sowie einen Punkt mit einem oberen bzw. unteren Ende
• ** (Leerzeichen) - ** Bezeichnet ein Leerzeichen

Mit diesen Symbolen kann der zuletzt genannte Beispielfall (ungelöst) wie folgt dargestellt werden:

 <    



    # 
 ^ #

Und die Lösung kann wie folgt dargestellt werden:

*< * *
   *  
     *
 *   *
 * *#*
 ^ # *

Beachten Sie, dass sich keine zwei Formen horizontal, vertikal oder diagonal berühren können , sodass der folgende Fall nicht gültig ist:

 *** 
**   
  ** 

Herausforderung

Ihre Herausforderung besteht darin, alle Logik-Punkte-Rätsel zu lösen, von 4x4 bis einschließlich 9x9. Sie erhalten vier Eingabezeilen und dann den Spielplan. Die Zeilen lauten wie folgt:

• 1. Zeile, Formen - Die zu findenden Formen, jeweils in der Form angegeben sizexquantity(z. B. 3x2für zwei Formen der Länge drei) und durch ein Leerzeichen getrennt. Beispielzeile:3x1 2x1 1x1
• 2. Zeile, Spalten - Eine durch Leerzeichen getrennte Liste der erforderlichen Punktanzahl für jede Spalte. Beispielzeile:1 1 2 2
• 3. Zeile, Zeilen - Eine durch Leerzeichen getrennte Liste der erforderlichen Punktanzahl für jede Zeile. Beispielzeile:3 0 3 0
• 4. Zeile, Boardgröße - Eine einzelne Ganzzahl, die Boardgröße, B

Die Karte ist dann gegeben und enthält BEingabezeilen, die die Karte unter Verwendung der oben erwähnten Notation darstellen. Die vollständige Eingabe für den letzteren Beispielfall lautet beispielsweise wie folgt:

4x1 3x1 2x2 1x2
1 4 0 3 0 5
4 1 1 2 3 2
6
 <    



    # 
 ^ #  

Ihr Programm gibt dann die gelöste Karte in derselben Notation aus. Die übereinstimmende Ausgabe für die obige Eingabe lautet wie folgt:

** * *
   *  
     *
 *   *
 * *#*
 * # *

Beachten Sie, dass ein Spielbrett mehrere Lösungen haben kann. In diesem Fall geben Sie einfach eine gültige Lösung aus. Außerdem muss Ihr Programm auf einem vernünftigen Desktop-Computer für ein kompliziertes 10x10-Raster innerhalb von 10 Sekunden eine korrekte Lösung ausgeben.

Das ist Codegolf, also gewinnen die wenigsten Bytes.

Testfälle

Eingang 1

3x2 1x4
2 2 3 1 2
4 0 3 0 3
5


    #
  #  
    *

Ausgang 1

*** *

 ***#
  #  
* * *

Eingang 2

3x1 1x6
2 0 4 0 3
3 1 2 1 2
5
*    


   # 

Ausgang 2

* * *
  *  
  * *
*  # 
  * *

Eingang 3

5x1 4x1 2x1 1x2
1 2 3 3 2 2
0 5 0 4 0 4
6
#     
  -   


 #    
   <  

Ausgang 3

#     
 *****

 **** 
 #    
* ** *

Python 2: 766 739 696 663 633 Bytes

def f(B,S,o=0):
 if[]==S:print'\n'.join(B);exit()
 s=S[0]
 for i in r:
  for j in R(Z-s+1):
   if(B[i][j]in' '+'>v'[o])*(B[i][j+s-1]in' '+'<^'[o])*({' ','-|'[o]}>=set(B[i][j+1:j+s-1]))*all(B[x][y]in'# 'for x,y in [(x,y)for y in R(j-1,j+s+1)for x in i-1,i+1]+[(i,j-1),(i,j+s)]if 0<=x<Z>y>=0):q=B[:];q[i]=q[i][:j]+'*'*s+q[i][j+s:];q=(q,t(q))[o];any((t(q)+q)[k].count('*')>m[k]for k in R(Z+Z))or f(q,S[1:])
 o or f(t(B),S,1)
y=raw_input;S=[];s=str.split
for i in s(y()):u,v=map(int,s(i,'x'));S+=[u]*v
m=map(int,s(y())+s(y()));Z=input();R=range;r=R(Z);B=[y()for _ in r];J=''.join;t=lambda x:map(J,zip(*x))
f(B,S[:len(S)-J(B).count('*')])

Sehen Sie, wie es online funktioniert: Ideone.com (Die Online-Version ist möglicherweise zu langsam für große und schwierige Raster, offline sollte es in Ordnung sein)

Die Eingabe erfolgt über stdin, kopieren Sie einfach die Zeilen aus dem OP und fügen Sie sie ein (aber seien Sie vorsichtig, Stapelaustausch löscht manchmal Leerzeichen oder Zeilen).

Einige grundlegende Ideen dieses Codes: Er verwendet eine rekursive Funktion f. fversucht eine Form auf dem Brett zu platzieren. Für jeden möglichen Standort ruft er sich mit der geänderten Karte auf. Es gibt 3 Schleifen. obestimmt die Ausrichtung (2 - horizontal, 3 - vertikal). Die Form wird immer horizontal platziert, daher wird am Ende o=2die Tafel mit der Funktion transponiert t. iist die Zeile und jsind alle möglichen Startspalten. Dann passieren viele Überprüfungen, ob die Enden der Form gültige Zeichen haben, ob die Mitte der Form gültige Zeichen hat und ob die Umgebung leer ist.

JavaScript (ES6) 661 667 695 702 745 755 786 790 784 798

In Bearbeitung, kann gekürzt werden. Wahrscheinlich zu langsam in einem komplexen Raster. Vielleicht nicht.

Bearbeiten Sie etwas länger, viel schneller.
Edit 2 Bugfix, Spalten / Zeilen prüfen. Jetzt geht es übrigens schneller

Die M-Funktion ist die Hauptfunktion. Der Parameter w ist eine mehrzeilige Zeichenfolge mit allen Eingaben. Die Funktion analysiert die Eingabe und bereitet eine Startkarte vor. Die Zeichen <>^v|-*in der Starttafel werden durch ersetzt ,. Jedes Zeichen ,muss durch *die richtige Lösung ersetzt werden.

Die R-Funktion versucht rekursiv, alle Formen auf der Tafel zu platzieren. Wenn eine Form platziert wird, ruft sie sich selbst auf, indem sie eine kürzere Liste von Formen und die geänderte Karte übergibt. Wenn alle Formen platziert sind, kann eine Lösung immer noch ungültig sein, wenn sie ,nicht durch ersetzt wird *.

Die P-Funktion testet, ob eine Form an einer bestimmten Position und Ausrichtung platziert werden kann. Es prüft alle Kosten (innerhalb der Tafel, keine Überlappung, keine Berührung, gültige Zeilen- und Spaltenanzahl)

M=w=>(
  [x,c,r,z]=w=w[S='split'](n='\n'),
  (b=[...w.slice(4).join(n)])
  .map((c,p)=>~(k='*<>-*^v|'.indexOf(c))&&[(q=k>3?z:1,0),k&1&&-q,k&2&&q].map(o=>b[p+o]=0),
    c=c[S](e=' '),r=r[S](e),w=z++,f='*',s='',x[S](e).map(v=>s+=v[0].repeat(v[2]))),
  R=(s,b,x=0,y=0,n=s[0],V=i=>b[i]>'#',
    P=(p,o,q,t,g,l,d=[...b])=>{
        if(l<z-n&!V(p+o*l-o)&!V(p+o*l+o*n))
        {
          for(i=-1;v=d[p],++i<w;p+=o,t-=v==f)
            if(i>=l&i-n<l)
              for(v!=e&v!=0|[q,w,~z].some(w=>V(p+w)|V(p-w))?t=0:d[p]=f,j=o*i,u=k=0;
                  ++k<z;(u+=d[j]==f)>g[i]?t=0:j+=q);
          return t>=n&&d.join('')
        }
    })=>{
    if(b){
      if(!n)return~b.search(0)?0:b;
      for(s=s.slice(1);y<w||(y=0,++x<w);++y)
        if(h=R(s,P(y*z,1,z,r[y],c,x))||n>1&&R(s,P(x,z,1,c[x],r,y)))return h
    }
  })(s,b)

Test In FireFox / Firebug - Konsole

;['3x2 1x4\n2 2 3 1 2\n4 0 3 0 3\n5\n     \n     \n    #\n  #  \n    *\n'
,'3x1 1x6\n2 0 4 0 3\n3 1 2 1 2\n5\n*    \n     \n     \n   # \n     \n'
,'5x1 4x1 2x1 1x2\n1 2 3 3 2 2\n0 5 0 4 0 4\n6\n#     \n  -   \n      \n      \n #    \n   <  \n'
,'4x1 3x1 2x2 1x2\n1 4 0 3 0 5\n4 1 1 2 3 2\n6\n <    \n      \n      \n      \n    # \n ^ #  \n']
.forEach(x=>console.log(x,M(x).replace(/ /g,'`'))) // space replaced with ` for clarity

Ausgabe (Gesamtausführungszeit <1sec)

3x2 1x4
2 2 3 1 2
4 0 3 0 3
5


    #
  #  
    *

***`*
`````
`***#
``#``
*`*`*

3x1 1x6
2 0 4 0 3
3 1 2 1 2
5
*    


   # 


*`*`*
``*``
``*`*
*``#`
``*`*

5x1 4x1 2x1 1x2
1 2 3 3 2 2
0 5 0 4 0 4
6
#     
  -   


 #    
   <  

#`````
`*****
``````
`****`
`#````
*`**`*

4x1 3x1 2x2 1x2
1 4 0 3 0 5
4 1 1 2 3 2
6
 <    



    # 
 ^ #  

**`*`*
```*``
`````*
`*```*
`*`*#*
`*`#`*