Филломино Солвер

Fillomino - это головоломка, в которой вы заполняете сетку полиомино . Каждое полиомино представляет собой область смежных клеток. Представление сетки показывает, какой размер polyomino покрывает каждую ячейку. Например, пентомино (5) будет показано как 5в каждой из пяти смежных клеток (см. Ниже). Два полиомино одинакового размера не могут иметь общую границу, но могут граничить по диагонали.

Для каждой загадки вы начинаете с нескольких знаков и должны заполнить оставшиеся ячейки. Простой пример головоломки и решения:

Ваша задача: Задать квадратную головоломку, решить ее и вывести ответ. Ввод может быть через стандартный ввод данных, один аргумент командной строки или текстовый файл. Ввод будет дан как целое число n, за которым следуют nстроки nцифр каждая. Пустые ячейки будут даны как точки ( .). Для приведенного выше примера головоломки это будет:

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

Вывод - это решаемая головоломка, заданная по nстрокам nцифрами, в консоль или текстовый файл:

33366
55446
55466
51462
33312

Если головоломка не действительна, выведите 0. Головоломка может быть недействительной, если ввод неверен или нет решения. Если существует несколько решений, вы можете вывести одно или все из них.

Так как каждая ячейка представлена ​​одной цифрой, все головоломки будут состоять только из размера полиомино 9и под ним. Если это невозможно решить без больших полиомино, считайте его недействительным.

Правильные ответы решат любую головоломку, а не просто выводят решения для тестовых случаев. Никаких внешних ресурсов, будь то онлайн или локально. Если случается , что язык с встроенной функцией решающего fillomino, вы не можете использовать его. Короче, играй честно .

Прецедент:

Входные данные:

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

Вывод (возможное решение):

322133315
355445555
315443334
235531444
233135551
141535515
344553155
324553553
321223133

Помните, что у некоторых полиомино нет заданных номеров, а у некоторых больше одного. Существует не отношения один-к-одному между числом данности и числом полимино.

Оценка по стандартному коду-гольфу, размер программы в байтах.

4882 персонажа - Java

Не очень удачное решение (т. Е. 4800 символов - это много) Может быть немного лучше, потому что 1 или 2 отладочные линии печати все еще там. Я думаю, что я могу еще немного сократить с точки зрения бесполезного / оптимизированного кода.

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

Никогда не видя Полемино до этого, я читал о том, что они из себя представляют, и, даже не глядя на решение алгоритмов, просто придумал свои (довольно медленно).

В основном, часто использует рекурсию ... Находит неполное Поломино, пытается завершить его. Находит пустое пространство, перебирает 1-9 через все квадраты в кармане, устанавливает этот карман на это значение. Если карман заполнен, он пытается найти другой карман, а затем повторяется до конца. Я не мог заставить его работать для сетки размера 9 ... Я имею в виду, по крайней мере, одну оптимизацию, которая могла бы заставить ее работать в течение разумного времени для 9. Возможно, скоро я попытаюсь это реализовать.