Binary Puzzle Solver - 10000 questions

Question

I finished creating a binary puzzle solver. The game can be found here: http://binarypuzzle.com/.

The rules for the game are:

1. Each box should contain a zero or a one.
2. No more than two similar numbers next to or below each other are allowed.
3. Each row and each column should contain an equal number of zeros and ones.
4. Each row is unique and each column is unique.

Each binary puzzle does only have one solution. You can always find this solution without guessing.

---

I solved it by just generating all possibilities and putting it against the rules.

I still have a couple of question about the quality of my code and what is preferred and not. Here are my questions about my BinaryPuzzle class:

1. Should BLANK be private static inside the BinaryPuzzle class? Or would it be better if I had an Enum for BLANK, ONE, and ZERO?
2. Is the name values[][] a good name? Why not boardValues or board?
3. Say I make a jar of this and someone would use this class, he will always have to extend this class if he wants to get the values[][] is that too strict?

public class BinaryPuzzle {

  private static final int BLANK = -1;

  private final int size;
  private final int[][] values;

  public BinaryPuzzle(int size) {
    if (size < 6 || size > 14 || size % 2 != 0) {
      throw new IllegalArgumentException("Invalid size. Only size of 6, 8, 10, 12, 14 allowed.");
    }
    this.size = size;
    values = new int[size][size];
    fillValuesWithBlank();
  }

  public BinaryPuzzle setValue(int x, int y, int value) {
    if (value != 0 && value != 1) {
      throw new IllegalArgumentException("Only 0 or 1 allowed.");
    }
    if ((x < 0 || x >= size) || (y < 0 || y >= size)) {
      throw new IllegalArgumentException(
          "x or y is outside the bounds. Only values between 0 and " + (size - 1) + " allowed.");
    }
    values[x][y] = value;
    return this;
  }

  protected int[][] getValues() {
    return values;
  }

  protected void fillValuesWithBlank() {
    for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
        values[i][j] = BLANK;
      }
    }
  }

  @Override
  public String toString() {
    StringBuilder stringBuilder = new StringBuilder();
    for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
        stringBuilder
            .append(values[i][j])
            .append(" ");
      }
      stringBuilder.append("\n"); // newline
    }
    return stringBuilder.toString();
  }

}

Questions about the BinaryPuzzleSolver class:

1. Should my solve() method be static? It is stateless, but if I make it static I can't override any methods.
2. Should solve() clone/copy BinaryPuzzle and return a new one? Or is the fact that it returns a boolean enough to imply that the BinaryPuzzle given as param is modified?
3. solve() actually only uses the values[][] from BinaryPuzzle, should that be the param instead?
4. Are my helper methods good with regards to naming and lenght? I tried to think about good names and make them smaller about 7 lines, but it is hard!
5. As you can see some methods have the default modifier instead of private, because they are less trivial and I wanted to write tests for them. Performing TDD and testing only public methods (solve() in this case) seems bad, so much functionality is in solve(). But making my methods that I want to test default seems weird, I have never seen someone do that. The classes that I left private are hard to test or are trivial.
6. I had a hard time thinking about a good name for my HashMap inside solve() method and the mapAllMatchingBinaryNumbersToEachBinaryNumberInsideBinaryPuzzleBasedOnSetValues is downright rediculous. Any suggestions?

public class BinaryPuzzleSolver {
// NOTE: each binary number is an int[]

  public boolean solve(BinaryPuzzle binaryPuzzle) {
    int[][] binaryPuzzleValues = binaryPuzzle.getValues();

    List<int[]> binaryNumbers = generateAllBinaryNumbersWithBitSizeOf(
        binaryPuzzleValues.length);

    binaryNumbers.removeIf(this::binaryNumberInvalidBecauseOfRules);

    HashMap<Integer, List<int[]>> matchingBinaryNumbersForBinaryPuzzleRows =
        mapAllMatchingBinaryNumbersToEachBinaryNumberInsideBinaryPuzzleBasedOnSetValues(
            binaryNumbers, binaryPuzzleValues);

    return solveByTryingOutAllPossibilitiesAndCheckingAgainstBinaryPuzzleRules(
        matchingBinaryNumbersForBinaryPuzzleRows, binaryPuzzleValues);  
   }

  List<int[]> generateAllBinaryNumbersWithBitSizeOf(int numberOfBits) {
    List<int[]> binaryNumbers = new ArrayList<>();
    int largestBinaryNumber = (int) Math.pow(2, numberOfBits);
    for (int i = 0; i < largestBinaryNumber; i++) {
      int[] binaryNumber = convertDecimalToBinary(i, numberOfBits);
      binaryNumbers.add(binaryNumber);
    }
    return binaryNumbers;
   }

  private int[] convertDecimalToBinary(int decimalValue, int numberOfBits) {
    int[] binaryNumber = new int[numberOfBits];
    for (int j = 1; decimalValue != 0; j++) {
      binaryNumber[numberOfBits - j] = decimalValue % 2;
      decimalValue /= 2;
    }
    return binaryNumber;
   }

  boolean binaryNumberInvalidBecauseOfRules(int[] binaryNumber) {
    return numberContainsMoreThan2SimilarBitsAfterEachOther(binaryNumber)
        || numberContainsUnequalAmountOfOnesAndZeros(binaryNumber);
   }

  private HashMap<Integer, List<int[]>> mapAllMatchingBinaryNumbersToEachBinaryNumberInsideBinaryPuzzleBasedOnSetValues(
      List<int[]> binaryNumbers, int[][] binaryPuzzleValues) {
    HashMap<Integer, List<int[]>> matchingBinaryNumbersForBinaryPuzzleRows = new HashMap<>();
    for (int i = 0; i < binaryPuzzleValues.length; i++) {
      int[] binaryPuzzleRow = binaryPuzzleValues[i]; // <-- binaryPuzzleRow is also a binaryNumber.
      // I think it is easier in this method to think about the binaryNumbers as a row inside the binary puzzle
      List<int[]> matchingBinaryNumbersForCurrentBinaryPuzzleRow = findMatchesForBinaryPuzzleRowBasedOnSetValues(
          binaryNumbers,
          binaryPuzzleRow);
      matchingBinaryNumbersForBinaryPuzzleRows
          .put(i, matchingBinaryNumbersForCurrentBinaryPuzzleRow);
    }
    return matchingBinaryNumbersForBinaryPuzzleRows;
   }

  private List<int[]> findMatchesForBinaryPuzzleRowBasedOnSetValues(List<int[]> binaryNumbers,
      int[] binaryPuzzleRow) {
    List<int[]> matchingBinaryNumber = new ArrayList<>();
    for (int[] array : binaryNumbers) {
      boolean isMatch = true;
      for (int i = 0; i < binaryPuzzleRow.length; i++) {
        if (binaryPuzzleRow[i] != -1) {
          if (binaryPuzzleRow[i] != array[i]) {
            isMatch = false;
            break;
          }
        }
      }
      if (isMatch) {
        matchingBinaryNumber.add(array);
      }
    }
    return matchingBinaryNumber;
   }

  private boolean solveByTryingOutAllPossibilitiesAndCheckingAgainstBinaryPuzzleRules(
      HashMap<Integer, List<int[]>> matchingBinaryNumbersForBinaryPuzzleRows,
      int[][] binaryPuzzleValues) {
    int allPossibilities = 1;
    for (int i = 0; i < binaryPuzzleValues.length; i++) {
      allPossibilities *= matchingBinaryNumbersForBinaryPuzzleRows.get(i).size();
    }
    System.out.println(
        "Amount of possible board configurations to be checked: " + allPossibilities + "\n");
    return solve(matchingBinaryNumbersForBinaryPuzzleRows, 0, binaryPuzzleValues);   }

  // 8 months ago when I first created this I was kissing my fingers, now I'm sitting here thinking wtf is this...
  private boolean solve(Map<Integer, List<int[]>> matchingBinaryNumbersForBinaryPuzzleRows,
      int mapKey,
      int[][] binaryPuzzleValues) {
    if (mapKey == matchingBinaryNumbersForBinaryPuzzleRows.size()) {
      return verticalBinariesNumberValid(binaryPuzzleValues) && binaryNumbersUnique(
          binaryPuzzleValues); // base
    }
    for (int i = 0; i < matchingBinaryNumbersForBinaryPuzzleRows.get(mapKey).size(); i++) {
      binaryPuzzleValues[mapKey] = matchingBinaryNumbersForBinaryPuzzleRows.get(mapKey).get(i);
      if (solve(matchingBinaryNumbersForBinaryPuzzleRows, mapKey + 1,
          binaryPuzzleValues)) { // recurse
        return true;
      }
    }
    return false;
   }

  private boolean verticalBinariesNumberValid(int[][] values) {
    int size = values.length;
    int[] verticalBinaryNumber = new int[size];
    for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
        verticalBinaryNumber[j] = values[j][i];
      }
      if (binaryNumberInvalidBecauseOfRules(verticalBinaryNumber)) {
        return false;
      }
    }
    return true;
   }

  private boolean binaryNumbersUnique(int[][] values) {
    return horizontalBinaryNumbersUnique(values) && verticalBinaryNumbersUnique(values);
   }

  private boolean horizontalBinaryNumbersUnique(int[][] values) {
    int size = values.length;
    int[] tempBinaryNumber = new int[size];
    for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
        tempBinaryNumber[j] = values[i][j];
      }
      for (int k = i + 1; k < size; k++) {
        if (Arrays.equals(values[k], tempBinaryNumber)) {
          return false;
        }
      }
    }
    return true;
   }

  private boolean verticalBinaryNumbersUnique(int[][] values) {
    int size = values.length;
    int[] tempBinaryNumber = new int[size];
    for (int i = 0; i < size; i++) {
      int[] tempBinaryNumberVertical = new int[size];
      for (int j = 0; j < size; j++) {
        tempBinaryNumber[j] = values[j][i];
      }
      for (int k = i + 1; k < size; k++) {
        for (int l = 0; l < size; l++) {
          tempBinaryNumberVertical[l] = values[l][k];
        }
        if (Arrays.equals(tempBinaryNumberVertical, tempBinaryNumber)) {
          return false;
        }
      }
    }
    return true;
   }

  boolean numberContainsMoreThan2SimilarBitsAfterEachOther(int[] binaryNumber) {
    for (int i = 0; i < binaryNumber.length; i++) {
      int currentBit = binaryNumber[i];
      int threeInARowCounter = 1;
      for (int j = -1; j < 2; j += 2) {
        int previousAndNextIndex = i + j;
        if (previousAndNextIndex < 0 || previousAndNextIndex > (binaryNumber.length - 1)) {
          break;
        }
        if (currentBit == binaryNumber[previousAndNextIndex]) {
          threeInARowCounter++;
        }
        if (threeInARowCounter == 3) {
          return true;
        }
      }
    }
    return false;
   }

  boolean numberContainsUnequalAmountOfOnesAndZeros(int[] binaryNumber) {
    int amountOfOnes = 0;
    for (int i : binaryNumber) {
      if (i == 1) {
        amountOfOnes++;
      }
    }
    return amountOfOnes != (binaryNumber.length / 2);
   }

}

How to run:

public class BinaryPuzzleSolverTest {

  private BinaryPuzzleSolver binaryPuzzleSolver = new BinaryPuzzleSolver();

  @Test
  public void test() {
    // http://binarypuzzle.com/puzzles.php?size=6&level=4&nr=2
    BinaryPuzzle binaryPuzzle = new BinaryPuzzle(6);
    binaryPuzzle
        .setValue(0, 1, 0)
        .setValue(2, 0, 1)
        .setValue(3, 1, 0)
        .setValue(3, 4, 0)
        .setValue(4, 0, 1)
        .setValue(4, 3, 0)
        .setValue(5, 1, 0)
        .setValue(5, 5, 0);
    System.out.println(binaryPuzzle.toString());

    System.out.println(new BinaryPuzzleSolver().solve(binaryPuzzle));
    System.out.println(binaryPuzzle.toString());
  }
}

Note: Probably too much in 1 post, how should I otherwise split my question? Is it überhaupt a good question?

Answer 1

A lot of your questions seem to have a "functional programming" tendency to them. I write in C# everyday, but I try to write like a functional programmer as much as possible until the solution stops feeling natural to the language you're writing in. So I'll express some possibilities, but leave it to you to decide how far to go.

Should BLANK be private static inside the BinaryPuzzle class? Or would it be better if I had an Enum for BLANK, ONE, and ZERO?

You most certainly can do this, but will it benefit you? A functional programmer would be very inclined to have not just a value, but a type for each number. However, doing this in Java isn't cheap or what people expect. If you have an enum, you can get rid of some of your defensive programming checks. Doing that would probably be worth it.

Is the name values[][] a good name? Why not boardValues or board?

It's a private variable, so it's not hugely concerning that it spell itself out exactly. I'm a firm believer that if your variable or member needs a long name, your class or function is probably trying to do too many things. Short names can be great.

Say I make a jar of this and someone would use this class, he will always have to extend this class if he wants to get the values[][] is that too strict?

I'm not sure what the inheritance possibilities are for this class. A functional programmer would write the functionality and it would all be generally available. Inheritance puts a weird twist on this. If you have real plans for it to be inherited, then consider whether or not those classes will need to know about it at all. If you don't have any immediate inheritance scenarios, I wouldn't worry about it for now.

Should my solve() method be static? It is stateless, but if I make it static I can't override any methods.

There's nothing more testable than a stateless static function. It's simply the best and what functional programming puts in the forefront.

Should solve() clone/copy BinaryPuzzle and return a new one? Or is the fact that it returns a boolean enough to imply that the BinaryPuzzle given as param is modified?

Again, a functional programmer would say absolutely return a new copy. In Java, you don't get the same language benefits that make this cheap or even worth it sometimes. So... you can, but it'll cost you code and complexity in Java.

solve() actually only uses the values[][] from BinaryPuzzle, should that be the param instead?

I would vote for that. A wrapper type of BoardValues that carries that double array would be very effective.

Are my helper methods good with regards to naming and lenght? I tried to think about good names and make them smaller about 7 lines, but it is hard!

Naming is the hardest part of programming most of the time. I would say there's a long one or two in here, but they seem to make a lot of sense so I'd be inclined to leave them. Method size is a good thing to be aware of. You should think about it in terms of how many things is my method doing. Generally speaking, methods that do fewer things are better and are usually short. Long methods are a code smell, but not a hard-fast rule.

As you can see some methods have the default modifier instead of private, because they are less trivial and I wanted to write tests for them. Performing TDD and testing only public methods (solve() in this case) seems bad, so much functionality is in solve(). But making my methods that I want to test default seems weird, I have never seen someone do that. The classes that I left private are hard to test or are trivial.

When I write private methods, I do not test them individually. I have on occasion made a function internal to be able to test it. But I think a better solution is to move that function to a static class and make it public (if possible). This is another benefit of a function style of programming.

I had a hard time thinking about a good name for my HashMap inside solve() method and the mapAllMatchingBinaryNumbersToEachBinaryNumberInsideBinaryPuzzleBasedOnSetValues is downright rediculous. Any suggestions?

I think the context is small. A large name shouldn't be required. That function has 5 executable lines, if understanding a short name is too difficult under those conditions, the method should be split up.

I've hammered away at the function nature of your questions only because it would seem you have good tendencies towards that kind of thinking. I'm a C# / F# programmer by trade. You should consider learning Scala perhaps. You'd probably enjoy it.