Problem beim Rätsellöser

[Lillie]

Hallo,
ich hoffe, ich habe das richtige Unterforum erwischt, falls nicht bitte ich um Verzeihung.
ich programmiere momentan ein Programm, das mir meine Mosaik-Rätsel lösen soll, da ich das Lösungsheft dazu nicht mehr finden kann und gerne wissen will, ob meine Lösungen stimmen.
Anfangs habe ich es mit Brute-Force versucht, aber das geht nur bis 5*5 Felder gut, bei 15*15 Feldern dauert es zu lange.

Erst einmal die Erklärung, was ich eigentlich machen will: Man hat Felder einer bestimmten Größe gegeben (z.B. 5*5) und am Rand stehen Zahlen (z.b. 2 1). Nun soll man die Kästchen des Felds schwarz anmalen. Und zwar so viele pro Zeile, wie am Rand steht. Zwischen 2 schwarzen Blöcken muss mindestens 1 weißes Feld sein.
Bei einer Zeile von 5 Kästchen mit den Zahlen 2 und 1 gibt es also folgende Möglichkeiten:
s s w s w
s s w w s
w s s w s

Mein Programm soll nun alle Möglichkeiten in eine LinkedList aus boolean[] speichern. Also pro Möglichkeit ein boolean[] an die LinkedList anhängen.

Problem: Je nachdem wie viele Zahlen ich im Zahlenarray gegeben habe, brauche ich unterschiedlich viele for-Schleifen (zumindest bei meiner jetzigen Implementierung). Das ist allerdings nicht schön, weil ich damit nicht alle Fälle abdecken kann und es bei vielen Zahlen sein kann, dass ich nicht genug Fälle abgedeckt habe. Ich poste mal den Code, den ich bisher habe, allerdings macht es glaube ich keinen Sinn ihn komplett zu ergänzen, weil er ja nicht sonderlich gut ist, aber damit ihr versteht, was ich machen will:

public static LinkedList<boolean[]> gibMoeglichkeiten(int felder,int zahlen[]){
		LinkedList<boolean[]> liste = new LinkedList<boolean[]>();
		if(zahlen.length == 1 && zahlen[0] == 0){
			return liste;
		}
		// eine Zahl
		if(zahlen.length == 1){
			for(int i = 0; i< felder; i++){
				boolean[] possible = new boolean[felder];
				for(int schwarz = 0; schwarz<zahlen[0]; schwarz ++){
					if(i+schwarz>= felder){
						return liste;
					}
					possible[i+schwarz] = true;
				}
				liste.add(possible);
			}		
		}
		// zwei Zahlen
		if(zahlen.length == 2){
			int maximum = felder-zahlen[1]-1;
			for(int i = 0; i< maximum; i++){
				// zweite Zahl 
				for(int j = i+zahlen[0] +1; j< felder; j++){
					boolean[] possible = new boolean[felder];
					// Hier habe ich jetzt aufgehört, weil es nicht sinnvoll ist das noch weiter auszuprogrammieren
				}
			}
		}
	}

Hat jemand eine Idee, wie ich das klüger machen kann, also so, dass ich keine von der Anzahl der Zahlen abhängige Anzahl an for-Schleifen benötige? Ich habe auch schon überlegt, ob das ganze vielleicht irgendwie rekursiv zu lösen ist, aber ich finde keine passende Möglichkeit...
Vielen Dank schon mal fürs Durchlesen, ich hoffe ihr könnt mir helfen

Lillie

 

[Quaxli]

Hallo,
...
Erst einmal die Erklärung, was ich eigentlich machen will: Man hat Felder einer bestimmten Größe gegeben (z.B. 5*5) und am Rand stehen Zahlen (z.b. 2 1). Nun soll man die Kästchen des Felds schwarz anmalen. Und zwar so viele pro Zeile, wie am Rand steht. Zwischen 2 schwarzen Blöcken muss mindestens 1 weißes Feld sein.
Bei einer Zeile von 5 Kästchen mit den Zahlen 2 und 1 gibt es also folgende Möglichkeiten:
s s w s w
s s w w s
w s s w s
...

Vielleicht wird Dir schneller geholfen, wenn Du weniger umständlich erklärst?
Langer Rede kurzer Sinn: Du möchtest ein Nonogramm lösen lassen.

 

[Lillie]

Danke, ich wusste nicht dass sowas Nonogramm heißt, nach dem Namen hab ich auch schon ewig gesucht. Also ja, ich möchte ein Nonogramm lösen.

 

[Marco13]

Rekursion ist vielleicht gar nicht so verkehrt. Ist jetzt nur straightforward hingeschrieben, da gibts sicher elegantere und vor allem effizientere Möglichkeiten

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class Nonogram
{
	public static void main(String[] args)
	{
		int input[] = new int[]{ 2, 1, 2 };
		int size = 10;
		List<List<Boolean>> results = new ArrayList<List<Boolean>>();
		for (int spaces=0; spaces<size; spaces++)
		{
			appendSpaces(results, new ArrayList<Boolean>(), spaces, input, 0, size);
		}
		for (List<Boolean> result : results)
		{
			System.out.println(result);
		}
	}
	
	public static void appendSpaces(List<List<Boolean>> results, List<Boolean> currentList, int numSpaces, int input[], int index, int size)
	{
		currentList.addAll(Collections.nCopies(numSpaces, Boolean.FALSE));
		if (currentList.size() == size)
		{
			if (index == input.length)
			{
				results.add(currentList);
			}
			return;
		}
		else if (currentList.size() < size)
		{
			appendFields(results, new ArrayList<Boolean>(currentList), 0, input, index, size);
		}
	}
	
	private static void appendFields(List<List<Boolean>> results, List<Boolean> currentList, int numSpaces, int[] input, int index, int size)
	{
		if (index < input.length)
		{
			currentList.addAll(Collections.nCopies(input[index], Boolean.TRUE));
			index++;
			if (currentList.size() == size)
			{
				if (index == input.length)
				{
					results.add(currentList);
				}
				return;
			}
			else if (currentList.size() < size)
			{
				for (int spaces=1; spaces<=size-currentList.size(); spaces++)
				{
					appendSpaces(results, new ArrayList<Boolean>(currentList), spaces, input, index, size);
				}
			}
		}
	}

	
}