Algorithme récursif pour trouver toutes les solutions possibles dans une rangée de nonogrammes

Question

J'essaie d'écrire un solveur de nonogrammes simple, de manière brute, mais je suis bloqué sur une tâche relativement facile. Disons que j'ai une rangée avec des indices [2,3] qui a une longueur de 10

donc les solutions sont :

$$-$$$----
$$--$$$---
$$---$$$--
$$----$$$-
$$-----$$$
-$$----$$$
--$$---$$$
---$$--$$$
----$$-$$$
-$$---$$$-
--$$-$$$--

Je veux trouver toutes les solutions possibles pour une ligne Je sais que je dois considérer chaque bloc séparément, et que chaque bloc aura un espace disponible de n-(somme de la longueur des blocs restants + nombre de blocs restants) mais je ne sais pas comment progresser à partir de là.

Answer 1

Cette question a déjà une bonne réponse, alors considérez celle-ci plutôt comme une publicité pour les prouesses de Python.

def place(blocks,total):
    if not blocks: return ["-"*total]
    if blocks[0]>total: return []

    starts = total-blocks[0] #starts = 2 means possible starting indexes are [0,1,2]
    if len(blocks)==1: #this is special case
        return [("-"*i+"$"*blocks[0]+"-"*(starts-i)) for i in range(starts+1)]

    ans = []
    for i in range(total-blocks[0]): #append current solutions
        for sol in place(blocks[1:],starts-i-1): #with all possible other solutiona
            ans.append("-"*i+"$"*blocks[0]+"-"+sol)

    return ans

Pour le tester :

for i in place([2,3,2],12):
    print(i)

Ce qui produit un résultat comme :

$$-$$$-$$---
$$-$$$--$$--
$$-$$$---$$-
$$-$$$----$$
$$--$$$-$$--
$$--$$$--$$-
$$--$$$---$$
$$---$$$-$$-
$$---$$$--$$
$$----$$$-$$
-$$-$$$-$$--
-$$-$$$--$$-
-$$-$$$---$$
-$$--$$$-$$-
-$$--$$$--$$
-$$---$$$-$$
--$$-$$$-$$-
--$$-$$$--$$
--$$--$$$-$$
---$$-$$$-$$

Answer 2

C'est ce que j'ai obtenu :

#include <iostream>
#include <vector>
#include <string>

using namespace std;

typedef std::vector<bool> tRow;

void printRow(tRow row){
    for (bool i : row){
        std::cout << ((i) ? '$' : '-');
    }
    std::cout << std::endl;
}

int requiredCells(const std::vector<int> nums){
    int sum = 0;
    for (int i : nums){
        sum += (i + 1); // The number + the at-least-one-cell gap at is right
    }
    return (sum == 0) ? 0 : sum - 1; // The right-most number don't need any gap
}

bool appendRow(tRow init, const std::vector<int> pendingNums, unsigned int rowSize, std::vector<tRow> &comb){
    if (pendingNums.size() <= 0){
        comb.push_back(init);
        return false;
    }
    int cellsRequired = requiredCells(pendingNums);
    if (cellsRequired > rowSize){
        return false;   // There are no combinations
    }
    tRow prefix;
    int gapSize = 0;
    std::vector<int> pNumsAux = pendingNums;
    pNumsAux.erase(pNumsAux.begin());
    unsigned int space = rowSize;
    while ((gapSize + cellsRequired) <= rowSize){
        space = rowSize;
        space -= gapSize;
        prefix.clear();
        prefix = init;
        for (int i = 0; i < gapSize; ++i){
            prefix.push_back(false);
        }
        for (int i = 0; i < pendingNums[0]; ++i){
            prefix.push_back(true);
            space--;
        }
        if (space > 0){
            prefix.push_back(false);
            space--;
        }
        appendRow(prefix, pNumsAux, space, comb);
        ++gapSize;
    }
    return true;
}

std::vector<tRow> getCombinations(const std::vector<int> row, unsigned int rowSize) {
    std::vector<tRow> comb;
    tRow init;
    appendRow(init, row, rowSize, comb);
    return comb;
}

int main(){
    std::vector<int> row = { 2, 3 };

    auto ret = getCombinations(row, 10);

    for (tRow r : ret){
        while (r.size() < 10)
            r.push_back(false);

        printRow(r);
    }

    return 0;

}

Et mon résultat est :

$$-$$$----

$$--$$$---

$$---$$$--

$$----$$$--

$$-----$$$

-$$-$$$----

-$$--$$$--

-$$---$$$-

-$$----$$$-

--$$-$$$--

--$$--$$$-

--$$---$$$

---$$-$$$-

---$$--$$$

----$$-$$$

Pour sûr, ce doit être absolument improbable.

Note : je ne l'ai pas testé plus que le cas déjà écrit.

J'espère que cela fonctionnera pour vous