Nonogram Programm



  • Hi!

    Bin gerade leicht am verzweifeln. Nämlich müssen wir ein Nonogram programmieren und ich habe keine Ahnung noch einen Ansatz wie. Könnte mir da jemand helfen?

    Folgender Code wurde uns gegeben:
    Da ich noch neu im programmieren bin, weiss ich nicht ganz welche weiteren Informationen benötigt werden. Ich hoffe ihr habt geduld mit mir 🙂

    #include "grid.h"
    
    // Check if the filled grid matches the hints.
    bool check_solution(const grid& nonogram,
                        const std::vector<hints>& row_hints,
                        const std::vector<hints>& col_hints) {
        // TODO
        return false;
    }
    
    // Solve recursively, filling the grid row-by-row.
    bool solve_from(grid& nonogram,
                    const std::vector<hints>& row_hints,
                    const std::vector<hints>& col_hints,
                    unsigned int row, unsigned int col) {
        // TODO
        return check_solution(nonogram, row_hints, col_hints);              
    }
    
    // Solve the nonogram, given the grid and the lists of hints.
    // Run recursive solver from position (0, 0).
    bool solve(grid& nonogram,
               const std::vector<hints>& row_hints,
               const std::vector<hints>& col_hints) {
        return solve_from(nonogram, row_hints, col_hints, 0, 0);
    }
    
    int main() {
      
      grid nonogram;
      std::vector<hints> row_hints, col_hints;
    
      read_grid(nonogram, row_hints, col_hints);
      
      if (!hints_match(row_hints, col_hints)) {
          std::cout << "The numbers in hints do not match!\n";
          return -1;
      }
      
      bool solved = solve(nonogram, row_hints, col_hints);
      
      if (solved) {
          std::cout << "FINAL RESULT\n";
          print_grid(nonogram);
      } else {
        std::cout << "No solution found.\n";
      }
      
      return 0;
    }
    

  • Mod



  • @SeppJ sagte in Nonogram Programm:

    Du brauchst Hilfe?

    Da Neulinge häufig ihren Quellcode hier im Forum nicht formatieren, hier noch der Hinweis, dass das in dem "Du brauchst Hilfe?"-Post nicht mehr korrekt ist.
    Da steht:

    Für Sourcecode gibts die [code=cpp][/code]-Tags, mit gut erkennbarem Syntaxhighlighting.

    Inzwischen muss (einzeiliger) Quelltext in einfache Backticks (das `-Zeichen) eingeschlossen werden. Code, der über mehrere Zeilen geht, in dreifache `-Zeichen:
    ```
    (hier der Quellcode)
    ```

    Außerdem sollte dieser Hinweis vermutlich auf der Hilfe-Seite weiter nach oben geschoben werden, weil er extrem wichtig ist bzw. unformatierter Code praktisch nicht lesbar ist. Edit: vielleicht sollte der Satz "Für Sourcecode gibts die [code=cpp][/code]-Tags, mit gut erkennbarem Syntaxhighlighting." raus aus dem "schreib lesbar" und als eigener Bullet "Formatiere den Quellcode" als 2. Bullet hinter dem "Reduziere aufs Wesentliche".



  • Ich bin der Meinung, dass man schon etwas Eigeninitiative zeigen muss, wenn man um Hilfe bittet. Einfach Quelltext per Copy&Paste in´s Forum zu schmieren und nicht eine einzige Zeile Quelltext selbst geschrieben zu haben verdient einen Hinweis darauf, wie man richtig um Hilfe bittet.



  • Liebe Alle

    Ich hoffe das passt jetzt so. Ansonst tut es mir leid

    #include "grid.h"
    
    // Check if the filled grid matches the hints.
    
    bool check_solution(const grid& nonogram,
    const std::vector<hints>& row_hints,
    const std::vector<hints>& col_hints) {
    
    // TODO
    
    return false;
    }
    
    // Solve recursively, filling the grid row-by-row.
    
    bool solve_from(grid& nonogram,
    const std::vector<hints>& row_hints,
    const std::vector<hints>& col_hints,
    unsigned int row, unsigned int col) {
    
    // TODO
    
    return check_solution(nonogram, row_hints, col_hints);
    }
    
    // Solve the nonogram, given the grid and the lists of hints.
    // Run recursive solver from position (0, 0).
    
    bool solve(grid& nonogram,
    const std::vector<hints>& row_hints,
    const std::vector<hints>& col_hints) {
    return solve_from(nonogram, row_hints, col_hints, 0, 0);
    }
    int main() {
    grid nonogram;
    std::vector<hints> row_hints, col_hints;
    read_grid(nonogram, row_hints, col_hints);
    if (!hints_match(row_hints, col_hints)) {
    std::cout << "The numbers in hints do not match!\n";
    return -1;
    }
    bool solved = solve(nonogram, row_hints, col_hints);
    if (solved) {
    std::cout << "FINAL RESULT\n";
    print_grid(nonogram);
    } else {
    std::cout << "No solution found.\n";
    }
    return 0;
    }
    


  • @DocShoe

    Es tut mir leid, dass ich dir das Gefühl gegeben habe. Tatsächlich war es so, dass mir nicht klar war das ``` den code "gut" zeigt.

    Als Anfänger finde ich das ziemlich cool. Vor allem da man den Code so tatsächlich viel besser lesen kann. Ich verstehe, dass der andere Code mühsam zu lesen war und hoffe, dass ihr mir den Fehler verzeihen könnt.


  • Mod

    @wob sagte in Nonogram Programm:

    Außerdem sollte dieser Hinweis vermutlich auf der Hilfe-Seite weiter nach oben geschoben werden, weil er extrem wichtig ist bzw. unformatierter Code praktisch nicht lesbar ist. Edit: vielleicht sollte der Satz "Für Sourcecode gibts die [code=cpp][/code]-Tags, mit gut erkennbarem Syntaxhighlighting." raus aus dem "schreib lesbar" und als eigener Bullet "Formatiere den Quellcode" als 2. Bullet hinter dem "Reduziere aufs Wesentliche".

    Danke, habe ich korrigiert und stärker hervorgehoben. Aber nicht nach oben verschoben, denn alle Punkte sind wichtig, und dieser spezielle Punkt scheint bloß jetzt besonders wichtig, weil er hier nicht beachtet wurde. Ich würde nicht sagen, dass die anderen Punkte weniger häufig missachtet werden. Tatsächlich verletzte der Fragesteller hier sogar ziemlich alle, daher auch der Link als Antwort auf seine "Frage".



  • Auf den Zeilen 28-50 seht ihr einen Ansatz den man mir gegeben hat. Leider verstehe ich nicht ganz was dieser Teil des Codes genau macht.

    Zusätzliche Tipps die ich bekommen habe sind:

    -am anfang von solvefrom überprüft ihr ob es am ende des feldes ist

    • falls ja check_solution aufrufen
    • falls nein einfach weitermachen
    • beim weitermachen überprüft ihr zuerst ob ihr am ende der soalte angekommen seid. col==nonogram.at(0).size()
    • falls ja: col = 0;row+=1
    • danach füllt ihr das derzeitige feld mit einem '.'
    • dann bool done = solve_from (nonogram,row_hints, col_hints,row, col+1)
    • falls done als true zurückkommt seid ihr fertig
    • falls es als false zurück kommt setzt ihr das feld des nonograms als die andere option ein
    • bool done = solve_from (nonogram,row_hints, col_hints, row, col+1)
    • falls done immer noch als false zurück kommt geht ihr einen schritt zurück

    Ich frage nicht nach einer Lösung für meine Hausaufgaben. Viel mehr hoffe ich, dass ihr mir helfen könnt diese Tipps und schlussendlich die Aufgabe zu verstehen. Ich hoffe wirklich diesmal habe ich alles richtig gemacht 🙂

    #include "grid.h"
    
    // Check if the filled grid matches the hints.
    bool check_solution(const grid& nonogram,
                        const std::vector<hints>& row_hints,
                        const std::vector<hints>& col_hints) {
        if (solutions -> size ()!= 0){
        return false;
    }
    LineState& start_ = *start_state_;
    if(counter_>0){
      std::vector <bool> & indices_ = *current_indices_;
      bool index;
      for (int i = 0; i < indices_.size(); i++) {     
        if  (( start_[i]==kUnknown  ) && indices_[i] ) {
          solutions->push_back(i);
        }
      }
    }
    return true;
    }
    
    // Solve recursively, filling the grid row-by-row.
    bool solve_from(grid& nonogram,
    const std::vector<hints>& row_hints,
    const std::vector<hints>& col_hints,
    unsigned int row, unsigned int col) {
      unsigned int rows=get_rows(nonogram)-1;
      unsigned int cols=get_cols(nonogram)-1;
      bool a=0
      nonogram.at(row).at(col)='#';
      if(col<cols)
      a=solve_from(nonogram,row_hints,col_hints,row,col+1);
      else if(row<rows)
      a=solve_from(nonogram,row_hints,col_hints,row+1,0);
      else 
      a=check_solution(nonogram,row_hints,col_hints);
      
      col==nonogram.at(0).size() //checking if at the end of the column
      if (col=0;row+=1){
        nonogram.at(row).at(col)='.'
     bool done=solve from(nonogram,row_hints,col_hints,row,col+1)
     //falls done als true zurückkommt ist man fertig
     if done=1{
       return check_solution(nonogram,row_hints,col_hints);
     }
    //falls false feld des nonograms als andere Option einsetzen   
    bool done=solve from(nonogram,row_hints,col_hints,row,col+1)
    //falls done immernoch false -> Schritt zurück gehen
      
      return check_solution(nonogram, row_hints, col_hints);              
    }
    
    // Solve the nonogram, given the grid and the lists of hints.
    // Run recursive solver from position (0, 0).
    bool solve(grid& nonogram,
               const std::vector<hints>& row_hints,
               const std::vector<hints>& col_hints) {
        return solve_from(nonogram, row_hints, col_hints, 0, 0);
    }
    
    int main() {
      
      grid nonogram;
      std::vector<hints> row_hints, col_hints;
    
      read_grid(nonogram, row_hints, col_hints);
      
      if (!hints_match(row_hints, col_hints)) {
          std::cout << "The numbers in hints do not match!\n";
          return -1;
      }
      
      bool solved = solve(nonogram, row_hints, col_hints);
      
      if (solved) {
          std::cout << "FINAL RESULT\n";
          print_grid(nonogram);
      } else {
        std::cout << "No solution found.\n";
      }
      
      return 0;
    }
    

  • Mod

    @madelinemiller sagte in Nonogram Programm:

    @DocShoe

    Es tut mir leid, dass ich dir das Gefühl gegeben habe. Tatsächlich war es so, dass mir nicht klar war das ``` den code "gut" zeigt.

    Als Anfänger finde ich das ziemlich cool. Vor allem da man den Code so tatsächlich viel besser lesen kann. Ich verstehe, dass der andere Code mühsam zu lesen war und hoffe, dass ihr mir den Fehler verzeihen könnt.

    Es fehlt immer noch eine Frage. Das ist der Code aus der Aufgabenstellung. Was möchtest du wissen? Selbst wenn du nur willst, dass wir dir die Hausaufgaben machen (unwahrscheinlich, aber nicht ausgeschlossen, dass sich jemand erbarmt), hast du ja nicht einmal die eigentliche Aufgabe wiedergegeben.



  • Es fällt mir schwer Fragen zu stellen, da ich hier wirklich komplett verloren bin. Eine Leitung durch die Aufgabe oder ein Erklären der Tipps wäre toll.

    Mir ist bewusst, dass das Geduld erfordert und ich es euch nicht gerade einfach mache mir zu helfen. Aber so wie Mathe einigen nicht liegt, liegt mir C++ nicht.

    Zu der Aufgabenstellung. Diese habe ich nicht gepostet, da sie sehr lang ist und ich nicht dachte, dass jemand die Geduld hätte sie durchzulesen.

    Zusammengefasst besagt sie:

    Man sollte ein Programm schreiben welches ein Nonogram löst. Das Programm liest die Nonogram Beschreibung als input und gibt die Lösung als output.

    Hier die Aufgabenstellung etwas ausführlicher aber immer noch gekürzt:

    The purpose of this task is to implement a program solving Nonograms. This puzzle is played on a n×m grid.

    We provide type grid which is a two-dimensional vector of characters
    using
    grid = std::vector<std::vector<char>>;
    representing the grid.

    In the beginning, the grid contains only whitespaces, corresponding to cells with unknown content.
    The character '#' stands for a marked cell, while '.' stands for a cell which is known to be empty.

    In the provided code skeleton, we use a variable of type grid and name it nonogram.
    A cell in its i-th row and j-th column can be accessed as nonogram.at(i).at(j). For example,
    nonogram.at(0).at(0) = '#';
    marks the upper-left corner of the grid.

    We also provide a type hints which is a one-dimensional vector of unsigned integers
    using hints = std::vector<unsigned int>;
    In the provided code skeleton, we use two vectors (of hints, i.e. vectors)std::vector<hints> to describe row_hints and col_hints
    We number the rows from top to bottom and the columns from left to right. For example,
    row_hints.at(i).at(j) > 5 && col_hints.at(k).at(l) > 1
    checks if the j-th hint in i-th row is greater than 5, and the l-th hint in k-th column is greater than 1.

    To make the task easier, our skeleton provides function main which reads and verifies the nonogram, runs the solver, and outputs the result.



  • @SeppJ sagte in Nonogram Programm:

    Danke, habe ich korrigiert und stärker hervorgehoben.

    👍



  • @madelinemiller Du hast ja in solve_fromschon irgendwas gemacht. Was davon, hast du warum genau gemacht? Wo beschwert sich denn schon dein Compiler (und warum wohl)?

    Wenn C++ insbesondere nicht deine Stärke ist, wie würdest du das Problem denn in Pseudocode lösen?



  • @Schlangenmensch

    Zuerst einmal danke für deine Antwort 🙂

    Das im solve_from hab nicht ich gemacht. War ein Tipp. Diesen verstehe ich leider nicht bzw verstehe ich nicht genau was der Code macht. Desshalb weiss ich auch nicht wie weiter oder besser wo ich mich auf der "Checkliste"befinde.

    Und mit "C++ ist nicht meine Stärke" meinte ich eigentlich das Programmieren allgemein. Alles was wir lernen ist C++.

    Was mich zu der Frage führt. Was ist ein Pseudocode?



  • Vielleicht hilft es wenn ich selbst eine konkrete Frage nach der anderen stelle.

    Angefangen mit:

    Wieso überprüft man ob man am Ende vom Feld ist?
    Was genau ist mit dem Ende des Feldes gemeint?
    Und wie ginge das?
    Hat Zeile 28-50 dies schon erledigt?

    Frage bezieht isch auf den oben erwähnten Tipp 1:
    "- Am Anfang von solve from überprüft ihr ob es am ende des feldes ist



  • @madelinemiller sagte in Nonogram Programm:

    Wieso überprüft man ob man am Ende vom Feld ist?

    Du wirst wohl das Feld von oben links bis unten rechts durchgehen. Für jedes Feld probierst du den Status "leer" und "voll" aus und setzt jeweils die Suche mit dem nächsten Feld fort, solange bis du bei dem letztem Feld unten rechts angekommen bist. Ich hoffe, dass dir das schon hilft.



  • @wob

    Also wenn ich am Ende des Feldes angelangt bin ist das schon vom Code vorher gemacht oder muss ich das nach dem solve from programmieren?
    und den status leer und voll kann man mit einem bool machen oder?



  • Ah und ich muss das wahrscheinlich in eine Schleife packen(zb while oder so)oder ist das der falsche Ansatz?

    (PS: Die Erklärung war toll. Hab zwar noch keine Ahnung wie ich das coden will und es hat zu noch mehr Fragen geführt, aber sehr verständlich und eine erste Idee. Danke dafür! 🙂 )



  • Siehe vorletzten Hinweis: bool done = solve_from (nonogram,row_hints, col_hints, row, col+1)

    Du rufst einfach die Funktion, in welcher du gerade bist, rekursiv für das nächste Feld auf. Schau die vielleicht mal https://de.wikipedia.org/wiki/Rekursive_Programmierung an.

    und den status leer und voll kann man mit einem bool machen oder?

    Ja, aber: nein, das ist nämlich auch in der Aufgabe vorgegeben. Du hast ein char-Array. Ich zitiere aus der Aufgabe:

    In the beginning, the grid contains only whitespaces, corresponding to cells with unknown content. The character '#' stands for a marked cell, while '.' stands for a cell which is known to be empty.

    Aber prinzipiell hast du recht, bool wäre sinnvoll für markiert/nicht markiert (*). Ihr verwendet aber offenbar auch noch den dritten Status "unbekannt". (Warum eigentlich als chars und nicht als enum? Weiß wohl nur der Aufgabensteller!)

    (*) um dich nicht (?) zu verwirren: std::vector<bool> verhält sich in C++ anders als andere vectoren und wird daher gerne vermieden



  • @wob

    Oke mit dieser Antwort bin ich leicht überfordert. Muss mir die wohl noch ein paar Mal durch lesen.
    Aber danke dir.

    Zudem:
    Was ist genau ein char-array?



  • Andere Frage:

    Zeile 38-50 hab ich selber hinzugefügt und da probiert die Hinweise in Code/Text umzuwandeln.
    Stimmt das ungefähr oder bin ich da komplett auf den Holzweg?


Log in to reply