Fillomino Solver

Fillomino to układanka, w której wypełniasz siatkę poliominoami . Każdy poliomino jest obszarem sąsiadujących komórek. Reprezentacja siatki pokazuje, jaki rozmiar poliomino pokrywa każdą komórkę. Na przykład pentomino (5) byłoby pokazane jak 5w każdej z pięciu sąsiadujących komórek (patrz poniżej). Dwa poliomino o tym samym rozmiarze nie mogą mieć granicy, ale mogą graniczić po przekątnej.

Dla każdej układanki zaczynasz z kilkoma dawcami i musisz wypełnić pozostałe komórki. Prosta przykładowa łamigłówka i rozwiązanie:

Twoje zadanie: mając kwadratową łamigłówkę, rozwiąż ją i wyślij odpowiedź. Dane wejściowe mogą być przesyłane przez stdin, pojedynczy argument wiersza poleceń lub plik tekstowy. Dane wejściowe będą podawane jako liczby całkowite n, po których będą następować nwiersze ncyfr. Puste komórki zostaną podane jako kropki ( .). W powyższej przykładowej układance byłoby to:

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

Dane wyjściowe to rozwiązana łamigłówka podana w nwierszach ncyfr do konsoli lub pliku tekstowego:

33366
55446
55466
51462
33312

Jeśli układanka nie jest poprawna, wyjdź 0. Układanka może być nieprawidłowa, jeśli dane wejściowe są zniekształcone lub nie ma rozwiązania. Jeśli istnieje wiele rozwiązań, możesz wypisać jedno lub wszystkie z nich.

Ponieważ każda komórka jest reprezentowana przez jedną cyfrę, wszystkie łamigłówki będą się składały z rozmiaru poliomino 9i tylko poniżej. Jeśli nie można rozwiązać bez większych poliominoów, należy uznać go za nieważny.

Prawidłowe odpowiedzi rozwiążą każdą zagadkę, a nie tylko wypisują rozwiązania przypadków testowych. Brak zewnętrznych zasobów, czy to online, czy lokalnych. Jeśli zdarzy się, że istnieje język z wbudowaną funkcją rozwiązywania problemów fillomino, nie możesz go użyć. Krótko mówiąc, graj uczciwie .

Przypadek testowy:

Wejście:

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....

Wyjście (możliwe rozwiązanie):

322133315
355445555
315443334
235531444
233135551
141535515
344553155
324553553
321223133

Pamiętaj, że niektóre poliominy nie mają podanych liczb, a niektóre mają więcej niż jedną. Jest nie relacja jeden-do-jednego między liczbą Givens i liczby polyominoes.

Wynik to standardowy kod-golf, rozmiar programu w bajtach.

4882 znaków - Java

Niezbyt golfowe rozwiązanie (tzn. 4800 znaków to dużo lotttttttttt). Można by grać w golfa nieco więcej, ponieważ 1 lub 2 linie debugowania są nadal dostępne. Myślę, że mogę jeszcze trochę zredukować pod względem bezużytecznego / zoptymalizowanego kodu.

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("");}}}

Nigdy wcześniej nie widziałem Polyominoes, czytam o tym, czym one są, i nie patrząc na rozwiązywanie alrogitmów, które właśnie stworzyłem (dość wolno).

Zasadniczo często korzysta z rekurencji ... Znajduje Polyomino, który jest niekompletny, próbuje go wykonać. Znajduje puste miejsce, Pętle 1-9 przez wszystkie kwadraty w kieszeni, ustawia tę kieszeń na tę wartość. Jeśli kieszeń jest kompletna, próbuje znaleźć inną kieszeń, a następnie powtarza się do końca. Nie mogłem zmusić go do pracy dla siatki o rozmiarze 9 ... Mam na myśli co najmniej jedną optymalizację, która mogłaby sprawić, że zadziała w rozsądnym czasie dla 9. Mogę spróbować to wkrótce wprowadzić.