مساله:
نکته: پس از تکمیل این کاتا ، نسخه 15×15 وجود دارد که می توانید امتحان کنید. و پس از اتمام آن ، می توانید نسخه چند سایز را انجام دهید که تا 50×50 افزایش می یابد.
برای این کاتا، شما یک حل کننده Nonogram خواهید ساخت. 🙂
اگر نمی دانید Nonograms چیست، می توانید به برخی دستورالعمل ها نگاه کنید و همچنین برخی از Nonograms را در اینجا امتحان کنید.
برای این کاتا، شما فقط باید Nonograms در اندازه 5×5 را حل کنید. 🙂
دستورالعمل:
شما باید کلاس Nonogram و روش حل را تکمیل کنید:
public class Nonogram {
public static int[][] solve(int[][][] clues) {
//Your code here
return null;
}
}به شما سرنخ داده می شود و باید معمای حل شده را برگردانید. همه معماها قابل حل خواهند بود، بنابراین نیازی به نگرانی در مورد آن نیست. سرنخ ها یک آرایه سه بعدی از سرنخ های افقی خواهند بود ، سپس سرنخ های عمودی ، که شامل سرنخ های جداگانه هستن. به عنوان مثال ، برای Nonogram:
سرنخ ها در بالا و سمت چپ پازل هستند ، بنابراین در این مورد:
سرنخ های افقی عبارتند از: {{1، 1}، {4}، {1، 1، 1}، {3}، {1}} و سرنخ های عمودی عبارتند از: {{1}، {2}، {3 } ، {2 ، 1} ، {4}}. سرنخ های افقی از چپ به راست داده می شوند. اگر برای یک ستون بیش از یک سرنخ وجود داشته باشد ، ابتدا سرنخ بالایی داده می شود. سرنخ های عمودی از بالا به پایین داده شده است. اگر برای یک ردیف بیش از یک سرنخ وجود داشته باشد ، ابتدا چپ ترین سرنخ داده می شود.
بنابراین ، سرنخ داده شده برای روش حل به صورت {{{{1، 1}، {4}، {1، 1، 1}، {3}، {1}}، {{1}، {2}، { 3} ، {2 ، 1} ، {4}}} می باشد. ابتدا سرنخ های افقی و سپس سرنخ های عمودی در اختیار شما قرار می گیرد.
شما باید یک آرایه دو بعدی را به عنوان پاسخ خود بازگردانید. در این مورد ، Nonogram حل شده شبیه زیر است:
در آرایه دو بعدی ، باید از 0 برای یک مربع پر نشده و 1 برای یک مربع پر شده استفاده کنید. بنابراین ، در این مورد ، شما باید برگردید:
{{0, 0, 1, 0, 0},
{1, 1, 0, 0, 0},
{0, 1, 1, 1, 0},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 1}}
موفق باشید!!
اگر چیز مبهم یا گیج کننده ای وجود دارد، فقط به من اطلاع دهید 🙂
Description:
Once you complete this kata, there is a 15×15 Version that you can try. And once you complete that, you can do the Multisize Version which goes up to 50×50.
Description
For this kata, you will be making a Nonogram solver. 🙂
If you don’t know what Nonograms are, you can look at some instructions and also try out some Nonograms here.
For this kata, you will only have to solve 5×5 Nonograms. 🙂
Instructions
You need to complete the Nonogram class and the solve method:
public class Nonogram {
public static int[][] solve(int[][][] clues) {
//Your code here
return null;
}
}
You will be given the clues and you should return the solved puzzle. All the puzzles will be solveable so you will not need to worry about that.
The clues will be a three dimensional array of the horizontal clues, then the vertical clues, which will contain the individual clues. For example, for the Nonogram:
The clues are on the top and the left of the puzzle, so in this case:
The horizontal clues are: {{1, 1}, {4}, {1, 1, 1}, {3}, {1}}, and the vertical clues are: {{1}, {2}, {3}, {2, 1}, {4}}. The horizontal clues are given from left to right. If there is more than one clue for the same column, the upper clue is given first. The vertical clues are given from top to bottom. If there is more than one clue for the same row, the leftmost clue is given first.
Therefore, the clue given to the solve method would be {{{1, 1}, {4}, {1, 1, 1}, {3}, {1}}, {{1}, {2}, {3}, {2, 1}, {4}}}. You are given the horizontal clues first then the vertical clues second.
You should return a two-dimensional array as your answer. In this case, the solved Nonogram looks like:
In the two-dimensional array, you should use 0 for a unfilled square and 1 for a filled square. Therefore, in this case, you should return:
{{0, 0, 1, 0, 0},
{1, 1, 0, 0, 0},
{0, 1, 1, 1, 0},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 1}}
Good Luck!!
If there is anything that is unclear or confusing, just let me know 🙂
راه حل ها:
class Nonogram {
static int N=5;
static int[][] a;
static boolean found;
static boolean valid(String clue,int[] a){
int t,i;
String s="";
for(t=0,i=0;i<N;i++)
if(a[i]==1) t++; else
if(t>0) {s+=t;t=0;}
return (t>0?s+t:s).equals(clue);
}
static int[] col(int c){
int[] b=new int[N];
for(int i=0;i<N;i++) b[i]=a[i];
return b;
}
static void dfs(String[] clues, int i){
int y=i/N, x=i%N;
if(x==0 && y >0 && !valid(clues[N-1+y], a[y-1])) return;
if(x==0 && y==N && !valid(clues[N-1], col(N-1))) return;
if(x >0 && y==N-1 && !valid(clues[x-1], col(x-1))) return;
if(y==N) found = true;
if(!found) { a[y][x]=0; dfs(clues, i+1); }
if(!found) { a[y][x]=1; dfs(clues, i+1); }
}
static int[][] solve(int[][][] clues) {
int i=0;
String[] s=new String[2*N];
for(int[][] c:clues)
for(int [] d:c){
String t="";
for(int e:d) t+=e;
s[i++]=t;
}
a=new int[N][N];
found=false;
dfs(s,0);
return found?a:null;
}
}import java.util.Arrays;
public class Nonogram {
private static int[] baseSolutions(int[] in){
if(Arrays.equals(in, new int[]{0})){
return new int[]{0, 0, 0, 0, 0};
} else if(Arrays.equals(in, new int[]{1, 1, 1})){
return new int[]{1, 0, 1, 0, 1};
} else if(Arrays.equals(in, new int[]{1, 3})){
return new int[]{1, 0, 1, 1, 1};
} else if(Arrays.equals(in, new int[]{2, 2})){
return new int[]{1, 1, 0, 1, 1};
} else if(Arrays.equals(in, new int[]{3, 1})){
return new int[]{1, 1, 1, 0, 1};
} else if(Arrays.equals(in, new int[]{5})){
return new int[]{1, 1, 1, 1, 1};
} else if(Arrays.equals(in, new int[]{4})){
return new int[]{-1, 1, 1, 1, -1};
} else if(Arrays.equals(in, new int[]{3})){
return new int[]{-1, -1, 1, -1, -1};
} else if(Arrays.equals(in, new int[]{2,1})) {
return new int[]{-1, 1, -1, -1, -1};
} else if(Arrays.equals(in, new int[]{1,2})){
return new int[]{-1, -1, -1, 1, -1};
} else
return null;
}
public static int[][] solve(int[][][] clues) {
//result tömb készítése és feltöltése -1-gyel
int[][] result = new int[5][5];
for (int[] ints : result) {
System.arraycopy(new int[]{-1, -1, -1, -1, -1},0, ints,0,5);
}
//össz kocka és megoldott kocka deklarálás
int solvedAmount = 0;
int allAmount = 0;
//össz kocka megszámolása
allAmount = Arrays.stream(clues[0]).flatMapToInt(Arrays::stream).sum();
//biztos sorok feltöltése
for (int i = 0; i < 5; i++) {
int[] rowValue= clues[1][i];
if(baseSolutions(rowValue)!=null){
System.arraycopy(baseSolutions(rowValue),0,result[i],0,5);
}
}
//biztos oszlopok feltöltés
for (int i = 0; i < 5; i++) {
int[] columnValue = clues[0][i];
if (baseSolutions(columnValue) != null){
int[] actSolution = baseSolutions(columnValue);
for (int j = 0; j < 5; j++) {
if (result[j][i] == -1){
result[j][i] = actSolution[j];
}
}
}
}
//végső kitötés
while(solvedAmount<allAmount){
//sorok
for (int i = 0; i < 5; i++) {
int[] rowValue = clues[1][i];
int[] actSolution = furtherSolutions(rowValue,result[i]);
if (actSolution != null) {
for (int j = 0; j < 5; j++) {
if (result[i][j] == -1 && actSolution[j] != -1) result[i][j] = actSolution[j];
}
}
}
//oszlopok
for (int i = 0; i < 5; i++) {
int[] columnValue= clues[0][i];
int[] actColumn = new int[5];
for (int j = 0; j < 5; j++) {
actColumn[j] = result[j][i];
}
int[] actSolution = furtherSolutions(columnValue, actColumn);
if (actSolution != null) {
for (int j = 0; j < 5; j++) {
if (result[j][i] == -1 && actSolution[j] != -1) result[j][i] = actSolution[j];
}
}
}
solvedAmount = Arrays.stream(result).flatMapToInt(Arrays::stream).sum();
}
return result;
}
private static int[] furtherSolutions(int[] in, int[] sample){
if(Arrays.equals(in, new int[]{1})){
if(fullFill(in,sample) != null){
return fullFill(in,sample);
}
} else if(Arrays.equals(in, new int[]{1, 1})){
if(fullFill(in,sample) != null){
return fullFill(in,sample);
}
else if (sample[0] == 1) return new int[]{1, 0, -1, -1, -1};
else if (sample[1] == 1) return new int[]{0, 1, 0, -1, -1};
else if (sample[2] == 1) return new int[]{-1, 0, 1, 0, -1};
else if (sample[3] == 1) return new int[]{-1, -1, 0, 1, 0};
else if (sample[4] == 1) return new int[]{-1, -1, -1, 0, 1};
} else if(Arrays.equals(in, new int[]{1, 2})){
if(fullFill(in,sample) != null){
return fullFill(in,sample);
}
else if (sample[4] == 1 || sample[2] == 0) return new int[]{-1, -1, 0, 1, 1};
else if (sample[0] == 1 || sample[1] == 0) return new int[]{1, 0, -1, -1, -1};
else if (sample[4] == 0 || sample[2] == 1) return new int[]{1, 0, 1, 1, 0};
else if (sample[0] == 0 || sample[1] == 1) return new int[]{0, 1, 0, 1, 1};
} else if(Arrays.equals(in, new int[]{2})){
if(fullFill(in,sample) != null){
return fullFill(in,sample);
}
else if (sample[0] == 1) return new int[]{1, 1, 0, 0, 0};
else if (sample[4] == 1) return new int[]{0, 0, 0, 1, 1};
else if (sample[1] == 1 || sample[3] == 0) return new int[]{-1, 1, -1, 0, 0};
else if (sample[2] == 1) return new int[]{0, -1, 1, -1, 0};
else if (sample[3] == 1 || sample[1] == 0) return new int[]{0, 0, -1, 1, -1};
} else if(Arrays.equals(in, new int[]{2, 1})){
if(fullFill(in,sample) != null){
return fullFill(in,sample);
}
else if (sample[0] == 1 || sample[2] == 0) return new int[]{1, 1, 0, -1, -1};
else if (sample[4] == 1 || sample[3] == 0) return new int[]{-1, -1, -1, 0, 1};
else if (sample[0] == 0 || sample[2] == 1) return new int[]{0, 1, 1, 0, 1};
else if (sample[4] == 0 || sample[3] == 1) return new int[]{1, 1, 0, 1, 0};
} else if(Arrays.equals(in, new int[]{3})){
if(fullFill(in,sample) != null){
return fullFill(in,sample);
}
else if (sample[1] == 0 || sample[4] == 1) return new int[]{0, 0, 1, 1, 1};
else if (sample[0] == 1 || sample[3] == 0) return new int[]{1, 1, 1, 0, 0};
else if (sample[1] == 1 || sample[4] == 0) return new int[]{-1, 1, 1, -1, 0};
else if (sample[3] == 1 || sample[0] == 0) return new int[]{0, -1, 1, 1, -1};
} else if(Arrays.equals(in, new int[]{4})){
if (sample[0] == 1 || sample[4] == 0) return new int[]{1, 1, 1, 1, 0};
else if (sample[0] == 0 || sample[4] == 1) return new int[]{0, 1, 1, 1, 1};
}
return null;
}
private static int[] fullFill(int[] clues, int[] sample){
if(Arrays.stream(clues).sum() == Arrays.stream(sample).filter(a -> a==1).count()){
return Arrays.stream(sample)
.map(a -> {
if(a == -1) return 0;
return -1;
})
.toArray();
} else if (Arrays.stream(clues).sum() == 5 - Arrays.stream(sample).filter(a -> a==0).count()){
return Arrays.stream(sample)
.map(a -> {
if(a == -1) return 1;
return -1;
})
.toArray();
}
return null;
}
}
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.stream.Collectors;
public class Nonogram {
private static HashMap<String, int[][]> operations = new HashMap<>() {{
put("5", new int[][]{{1, 1, 1, 1, 1}});
put("3,1", new int[][]{{1, 1, 1, -1, 1}});
put("1,3", new int[][]{{1, -1, 1, 1, 1}});
put("2,2", new int[][]{{1, 1, -1, 1, 1}});
put("1,1,1", new int[][]{{1, -1, 1, -1, 1}});
put("4", new int[][]{{1, 1, 1, 1, -1}, {-1, 1, 1, 1, 1}});
put("3", new int[][]{{1, 1, 1, -1, -1}, {-1, 1, 1, 1, -1}, {-1, -1, 1, 1, 1}});
put("1,2", new int[][]{{1, -1, 1, 1, -1}, {1, -1, -1, 1, 1}, {-1, 1, -1, 1, 1}});
put("2,1", new int[][]{{1, 1, -1, 1, -1}, {1, 1, -1, -1, 1}, {-1, 1, 1, -1, 1}});
put("2", new int[][]{{1, 1, -1, -1, -1}, {-1, 1, 1, -1, -1}, {-1, -1, 1, 1, -1}, {-1, -1, -1, 1, 1}});
put("1", new int[][]{{1, -1, -1, -1, -1}, {-1, 1, -1, -1, -1}, {-1, -1, 1, -1, -1}, {-1, -1, -1, 1, -1}, {-1, -1, -1, -1, 1}});
put("1,1", new int[][]{{1, -1, 1, -1, -1}, {1, -1, -1, 1, -1}, {1, -1, -1, -1, 1}, {-1, 1, -1, 1, -1}, {-1, 1, -1, -1, 1}, {-1, -1, 1, -1, 1}});
}};
private static String asClue(int[] row) {
return Arrays.stream(row).mapToObj(v -> Integer.toString(v)).collect(Collectors.joining(","));
}
private static boolean canMerge(int[] existing, int[] testing) {
for (int i = 0; i < existing.length; ++i) {
if (existing[i] == -1 && testing[i] > 0 || testing[i] == -1 && existing[i] > 0) return false;
}
return true;
}
private static List<int[]> findMatches(String clue, int[] currentRow) {
var poss = operations.get(clue);
if (poss == null) throw new Error("Clue not found " + clue);
return Arrays.stream(poss).filter(v -> canMerge(currentRow, v)).collect(Collectors.toList());
}
private static boolean isSolved(int[][] board, List<String> vclues) {
if (Arrays.stream(board).anyMatch(l -> Arrays.stream(l).anyMatch(v -> v == 0))) return false;
for (int i = 0; i < board.length; ++i) {
final int j = i;
var lst = Arrays.stream(board).map(l -> Integer.toString(l[j])).collect(Collectors.joining(","));
var oneMatch = Arrays.stream(operations.get(vclues.get(j))).anyMatch(c -> asClue(c).equals(lst));
if (!oneMatch) return false;
}
return true;
}
private static int[][] attemptConstruct(int[][] map, List<String> hClues, List<String> vClues, final int index) {
if (isSolved(map, vClues)) return map;
if (index >= hClues.size()) return null;
var currentClue = hClues.get(index);
final var before = map[index].clone();
var matches = findMatches(currentClue, before);
for (var m : matches) {
map[index] = m.clone();
var subMap = attemptConstruct(map, hClues, vClues, index + 1);
if (subMap != null) {
return subMap;
}
}
map[index] = before;
return null;
}
private static int[][] normalize(int[][] map) {
for (var l : map) {
for (int i = 0; i < l.length; ++i) {
l[i] = Math.max(l[i], 0);
}
}
return map;
}
public static int[][] solve(int[][][] clues) {
return normalize(attemptConstruct(new int[5][5],
Arrays.stream(clues[1]).map(i -> asClue(i)).collect(Collectors.toList()),
Arrays.stream(clues[0]).map(i -> asClue(i)).collect(Collectors.toList()),
0));
}
}import java.util.*;
public class Nonogram {
public static final boolean OUTPUT = false;
private static final int[][] clueLookup;
static {
clueLookup = new int[(1 << 5)][];
ArrayList<Integer> clues = new ArrayList<>();
for(int config = 0; config < (1 << 5); config++) {
int length = 0;
for(int i = 0; i < 5; i++) {
int val = (config >> i) & 1;
if(val == 1) {
length++;
}
else {
if(length > 0) {
clues.add(length);
length = 0;
}
}
}
if(length > 0) {
clues.add(length);
length = 0;
}
int[] clue = new int[clues.size()];
for(int i = 0; i < clues.size(); i++) {
clue[i] = clues.get(i);
}
clueLookup[config] = clue;
StringBuilder sb = new StringBuilder();
sb.append("config " + String.format("0x%x", config) + ": ");
for(int i : clueLookup[config]) {
sb.append(i + ", ");
}
sb.append('\n');
System.out.println(sb);
clues.clear();
}
// System.exit(0);
}
private static final HashMap<String, Integer> solutions = new HashMap<>();
public static void applyConfig(int config, int[][] grid) {
for(int i = 0; i < 25; i++) {
int val = (config >> i) & 0x1;
int col = i%5;
int row = i/5;
grid[row][col] = val;
}
}
/// 5x5
public static int[][] solve(int[][][] clues) {
int[][] columnClues = clues[0];
int[][] rowClues = clues[1];
int[][] grid = new int[5][5];
for(int config = 0; config < (1 << 25); config++) {
if(OUTPUT) {
System.out.println(String.format("0x%x", config));
applyConfig(config, grid);
printGrid(grid);
}
if(validate(config, columnClues, rowClues)) {
System.out.println(String.format("Solved: 0x%x", config));
applyConfig(config, grid);
printGrid(grid);
return grid;
}
}
return null;
}
public static boolean validate(int grid, int[][] columnClues, int[][] rowClues) {
for(int col = 0; col < 5; col++) {
int temp = grid >> col;
int config = (temp & 0x1) | ((temp >> 4) & 0x2) | ((temp >> 8) & 0x4) | ((temp >> 12) & 0x8) | ((temp >> 16) & 0x10);
int[] clue = clueLookup[config];
if(!Arrays.equals(clue, columnClues[col])) {
return false;
}
}
for(int row = 0; row < 5; row++) {
int temp = grid >> (row*5);
int config = temp & 0x1F;
int[] clue = clueLookup[config];
if(!Arrays.equals(clue, rowClues[row])) {
return false;
}
}
return true;
}
public static void printGrid(int[][] grid) {
StringBuilder sb = new StringBuilder();
sb.append("__________\n");
for(int row = 0; row < 5; row++) {
sb.append('|');
for(int col = 0; col < 5; col++) {
sb.append(grid[row][col] == 0 ? "-|" : "#|");
}
sb.append('\n');
}
System.out.println(sb.toString());
}
}import java.util.*;
public class Nonogram {
public static int[][] solve(int[][][] asd) {
int[][] result = new int[5][5];
HashMap<List<Integer>, List<List<Integer>>> posibilidades = new HashMap<>();
List<Integer> pre1 = List.of(1);
List<Integer> pre11 = List.of(1, 1);
List<Integer> pre111 = List.of(1, 1, 1);
List<Integer> pre12 = List.of(1, 2);
List<Integer> pre21 = List.of(2, 1);
List<Integer> pre2 = List.of(2);
List<Integer> pre22 = List.of(2, 2);
List<Integer> pre3 = List.of(3);
List<Integer> pre13 = List.of(1, 3);
List<Integer> pre31 = List.of(3, 1);
List<Integer> pre4 = List.of(4);
List<Integer> pre5 = List.of(5);
List<List<Integer>> sol1 = new ArrayList<>();
sol1.add(Arrays.asList(0, 0, 0, 0, 1));
sol1.add(Arrays.asList(0, 0, 0, 1, 0));
sol1.add(Arrays.asList(0, 0, 1, 0, 0));
sol1.add(Arrays.asList(0, 1, 0, 0, 0));
sol1.add(Arrays.asList(1, 0, 0, 0, 0));
List<List<Integer>> sol11 = new ArrayList<>();
sol11.add(Arrays.asList(1, 0, 1, 0, 0));
sol11.add(Arrays.asList(1, 0, 0, 1, 0));
sol11.add(Arrays.asList(1, 0, 0, 0, 1));
sol11.add(Arrays.asList(0, 1, 0, 1, 0));
sol11.add(Arrays.asList(0, 1, 0, 0, 1));
sol11.add(Arrays.asList(0, 0, 1, 0, 1));
List<List<Integer>> sol111 = new ArrayList<>();
sol111.add(Arrays.asList(1, 0, 1, 0, 1));
List<List<Integer>> sol12 = new ArrayList<>();
sol12.add(Arrays.asList(1, 0, 1, 1, 0));
sol12.add(Arrays.asList(1, 0, 0, 1, 1));
sol12.add(Arrays.asList(0, 1, 0, 1, 1));
List<List<Integer>> sol21 = new ArrayList<>();
sol21.add(Arrays.asList(1, 1, 0, 0, 1));
sol21.add(Arrays.asList(1, 1, 0, 1, 0));
sol21.add(Arrays.asList(0, 1, 1, 0, 1));
List<List<Integer>> sol2 = new ArrayList<>();
sol2.add(Arrays.asList(1, 1, 0, 0, 0));
sol2.add(Arrays.asList(0, 1, 1, 0, 0));
sol2.add(Arrays.asList(0, 0, 1, 1, 0));
sol2.add(Arrays.asList(0, 0, 0, 1, 1));
List<List<Integer>> sol22 = new ArrayList<>();
sol22.add(Arrays.asList(1, 1, 0, 1, 1));
List<List<Integer>> sol3 = new ArrayList<>();
sol3.add(Arrays.asList(1, 1, 1, 0, 0));
sol3.add(Arrays.asList(0, 1, 1, 1, 0));
sol3.add(Arrays.asList(0, 0, 1, 1, 1));
List<List<Integer>> sol13 = new ArrayList<>();
sol13.add(Arrays.asList(1, 0, 1, 1, 1));
List<List<Integer>> sol31 = new ArrayList<>();
sol31.add(Arrays.asList(1, 1, 1, 0, 1));
List<List<Integer>> sol4 = new ArrayList<>();
sol4.add(Arrays.asList(1, 1, 1, 1, 0));
sol4.add(Arrays.asList(0, 1, 1, 1, 1));
List<List<Integer>> sol5 = new ArrayList<>();
sol5.add(Arrays.asList(1, 1, 1, 1, 1));
posibilidades.put(pre1, sol1);
posibilidades.put(pre11, sol11);
posibilidades.put(pre111, sol111);
posibilidades.put(pre12, sol12);
posibilidades.put(pre21, sol21);
posibilidades.put(pre2, sol2);
posibilidades.put(pre22, sol22);
posibilidades.put(pre13, sol13);
posibilidades.put(pre31, sol31);
posibilidades.put(pre3, sol3);
posibilidades.put(pre4, sol4);
posibilidades.put(pre5, sol5);
List<List<Integer>> preguntasHorizontales = new ArrayList<>();
for(int i = 0; i<5; i++) {
List<Integer> agregar = new ArrayList<>();
for(int j = 0; j<asd[1][i].length; j++) {
agregar.add(asd[1][i][j]);
}
preguntasHorizontales.add(agregar);
}
List<List<Integer>> preguntasVerticales = new ArrayList<>();
for(int i = 0; i<5; i++) {
List<Integer> agregar = new ArrayList<>();
for(int j = 0; j<asd[0][i].length; j++) {
agregar.add(asd[0][i][j]);
}
preguntasVerticales.add(agregar);
}
List<List<Integer>> resultado = new ArrayList<>(5);
resultado.add(null);
resultado.add(null);
resultado.add(null);
resultado.add(null);
resultado.add(null);
List<List<Integer>> trueResultado = new ArrayList<>();
for(int i = 0; i<posibilidades.get(preguntasHorizontales.get(0)).size();i++){
resultado.set(0, posibilidades.get(preguntasHorizontales.get(0)).get(i));
for(int o = 0; o<posibilidades.get(preguntasHorizontales.get(1)).size();o++){
resultado.set(1, posibilidades.get(preguntasHorizontales.get(1)).get(o));
for(int w = 0; w<posibilidades.get(preguntasHorizontales.get(2)).size();w++) {
resultado.set(2, posibilidades.get(preguntasHorizontales.get(2)).get(w));
for (int j = 0; j <posibilidades.get(preguntasHorizontales.get(3)).size(); j++) {
resultado.set(3, posibilidades.get(preguntasHorizontales.get(3)).get(j));
for (int k = 0; k < posibilidades.get(preguntasHorizontales.get(4)).size(); k++) {
resultado.set(4, posibilidades.get(preguntasHorizontales.get(4)).get(k));
if (isValid(resultado, preguntasVerticales, posibilidades)){
trueResultado = List.copyOf(resultado);
}
}
}
}
}
}
for(int i = 0; i<5; i++){
for(int j = 0; j<5; j++){
result[i][j] = (trueResultado.get(i)).get(j);
}
}
return result;
}
public static boolean isValid(List<List<Integer>> resultado, List<List<Integer>> preguntasVerticales, HashMap<List<Integer>, List<List<Integer>>> posibilidades){
List<Integer> comprobador = new ArrayList<>();
for (int i=0; i<5; i++){
comprobador.add(resultado.get(i).get(0));
}
if(posibilidades.get(preguntasVerticales.get(0)).contains(comprobador)){
comprobador.clear();
}else return false;
for (int i=0; i<5; i++){
comprobador.add(resultado.get(i).get(1));
}
if(posibilidades.get(preguntasVerticales.get(1)).contains(comprobador)){
comprobador.clear();
}else return false;
for (int i=0; i<5; i++){
comprobador.add(resultado.get(i).get(2));
}
if(posibilidades.get(preguntasVerticales.get(2)).contains(comprobador)){
comprobador.clear();
}else return false;
for (int i=0; i<5; i++){
comprobador.add(resultado.get(i).get(3));
}
if(posibilidades.get(preguntasVerticales.get(3)).contains(comprobador)){
comprobador.clear();
}else return false;
for (int i=0; i<5; i++){
comprobador.add(resultado.get(i).get(4));
}
if(posibilidades.get(preguntasVerticales.get(4)).contains(comprobador)){
comprobador.clear();
}else return false;
return true;
}
}
import java.util.Arrays;
public class Nonogram {
private static final int SIZE = 5;
private static final int CLUE_INDEX_BITS;
private static final int[] FIBO = new int[SIZE + 1];
private static final int POSSIBLE_LINES = 1 << SIZE;
private static final int POSSIBLE_TABLES = 1 << (SIZE * SIZE);
private static final int[] ROW_TO_COLUMN = new int[POSSIBLE_LINES];
private static final int LINE_MASK = POSSIBLE_LINES - 1;
private static final int[] TABLE_TO_SIDE_CLUES = new int[POSSIBLE_TABLES];
static {
FIBO[0] = 1;
FIBO[1] = 2;
for (int n = 2; n <= SIZE; n++)
FIBO[n] = FIBO[n - 2] + FIBO[n - 1];
CLUE_INDEX_BITS = Integer.SIZE - Integer.numberOfLeadingZeros(FIBO[SIZE] - 1);
int[] lineToClueIndex = new int[POSSIBLE_LINES];
int[] clue = new int[(SIZE + 1) / 2];
for (int line = 0; line < POSSIBLE_LINES; line++) {
int x = line;
int k = -1;
boolean space = true;
for (int i = 0; i < SIZE; i++) {
if ((x & 1) == 0)
space = true;
else if (space) {
clue[++k] = 1;
space = false;
} else
clue[k]++;
x >>= 1;
}
lineToClueIndex[line] = clueToIndex(Arrays.copyOf(clue, k + 1));
x = line;
int y = 0;
int t = 1;
for (int i = 0; i < SIZE; i++) {
if ((x & 1) != 0)
y += t;
x >>= 1;
t <<= SIZE;
}
ROW_TO_COLUMN[line] = y;
}
for (int table = 0; table < POSSIBLE_TABLES; table++) {
int verticalClues = 0;
int x = table;
for (int i = 0; i < SIZE; i++) {
verticalClues <<= CLUE_INDEX_BITS;
verticalClues += lineToClueIndex[x & LINE_MASK];
x >>= SIZE;
}
TABLE_TO_SIDE_CLUES[table] = verticalClues;
}
}
private static int clueToIndex(int[] clue, int size, int begin, int subtract) {
if (begin == clue.length) // includes the case size == 0
return 0;
if (size == 1)
return 1;
if (clue[begin] - subtract == 1)
return 1 + clueToIndex(clue, size - 2, begin + 1, 0);
else
return FIBO[size - 2] + clueToIndex(clue, size - 1, begin, subtract + 1);
}
private static int clueToIndex(int[] clue) {
int s = 0;
int len = clue.length;
for (int i = 0; i < len; i++) {
int x = clue[i];
s += x + 1;
if (x <= 0 || s > SIZE + 1)
throw new IllegalArgumentException("Wrong clues: " + Arrays.toString(clue));
}
return clueToIndex(clue, SIZE, 0, 0);
}
private static int sideCluesToIndex(int[][] clues) {
int index = 0;
for (int[] clue : clues) {
index <<= CLUE_INDEX_BITS;
index += clueToIndex(clue);
}
return index;
}
private static int transpose(int table) {
int result = 0;
int shift = 0;
for (int i = 0; i < SIZE; i++) {
result += ROW_TO_COLUMN[table & LINE_MASK] << shift++;
table >>= SIZE;
}
return result;
}
private static int[][] tableToArray(int table) {
int[][] result = new int[SIZE][SIZE];
for (int[] row : result)
for (int i = 0; i < SIZE; i++) {
if ((table & 1) != 0)
row[i] = 1;
table >>= 1;
}
return result;
}
public static int[][] solve(int[][][] clues) {
int horizontalClues = sideCluesToIndex(clues[0]);
int verticalClues = sideCluesToIndex(clues[1]);
for (int table = 0; table < POSSIBLE_TABLES; table++)
if (TABLE_TO_SIDE_CLUES[table] == verticalClues
&& TABLE_TO_SIDE_CLUES[transpose(table)] == horizontalClues)
return tableToArray(table);
throw new RuntimeException("No solution for " + Arrays.deepToString(clues));
}
}import java.util.Arrays;
import java.util.logging.Level;
import java.util.logging.Logger;
public class Nonogram {
public static int[][] solve(int[][][] clues) {
Game game = new Game(5, 5, clues);
return game.solve();
}
}
//Возможные значения полей игровой доски (неизвестное, белое и чёрное)
enum Palitra {White, Black, Unknow};
//Расположение обрабатываемой строки
enum Direction {Horizontal, Vertical};
//Создание игры и поиск решения
class Game {
private final Board board;
private final int[][][] clues;
public Game(int row, int col, int[][][] clues) {
board = new Board(row, col);
this.clues = clues;
}//contructor
//метод поиска решений
public int[][] solve() {
LineSolver ls;
do {
for (int r=0; r<board.getRow(); r++) {
if (board.isFullLine(r, Direction.Horizontal)) continue;
ls = new LineSolver(board.getLine(r, Direction.Horizontal), clues[1][r]);
board.setLine(r, ls.solve_Line(), Direction.Horizontal);
}
for (int c=0; c<board.getCol(); c++) {
if (board.isFullLine(c, Direction.Vertical)) continue;
ls = new LineSolver(board.getLine(c, Direction.Vertical), clues[0]);
board.setLine(c, ls.solve_Line(), Direction.Vertical);
}
} while (!board.isResolved());
return formResult();
}//solve
//формирует ответ в требуемой форме
private int[][] formResult() {
int[][] res = new int[board.getRow()][board.getCol()];
for (int i=0; i<board.getRow(); i++)
for (int j=0; j<board.getCol(); j++)
res[i][j]= board.getCell(i, j).equals(Palitra.Black)? 1: 0;
return res;
}//formResult
}//Game class
//Поиск решения для одной линии
class LineSolver {
Palitra[] line;//анализируемая линия
int nLine;//длина анализируемой линии
int[] hints;//подсказки для анализируемой линии
int[][][] calc;//массив используется для расчётов
int[] black;//храним черные
int[] white;//храним белые
boolean[] canBlack;//вероятные чёрные
boolean[] canWhite;//вероятные белые
int[] diffBlack;
LineSolver(Palitra[] line, int[] hints) {
this.line = line;
nLine = line.length;
this.hints = hints;
calc = new int[nLine+5][this.hints.length+5][2];
for (int i3=0; i3<calc.length; i3++)
for (int i2=0; i2<calc[i3].length; i2++)
for (int i1=0; i1<2; i1++) calc[i3][i2][i1]=-1;
black = new int[nLine];
white = new int[nLine];
canBlack = new boolean[nLine];
canWhite = new boolean[nLine];
for (int i=0; i<nLine; i++)
if (line[i].equals(Palitra.Black)) {black[i]++; canBlack[i]=true;}
else if (line[i].equals(Palitra.White)) {white[i]++; canWhite[i]=true;}
diffBlack = new int[nLine+1];
}//LineSolver constructor
//Подбор решения одной линии
//За основу был взят алгоритм с
//https://github.com/Izaron/ACM-ICPC/blob/master/International%20Olympiad%20in%20Informatics/IOI%202016/paint.cpp
public Palitra[] solve_Line() {
for (int i=1; i<nLine; i++) white[i] += white[i-1];
int find = searchPostingHints(0, 0, 0);
if (find==0) try {
throw new Exception("Error in clues array!");
} catch (Exception ex) {
Logger.getLogger(LineSolver.class.getName()).log(Level.SEVERE, null, ex);
}
for (int i=0; i<nLine; i++) {
if (i > 0) diffBlack[i] += diffBlack[i - 1];
if (diffBlack[i] > 0) canBlack[i] = true;
}
for (int i=0; i<nLine; i++)
if (canBlack[i] && canWhite[i]) ;
else if (canBlack[i]) line[i] = Palitra.Black;
else line[i] = Palitra.White;
return line;
}//solve_Line
//Поиск всех значений белых и чёрных через рассмотрения возможных размещений
int searchPostingHints(int cell, int kHints, int last) {
if (cell > nLine) return 0;
if (cell == nLine && kHints != hints.length) return 0;
if (cell == nLine) return 1;
if (calc[cell][kHints][last] != -1) return calc[cell][kHints][last];
int rez = 0;
if (black[cell]==0 && searchPostingHints(cell+1, kHints, 0)==1) {
rez=1;
canWhite[cell] = true;
}
if (kHints<hints.length && last==0 &&
cell+hints[kHints]<=nLine &&
!isWhites(cell, cell+ hints[kHints]-1) &&
searchPostingHints(cell + hints[kHints], kHints+1, 1) == 1) {
rez = 1;
diffBlack[cell]++;
diffBlack[cell + hints[kHints]]--;
}
calc[cell][kHints][last] = rez;
return rez;
}
boolean isWhites(int a, int b) {
int value = white[b];
if (a>0) value -= white[a - 1];
return value>0;
}
}//LineSolver class
//Описание игровой доски
class Board {
private final Palitra[][] board;//игровая доска
private final int lenR;//размер игровой доски: количество строк
private final int lenC;//размер игровой доски: количество столбцов
private final boolean[] fullR;//массив-маркер отгадана(заполнена значениями) строка
private final boolean[] fullC;//массив-маркер отгадан(заполнен значениями) столбец
public Board(int row, int col) {
board = new Palitra[row][col];
for (Palitra[] line: board) Arrays.fill(line, Palitra.Unknow);
lenR=row;
lenC=col;
fullR = new boolean[row];
fullC = new boolean[col];
}//Board constructor
//Количество строк
public int getRow() {
return lenR;
}//getRow
//Количество столбцов
public int getCol() {
return lenC;
}//getCol
//метод для тестирования, удалить после создания приложения!!!!!!!!!!!!!!!
public void print() {
System.out.println("Игровая доска:");
for (Palitra[] line: board) {
for (Palitra i: line) System.out.print(i.ordinal()+" ");
System.out.println();
}
System.out.println(" ---------------");
}//print
//проверяет решена ли нонограмма
public boolean isResolved() {
for (boolean b: fullR) if (!b) return false;
for (boolean b: fullC) if (!b) return false;
return true;
}//isResolved
//проверяет линию на заполненность значениями, отгаданность
public boolean isFullLine(int kLine, Direction direct) {
if (direct.equals(Direction.Horizontal)) {
if (fullR[kLine]) return true;
for (Palitra cell: board[kLine])
if (cell.equals(Palitra.Unknow)) return false;
fullR[kLine] = true;
return true;
} else {
if (fullC[kLine]) return true;
for (Palitra[] row: board)
if (row[kLine].equals(Palitra.Unknow)) return false;
fullC[kLine]=true;
return true;
}
}//isFullline
//возвращает одну линию
public Palitra[] getLine(int kLine, Direction direct) {
if (direct.equals(Direction.Horizontal)) return board[kLine];
else {
Palitra[] line = new Palitra[lenR];
for (int i=0; i<lenR; i++) line[i]=board[i][kLine];
return line;
}
}//getLine
//заполняет значениями одну линию
public void setLine(int kLine, Palitra[] line, Direction direct) {
if (direct.equals(Direction.Horizontal)) board[kLine]=line;
else for (int i=0; i<lenR; i++) board[i][kLine]=line[i];
}//setLine
//заполняет значением одну клетку
public void fillCell(int r, int c, Palitra p) {
/*if (p.equals(Palitra.Unknow)) return;*/
board[r] = p;
}//fillCell
//Получаем значение одной клетки
public Palitra getCell(int r, int c) {
return board[r];
}//getCell
}//Board classimport java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Nonogram {
static boolean testHelper(int[][] clues, boolean[][] board, boolean vertical) {
for (int i = 0; i < 5; i++) {
boolean matching = vertical ? board[i][0] : board[0][i];
int matches = 0;
int matchLength = 0;
for (int j = 0; j < 5; j++) {
if (matching) {
if (!(vertical ? board[i][j] : board[j][i]) || j == 4) {
if (vertical ? board[i][j] : board[j][i]) {
matchLength++;
}
if (clues[i].length >= matches + 1) {
if (clues[i][matches++] != matchLength) {
return false;
}
} else {
return false;
}
matchLength = 0;
matching = j < 4 && (vertical ? board[i][j + 1] : board[j + 1][i]);
} else {
matchLength++;
}
} else {
if (j < 4 && (vertical ? board[i][j + 1] : board[j + 1][i])) {
matching = true;
}
}
}
if (matches != clues[i].length) {
return false;
}
}
return true;
}
static boolean test(int[][] horizontalClues, int[][] verticalClues, boolean[][] board) {
return testHelper(horizontalClues, board, false) && testHelper(verticalClues, board, true);
}
static List<boolean[]> allCombinations(int n, int[] clues) {
if (clues.length == 0) {
return new ArrayList<>();
}
// Handling the only case where 3 clues input will be valid.
if (clues.length == 3) {
if (clues[0] == 1 && clues[1] == 1 && clues[2] == 1) {
return List.of(new boolean[] {true, false, true, false, true});
}
}
List<boolean[]> result = new ArrayList<>();
int clue1 = clues[0];
int clue2 = clues.length == 2 ? clues[1] : 0;
int tempN = n;
while (clue1 + clue2 <= tempN) {
int clue1Pos = n - tempN;
int clue2Pos = clue1Pos + clue1 + 1;
boolean[] output = new boolean[n];
for (int i = clue1Pos; i < clue1Pos + clue1; i++) {
output[i] = true;
}
if (clue2 > 0) {
while (clue2Pos + clue2 <= n) {
boolean[] out = Arrays.copyOf(output, output.length);
for (int i = clue2Pos; i < clue2Pos + clue2; i++) {
out[i] = true;
}
result.add(out);
clue2Pos++;
}
} else {
result.add(output);
}
tempN--;
}
return result;
}
public static int[][] solve(int[][][] clues) {
int[][] horizontalClues = clues[0];
int[][] verticalClues = clues[1];
int[][] board = {
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
};
return solveHelper(board, horizontalClues, verticalClues, 0);
}
private static int[][] deepClone2DArray(int[][] board) {
int[][] clone = new int[board.length][board.length > 0 ? board[0].length : 0];
for (int i = 0; i < board.length; i++) {
System.arraycopy(board[i], 0, clone[i], 0, board[0].length);
}
return clone;
}
public static int[][] solveHelper(int[][] board, int[][] horzClues, int[][] vertClues, int pos) {
if (pos >= 5) {
return null;
}
List<boolean[]> allCombs = allCombinations(5, vertClues[pos]);
for (boolean[] comb : allCombs) {
// Before trying combination, save board state for backtracking.
int[][] saveBoard = deepClone2DArray(board);
applyCombination(saveBoard, comb, pos);
if (pos == 4) {
if (test(horzClues, vertClues, boardToBool(saveBoard))) {
return saveBoard;
} else {
continue;
}
}
int[][] result = solveHelper(saveBoard, horzClues, vertClues, pos + 1);
if (result != null) {
return result;
}
}
// When some position has no combinations, we have no solution.
return null;
}
private static void applyCombination(int[][] board, boolean[] combination, int pos) {
for (int i = 0; i < 5; i++) {
board[pos][i] = combination[i] ? 1 : 0;
}
}
private static boolean[][] boardToBool(int[][] board) {
// 5x5 Board
boolean[][] result = new boolean[5][5];
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
result[i][j] = board[i][j] == 1;
}
}
return result;
}
}import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Nonogram {
static boolean testHelper(int[][] clues, boolean[][] board, boolean vertical) {
for (int i = 0; i < 5; i++) {
boolean matching = vertical ? board[i][0] : board[0][i];
int matches = 0;
int matchLength = 0;
for (int j = 0; j < 5; j++) {
if (matching) {
if (!(vertical ? board[i][j] : board[j][i]) || j == 4) {
if (vertical ? board[i][j] : board[j][i]) {
matchLength++;
}
if (clues[i].length >= matches + 1) {
if (clues[i][matches++] != matchLength) {
return false;
}
} else {
return false;
}
matchLength = 0;
matching = j < 4 && (vertical ? board[i][j + 1] : board[j + 1][i]);
} else {
matchLength++;
}
} else {
if (j < 4 && (vertical ? board[i][j + 1] : board[j + 1][i])) {
matching = true;
}
}
}
if (matches != clues[i].length) {
return false;
}
}
return true;
}
static boolean test(int[][] horizontalClues, int[][] verticalClues, boolean[][] board) {
return testHelper(horizontalClues, board, false) && testHelper(verticalClues, board, true);
}
static List<boolean[]> allCombinations(int n, int[] clues) {
if (clues.length == 0) {
return new ArrayList<>();
}
// Handling the only case where 3 clues input will be valid.
if (clues.length == 3) {
if (clues[0] == 1 && clues[1] == 1 && clues[2] == 1) {
return List.of(new boolean[] {true, false, true, false, true});
}
}
List<boolean[]> result = new ArrayList<>();
int clue1 = clues[0];
int clue2 = clues.length == 2 ? clues[1] : 0;
int tempN = n;
while (clue1 + clue2 <= tempN) {
int clue1Pos = n - tempN;
int clue2Pos = clue1Pos + clue1 + 1;
boolean[] output = new boolean[n];
for (int i = clue1Pos; i < clue1Pos + clue1; i++) {
output[i] = true;
}
if (clue2 > 0) {
while (clue2Pos + clue2 <= n) {
boolean[] out = Arrays.copyOf(output, output.length);
for (int i = clue2Pos; i < clue2Pos + clue2; i++) {
out[i] = true;
}
result.add(out);
clue2Pos++;
}
} else {
result.add(output);
}
tempN--;
}
return result;
}
public static int[][] solve(int[][][] clues) {
int[][] horizontalClues = clues[0];
int[][] verticalClues = clues[1];
int[][] board = {
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
};
return solveHelper(board, horizontalClues, verticalClues, 0);
}
private static int[][] deepClone2DArray(int[][] board) {
int[][] clone = new int[board.length][board.length > 0 ? board[0].length : 0];
for (int i = 0; i < board.length; i++) {
System.arraycopy(board[i], 0, clone[i], 0, board[0].length);
}
return clone;
}
public static int[][] solveHelper(int[][] board, int[][] horzClues, int[][] vertClues, int pos) {
if (pos >= 5) {
return null;
}
List<boolean[]> allCombs = allCombinations(5, vertClues[pos]);
for (boolean[] comb : allCombs) {
// Before trying combination, save board state for backtracking.
int[][] saveBoard = deepClone2DArray(board);
applyCombination(saveBoard, comb, pos);
if (pos == 4) {
if (test(horzClues, vertClues, boardToBool(saveBoard))) {
return saveBoard;
} else {
continue;
}
}
int[][] result = solveHelper(saveBoard, horzClues, vertClues, pos + 1);
if (result != null) {
return result;
}
}
// When some position has no combinations, we have no solution.
return null;
}
private static void applyCombination(int[][] board, boolean[] combination, int pos) {
for (int i = 0; i < 5; i++) {
board[pos][i] = combination[i] ? 1 : 0;
}
}
private static boolean[][] boardToBool(int[][] board) {
// 5x5 Board
boolean[][] result = new boolean[5][5];
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
result[i][j] = board[i][j] == 1;
}
}
return result;
}
}
