Implementing an algorithm to check a nonogram solution

user_15425383 0
Viewed 1342

I am trying to write an algorithm to check if a nonogram has been solved. I have already create multiple classes to have helper methods. The design for what I have so far is a class for Clues where the constructor looks like this:

public Clues(int[][] rowClues, int[][] colClues) { // constructor stuff }

I am storing the clues in these 2D arrays. For example, this puzzle would have the clues stored like this:

int[][] rowClues =
    new int[][] {
      new int[] {0, 2},
      new int[] {1, 2},
      new int[] {0, 3},
      new int[] {0, 3},
      new int[] {1, 1},
    };

int[][] colClues =
    new int[][] {
      new int[] {1, 1},
      new int[] {0, 1},
      new int[] {0, 3},
      new int[] {0, 3},
      new int[] {3, 1},
    };

I created another class called Puzzle that is composed of a board (for the game) and the clues. I am trying to write a function called isSolved to check if the Puzzle has been solved, but I am struggling on how to come up with an algorithm. I currently have this:

    public boolean isSolved() {

    boolean flag = false;
    for (int i=0; i<clue.getColCluesLength(); i++) {
      flag = checkColumn(getBoard().getBoardColumn(i), getClues().getColClues(i));
      if (flag == false) {
        return false;
      }
    }
    for (int i=0; i<clue.getRowCluesLength(); i++) {
      flag = checkRow(getBoard().getBoardRow(i), getClues().getRowClues(i));
      if (flag == false) {
        return false;
      }
    }
    return flag;
  }
 

  public boolean isRowSolved() {
    for (int i=0; i< clue.getRowCluesLength(); i++) {
      for (int j=0; j< clue.getRowClues(i).length; j++) {

      }
    }
    return false;
  }

The board (2D array) I have stores int's, and certain values represent elimination, space, and shaded.

I'm thinking I could compare the existing array in the board with the clues array, but I'm not sure how to exactly do that.

Some helper methods for this part are: int[] getRowClues(int index), int getColRowCluesLength(), int getWidth() (# of cells horizontally in each row of puzzle), getBoard().isShaded(), getBoard().isEliminated(), getBoard().isSpace()

algorithm java
2 Answers

A solution is correct if every column and every row satisfies all the clues. Clearly, a correct solution cannot contain blank cells, that is, a cell must be either shaded or eliminated. So to validate a solution, you must iterate over every column and every row, and check whether the clues are satisfied.

A small note: the isSolved() method could be simplified to:

public boolean isSolved(){
    return isRowSolved() && isColSolved();
}

Now to check a row or a column, there are various approaches you could use. Here's one that simply constructs a new 'clue' based on a column, and then compares this new clue with the actual clue.

private boolean checkColumn(int[] column, int[] clue){
  int count = 0; // Count sequence of shaded cells
  List<Integer> newClue=new LinkedList<>();
  for(int i=0; i<column.length; i++){
    if(column[i] == SHADED){ //Found a new shaded cell, increment counter
      count++;
    }else if(column[i] == ELIMINATED){ //Found a ELIMINATED cell. If counter >0, we completed a sequence
      if(count > 0){
        newClue.add(count);
        count=0; //Reset counter
      }
    }else{
      return false; //blank cell
    }
  }
  if(count > 0) //Remember to add the last one too
    newClue.add(count);
    
  //Finally, we can check whether the given clue matches the clue constructed from the column:
  int[] newClueArray = newClue.stream().mapToInt(i->i).toArray();
  return Arrays.equals(clue, newClueArray)
}

The method above returns true if the given column satisfies the given clue, false otherwise. False is also returned if the column contains a blank cell.

Note: I don't know whether a nonogram can contain columns which do not contain any shaded cells (i.e. all cells are eliminated). If this happens, than I presume that the clue for such a column is new int[]{0}, in which case you would have to verify that newClue in the above example code is an empty list.

user_19038520 
public class Nonogram {

    public static void main(String[] args) {
        char[][] input = {
                {'W', 'W'},
                {'B', 'B'},
                {'B', 'B'},
                {'W', 'B'}
        };
        int[][] rowInstructions = {{}, {2}, {2}, {1}};
        int[][] colInstructions = {{2}, {2}};
        System.out.println(nonoChecker(input, rowInstructions, colInstructions));
    }

    public static boolean nonoChecker(char[][]input, int[][] rowInstructions,
                                   int[][] colInstructions) {
        for (int i = 0; i<rowInstructions.length; i++) {
            List<Integer> rowEncoding = rowEncoding(input, i);
            int[] encoded = rowEncoding.stream().mapToInt(c->c).toArray();
            if (!Arrays.equals(encoded, rowInstructions[i])) {
                return false;
            }
        }
        for (int i = 0; i<colInstructions.length; i++) {
            List<Integer> columnEncoding = columnEncoding(input, i);
            int[] encoded = columnEncoding.stream().mapToInt(c->c).toArray();
            if (!Arrays.equals(encoded, colInstructions[i])) {
                return false;
            }
        }
        return true;
    }
    public static List<Integer> rowEncoding(char[][] input, int row) {
        List<Integer> result = new LinkedList<>();
        int count = 0;
        for (int j = 0; j < input[row].length; j++) {
            if (input[row][j] == 'B') {
                count++;
            } else if (count > 0) {
                result.add(count);
                count = 0;
            }
        }
        if (count > 0) {
            result.add(count);
        }
        return result;
    }

    public static List<Integer> columnEncoding(char[][] input, int col) {
        List<Integer> result = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < input.length; i++) {
            if (input[i][col] == 'B') {
                count++;
            } else if (count > 0) {
                result.add(count);
                count = 0;
            }
        }
        if (count > 0) {
            result.add(count);
        }
        return result;
    }

}
user_18235250
Related