Fillomino Solver

Fillomino ist ein Puzzle, bei dem Sie ein Gitter mit Polyomino füllen . Jedes Polyomino ist ein Bereich zusammenhängender Zellen. Die Rasterdarstellung zeigt, welche Polyomino-Größe jede Zelle bedeckt. Zum Beispiel würde ein Pentomino (5) wie 5in jeder der fünf zusammenhängenden Zellen gezeigt (siehe unten). Zwei gleich große Polyominos können sich keinen Rand teilen, sondern dürfen diagonal angrenzen.

Für jedes Rätsel müssen Sie eine Reihe von Angaben machen und die verbleibenden Felder ausfüllen. Ein einfaches Beispiel Puzzle und Lösung:

Ihre Aufgabe: Lösen Sie ein quadratisches Rätsel und geben Sie die Antwort aus. Die Eingabe kann über stdin, ein einzelnes Befehlszeilenargument oder eine Textdatei erfolgen. Die Eingabe erfolgt als Ganzzahl n, gefolgt von jeweils neiner nZiffernreihe. Leere Zellen werden als Punkte ( .) angegeben. Für das obige Beispielpuzzle wäre es:

5
3..66
5.4.6
.54.6
.1.6.
..312

Die Ausgabe ist das Rätsel gelöst, da auf nZeilen von nZiffern, auf Konsole oder Textdatei:

33366
55446
55466
51462
33312

Wenn das Puzzle nicht gültig ist, wird ausgegeben 0. Ein Puzzle kann ungültig sein, wenn die Eingabe fehlerhaft ist oder es keine Lösung gibt. Wenn es mehrere Lösungen gibt, können Sie eine oder alle ausgeben.

Da jede Zelle durch eine einzelne Ziffer dargestellt wird, bestehen alle Puzzlespiele aus Polyominoen der Größe 9und darunter. Wenn es nicht möglich ist, ohne größere Polyominos zu lösen, halten Sie es für ungültig.

Gültige Antworten lösen ein bestimmtes Rätsel und geben Lösungen nicht einfach in Testfällen aus. Keine externen Ressourcen, sei es online oder lokal. Wenn es geschieht mit einem eingebauten in Fillomino Lösung Funktion eine Sprache zu sein, können Sie es nicht verwenden können. Kurz gesagt, fair spielen .

Testfall:

Eingang:

9
..21.3..5
.5...5..5
.1.44.334
...53.4..
2.3.3..5.
1.15.5.15
..45..1..
.24.53.53
....2....

Ausgabe (eine mögliche Lösung):

322133315
355445555
315443334
235531444
233135551
141535515
344553155
324553553
321223133

Denken Sie daran, dass einige Polyominos keine bestimmten Zahlen haben und einige mehr als eine. Es gibt keine Eins-zu-Eins-Beziehung zwischen der Anzahl der Gaben und der Anzahl der Polyominos.

Punktzahl ist Standard-Code-Golf, Größe des Programms in Bytes.

4882 Zeichen - Java

Keine sehr gute Lösung (dh 4800 Zeichen sind keine guten Tipps) Könnte ein bisschen besser sein, wenn noch 1 oder 2 Debug-Druckzeilen vorhanden sind. Ich denke, ich kann noch einiges an nutzlosem / optimiertem Code reduzieren.

import java.util.*;import java.awt.Point;public class G{public static void main(String[]args){new G();}Scanner z=new Scanner(System.in);public G(){s=z.nextInt();z.nextLine();int g[][]=new int[s][s];for(int i=0;i<s;i++)Arrays.fill(g[i],-1);for(int i=0;i<s;i++){String line=z.nextLine();for(int j=0;j<s;j++)if(line.charAt(j)!='.')g[i][j]=Integer.parseInt(Character.toString(line.charAt(j)));}System.out.println();if(y(g)){for(int i=0;i<s;i++)for(int j=0;j<s;j++)System.out.print(g[i][j]);System.out.println();}else System.out.println(0);}private boolean x(Collection<Point>c,int[][]d){if(c.size()==0)return true;int j=0;for(Iterator<Point>k=c.iterator();k.hasNext();k.next(),j++){for(int sol=9;sol>=0;sol--){int[][]a=new int[s][s];for(int i=0;i<s;i++)a[i]=Arrays.copyOf(d[i],s);List<Point>b=new ArrayList<Point>();for(Point p:c)if(!b.contains(p))b.add(new Point(p));a[b.get(j).x][b.get(j).y]=sol;if(w(a,b.get(j))){if(x(b,a)){for(int i=0;i<s;i++)d[i]=Arrays.copyOf(a[i],s);c.clear();c.addAll(b);return true;}}}}return false;}int s;private boolean y(int[][]d){int[][] a=new int[s][s];for (int i = 0; i<s;i++)a[i]=Arrays.copyOf(d[i],s);List<Point> incomplete=new ArrayList<Point>();if(r(a)&&s(a)){a(a);System.exit(0);}else if(!r(a)){q("INVALID FROM MAIN, ",12);return false;}for(int i=0;i<s;i++)for(int j=0;j<s;j++){if(a[i][j]!=-1)if(t(new Point(i,j),a,null,a[i][j]).size()!=a[i][j]){if(w(a,new Point(i,j))){a(a);if(y(a)){for(int i=0;i<s;i++)d[i]=Arrays.copyOf(a[i],s);return true;}else return false;}else return false;}}for(int i=0;i<s;i++)for(int j=0;j<s;j++)if(a[i][j]==-1){Set<Point>c=t(new Point(i,j),a,null,-1);if(x(c,a)){if(y(a)){for(int i=0;i<s;i++)d[i] = Arrays.copyOf(a[i], s);return true;}else return false;}else return false;}q("How did you get here",1);return false;}private boolean w(int[][]d,Point b){List<Point>c;Set<Point>a;a=t(b,d,null,d[b.x][b.y]);c=new ArrayList<Point>(u(b,d,null,d[b.x][b.y]));int h=d[b.x][b.y];int g=h-a.size();if(c.size()<g){return false;}else if(v(c,h,h,new ArrayList<Point>(a),0,d))return true;else return false;}private boolean v(List<Point>c,int h,int g,List<Point>e,int f,int[][]d){if(e==null)e=new ArrayList<Point>();int[][]a=new int[s][s];for(int i=0;i<s;i++)for(int k=0;k<s;k++)a[i][k]=d[i][k];if(f<g&&e.size()<g){for(int i=0;i<c.size();i++){if(!e.contains(c.get(i))){if(d[c.get(i).x][c.get(i).y]==h){for(Point c:e){a[c.x][c.y]=h;}Set<Point> u=t(e.get(0),a,null,h);Set<Point>v=t(c.get(i),a,null,h);if(!Collections.disjoint(u,v)){u.addAll(v);List<Point>uList=new ArrayList<Point>(u);if(v(c,h,g,uList,f+1,a)){q("this e sucess",2);if(y(d)){e.addAll(uList);return true;}}else;}for(int l=0;l<s;l++)for(int k=0;k<s;k++)a[l][k]=d[l][k];}else if(e.add(c.get(i))){if(v(c,h,g,e,f+1,d)){q("this e sucess",2);if(y(d))return true;}}if(e.contains(c.get(i)))e.remove(c.get(i));}}return false;}else if(f>g||e.size()>g){if(f>g){q("Your over the g. ");return false;}else return false;}else{for(Point c:e){a[c.x][c.y]=h;}if(r(a)){if(y(a)){for(int i=0;i<s;i++)d[i]=Arrays.copyOf(a[i],s);q("complete(a) is true, ",4);return true;}else{return false;}}else{return false;}}}private void q(String out,int i){System.err.println(out+". exit code: "+i);System.exit(i);}private void q(String a){q(a,0);}private boolean r(int[][] d){for(int i=0;i<s;i++)for(int j=0;j<s;j++)if(d[i][j]!=-1){Set<Point>same=t(new Point(i,j),d,null,d[i][j]);if(same.size()>d[i][j]){return false;}Set<Point>fae=u(new Point(i,j),d,null,d[i][j]);if(u(new Point(i,j),d,null,d[i][j]).size()<d[i][j]){return false;}}return true;}private Set<Point> u(Point p,int[][]d,Set<Point>u,int i){u=(u==null)?new HashSet<Point>():u;if(d[p.x][p.y]==i||d[p.x][p.y]==-1)u.add(p);int x=p.x,y=p.y;Point t=new Point();if(x+1<s&&(d[x+1][y]==i||d[x+1][y]==-1)){if(u.add(new Point(x+1,y)))u=u(new Point(x+1,y),d,u,i);}if(y+1<s&&(d[x][y+1]==i||d[x][y+1]==-1)){if(u.add(new Point(x,y+1)))u=u(new Point(x,y+1),d,u,i);}if(x-1>=0&&(d[x-1][y]==i||d[x-1][y]==-1)){if(u.add(new Point(x-1,y)))u=u(new Point(x-1,y),d,u,i);}if(y-1>=0&&(d[x][y-1]==i||d[x][y-1]==-1)){if(u.add(new Point(x,y-1)))u=u(new Point(x,y-1),d,u,i);}return u;}private Set<Point> t(Point p,int[][]d,Set<Point>u,int i){u=(u==null)?new HashSet<Point>():u;if(d[p.x][p.y]==i)u.add(p);int x=p.x,y=p.y;Point t=new Point(p);if(x+1<s&&d[x+1][y]==i){if(u.add(new Point(x+1,y)))u=t(new Point(x+1,y),d,u,i);}if(y+1<s&&d[x][y+1]==i){if(u.add(new Point(x,y+1)))u=t(new Point(x,y+1),d,u,i);}if(x-1>=0&&d[x-1][y]==i){if(u.add(new Point(x-1,y)))u=t(new Point(x-1,y),d,u,i);}if(y-1>=0&&d[x][y-1]==i){if(u.add(new Point(x,y-1)))u=t(new Point(x,y-1),d,u,i);}return u;}private boolean s(int[][]d){for(int i=0;i<s;i++)for(int j=0;j<s;j++)if(t(new Point(i,j),d,null,d[i][j]).size()!=d[i][j])return false;return true;}private void a(int[][]d){for(int i=0;i<s;i++){for(int j=0;j<s;j++){System.out.printf("%1s",d[i][j]==-1?".":Integer.toString(d[i][j]));}System.out.println("");}}}

Nachdem ich Polyominoes noch nie zuvor gesehen hatte, las ich nach, was sie sind, und ohne mir Gedanken über das Lösen von Algorithmen zu machen, machte ich mir nur meine eigenen (ziemlich langsamen).

Verwendet im Grunde viel Rekursion ... Findet ein unvollständiges Polyomino und versucht es zu vervollständigen. Findet eine leere Stelle, durchläuft alle Felder in der Tasche mit den Schleifen 1-9 und setzt diese Tasche auf diesen Wert. Wenn das Fach vollständig ist, versucht es, ein anderes Fach zu finden, und wiederholt dies, bis es fertig ist. Ich konnte es für ein Raster der Größe 9 nicht zum Laufen bringen ... Ich habe mindestens eine Optimierung im Sinn, die es in einer angemessenen Zeit für 9 zum Laufen bringen könnte. Könnte versuchen, dies bald zu implementieren.