4 By 4 Skyscrapers in Java

The challenge

In a grid of 4 by 4 squares you want to place a skyscraper in each square with only some clues:

The height of the skyscrapers is between 1 and 4
No two skyscrapers in a row or column may have the same number of floors
A clue is the number of skyscrapers that you can see in a row or column from the outside
Higher skyscrapers block the view of lower skyscrapers located behind them

Can you write a program that can solve this puzzle?

Example:

To understand how the puzzle works, this is an example of a row with 2 clues. Seen from the left side there are 4 buildings visible while seen from the right side only 1:


4					1

There is only one way in which the skyscrapers can be placed. From left-to-right all four buildings must be visible and no building may hide behind another building:


4	1	2	3	4	1

Example of a 4 by 4 puzzle with the solution:


	1	2

			2
1

	3


			1	2
	2	1	4	3
	3	4	1	2	2
1	4	2	3	1
	1	3	2	4
			3

Task:

Finish:

`1`	`public static int[][] solvePuzzle (int[] clues)`

Pass the clues in an array of 16 items. This array contains the clues around the clock, index:
0 1 2 3 15 4 14 5 13 6 12 7 1110 9 8
If no clue is available, add value `0`
Each puzzle has only one possible solution
`SolvePuzzle()` returns matrix `int[][]`. The first indexer is for the row, the second indexer for the column. (Python: returns 4-tuple of 4-tuples, Ruby: 4-Array of 4-Arrays)

The solution in Java code

Option 1:

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class SkyScrapers {

  private final static Integer SIZE = 4;

  static int[][] solvePuzzle (int[] clues) {
    return new SkyScrapers().solve(clues);
  }
  
  private static class AbortException extends Exception { }

  private Table table;

  private int[][] solve(int[] clues) {
    table = new Table(clues);
    try {
      Position initPosition = table.getInitPosition();
      if (iter(initPosition)) return table.table;
      else throw new RuntimeException("no solution");
    } catch (AbortException e) { return table.table; }
  }

  private boolean iter(Position position) {
    Set<Integer> possibleValues = table.getPossibleValuesForPosition(position);
    for (Integer possibleValue : possibleValues) {
      table.setValueForPosition(position, possibleValue);
      try {
        Position nextPosition = table.getNextPosition(position);
        if(iter(nextPosition))
          return true;
        else
          table.setValueForPosition(position, 0);
      } catch (AbortException e) { return true; }
    }
    return false;
  }

  static class Position {
    Integer x;
    Integer y;

    Position(Integer x, Integer y) {
      this.x = x;
      this.y = y;
    }

    Integer getX() {
      return x;
    }

    Integer getY() {
      return y;
    }
  }

  static class Table {
    int[][] table;
    Line[] horizontalLines = new Line[SIZE];
    Line[] verticalLines = new Line[SIZE];

    Table(int[] clues) {
      initTable();
      initLinesWithClues(clues);
    }

    private Integer getValueForPosition(int x, int y) {
      return table[y][x]; // inverted!
    }

    void setValueForPosition(Position position, int value) {
      int x = position.getX();
      int y = position.getY();
      setValueForPosition(x, y, value);
      verticalLines[x].line[y] = value; 
      horizontalLines[y].line[x] = value; 
    }

    private void setValueForPosition(int x, int y, int value) {
      table[y][x] = value; // inverted!
    }

    Position getInitPosition() throws AbortException {
      Position position = new Position(0,0);
      if (getValueForPosition(0,0) != 0) position = getNextPosition(position);
      return position;  
    }

    Position getNextPosition(Position position) throws AbortException {
      int x = position.getX();
      int y = position.getY();
      do {
        if (x == SIZE-1)
          if (y == SIZE-1)
            throw new AbortException();
          else {
            x = 0;
            y++;
          }
        else
          x++;
      } while (getValueForPosition(x,y) != 0);
      return new Position(x,y);
    }

    Set<Integer> getPossibleValuesForPosition(Position position) {
      int x = position.getX();
      int y = position.getY();
      Set<Integer> possibleValues = new HashSet<>();
      Set<Integer> possibleValuesForHorizontalLine = horizontalLines[y].getPossibleValuesForPosition(x); 
      Set<Integer> possibleValuesForVerticalLine = verticalLines[x].getPossibleValuesForPosition(y);
      possibleValues.addAll(possibleValuesForHorizontalLine);
      possibleValues.retainAll(possibleValuesForVerticalLine);
      return possibleValues;
    }

    private void initLinesWithClues(int[] clues) {
      IntStream.range(0, SIZE).forEach(x -> verticalLines[x] = new Line(getVerticalLine(x), clues[x], clues[3*SIZE-1-x]));
      synchTableWithVerticalLines();
      IntStream.range(0, SIZE).forEach(y -> horizontalLines[y] = new Line(getHorizontalLine(y), clues[4*SIZE-1-y], clues[SIZE+y]));
      synchTableWithHorizontalLines();
    }

    private void synchTableWithHorizontalLines() {
      for (int x = 0 ; x < SIZE ; x++)
        for (int y = 0 ; y < SIZE ; y++)
          setValueForPosition(x, y, horizontalLines[y].line[x]);
    }

    private void synchTableWithVerticalLines() {
      for (int x = 0 ; x < SIZE ; x++)
        for (int y = 0 ; y < SIZE ; y++)
          setValueForPosition(x, y, verticalLines[x].line[y]);
    }

    private int[] getVerticalLine(int x) {
      int[] line = new int[SIZE];
      IntStream.range(0, SIZE).forEach(y -> line[y] = getValueForPosition(x,y));
      return line;
    }

    private int[] getHorizontalLine(int y) {
      int[] line = new int[SIZE];
      IntStream.range(0, SIZE).forEach(x -> line[x] = getValueForPosition(x,y));
      return line;
    }

    private void initTable() {
      table = new int[SIZE][SIZE];
      IntStream.range(0, SIZE).forEach(i -> Arrays.fill(table[i], 0));
    }

  }

  static class Line {
    int[] line;
    int topClue;
    int bottomClue;

    private Set<Integer> allNonInitClues = IntStream.rangeClosed(2, SIZE-1).boxed().collect(Collectors.toSet());

    Line(int[] line, int topClue, int bottomClue) {
      this.line = line;
      this.topClue = topClue;
      this.bottomClue = bottomClue;
      resolveInitClues();
    }

    private void resolveInitClues() {
      if (topClue == 1) line[0] = SIZE;
      if (bottomClue == 1) line[SIZE-1] = SIZE;
      if (topClue == SIZE) IntStream.range(0, SIZE).forEach(i -> line[i] = i + 1);
      if (bottomClue == SIZE) IntStream.range(0, SIZE).forEach(i -> line[SIZE-1-i] = i + 1);
    }

    Set<Integer> getPossibleValuesForPosition(Integer positionInLine) {
      if(line[positionInLine] != 0)
        throw new IllegalArgumentException("Fatal Error : Trying to discover already discovered value !!"
            + "\n position = " + positionInLine + "\n line : " + this);
      Set<Integer> alreadyPlacedValues = getAlreadyPlacedValues(positionInLine);
      Set<Integer> possibleValues = IntStream.rangeClosed(1, SIZE).boxed().collect(Collectors.toSet());
      possibleValues.removeAll(alreadyPlacedValues); 
      possibleValues.removeIf(valueToTest -> !isCompatibleWithClues(valueToTest, positionInLine));
      return possibleValues;
    }

    private boolean isCompatibleWithClues(Integer valueToTest, int position) {
      line[position] = valueToTest;
      boolean result = true;
      if(this.isComplete()) result = this.isCompatibleWithClues(); // double negation!
      line[position] = 0;
      return result;
    }

    private boolean isComplete() {
      return IntStream.range(0, SIZE).allMatch(i -> line[i] != 0);
    }

    private boolean isCompatibleWithClues() {
      boolean isNotCompatibleWithClues = 
        (allNonInitClues.contains(topClue) && getNumberOfSkyCrapersOnLine(true) != topClue) ||
        (allNonInitClues.contains(bottomClue) && getNumberOfSkyCrapersOnLine(false) != bottomClue);
      return !isNotCompatibleWithClues;
    }

    private int getNumberOfSkyCrapersOnLine(boolean isAscending) {
      int result = 0;
      int maxValue = 0;
      for (int i = 0 ; i < SIZE ; i++) {
        int positionInLine = isAscending ? i : SIZE-1-i; 
        if (line[positionInLine] > maxValue) {
          maxValue = line[positionInLine];
          result++;
        }    
      }
      return result;
    }

    private Set<Integer> getAlreadyPlacedValues(int positionInLine) {
      Set<Integer> alreadyPlacedValues = new HashSet<Integer>();
      for (int i = 0 ; i < SIZE ; i ++) {
        if (i == positionInLine) continue;
        if (line[i] != 0) alreadyPlacedValues.add(line[i]);
      }
      return alreadyPlacedValues;
    }

  }
}

Option 2:

import java.util.*;
public class SkyScrapers {
  
  public static final int SIZE = 4;
  public static final int[][] direction = new int[][]{{0,1}, {1,0}, {0,-1}, {-1, 0}};
  public static int[][][] square3d;
  public static int row = 0, col = 0;
  public static int count;

  static int[][] solvePuzzle (int[] clues) {
    
    generateEmptySquare();

    while(count < SIZE * SIZE) {
      for(int i = 0; i < SIZE * 4; i++) {
       System.out.printf("i = %d, clue[i]=%d, r = %d, c = %d%n", i, clues[i], row, col);
        cleanAllHintsInLine(i);
        checkLineForOneHint(i);
        useClue(i, clues[i]);
        if((i + 1) % SIZE != 0) {
          row += direction[i / SIZE][0];
          col += direction[i / SIZE][1];
        }
      }
      checkSquareForOneHint();
    }
    
    int[][] result = new int[SIZE][SIZE];
    for(int i = 0; i < SIZE; i++) {
      for(int j = 0; j < SIZE; j++) {
        result[i][j] = square3d[i][j][0];
      }
    }
    
    return result;
  }
  
  static void useClue(int i, int clue) {
    switch(clue) {
        case 1:
          setSkyscraper(iRow(i, 0), iCol(i, 0), SIZE);
          cleanHintLine(i, SIZE);
          break;
        case 2:
          cleanHint(i, 0, SIZE);
          if(getSkyscraper(i, SIZE - 1) == SIZE) {
            setSkyscraper(iRow(i, 0), iCol(i, 0), SIZE - 1);
          }
          if(getSkyscraper(i, SIZE - 2) == SIZE) {
            cleanHint(i, 1, SIZE - 1);
          }
          if(getSkyscraper(i, SIZE - 2) == SIZE && getSkyscraper(i, SIZE - 1) == SIZE - 1) {
            setSkyscraper(iRow(i, 0), iCol(i, 0), 2);
            setSkyscraper(iRow(i, 1), iCol(i, 1), 1);
          }
          break;
        case 3:
          cleanHint(i, 0, SIZE);
          cleanHint(i, 1, SIZE);
          cleanHint(i, 0, SIZE - 1);
          if(getSkyscraper(i, SIZE - 1) == SIZE && getSkyscraper(i, SIZE - 2) == SIZE - 1) {
            setSkyscraper(iRow(i, 0), iCol(i, 0), 2);
            setSkyscraper(iRow(i, 1), iCol(i, 1), 1);
          } else if (getSkyscraper(i, SIZE - 1) == SIZE - 1 && getSkyscraper(i, SIZE - 2) == SIZE) {
            setSkyscraper(iRow(i, 0), iCol(i, 0), 1);
            setSkyscraper(iRow(i, 1), iCol(i, 1), 2);
          } else if (getSkyscraper(i, SIZE - 2) == SIZE && getSkyscraper(i, 0) == 2) {
            setSkyscraper(iRow(i, 1), iCol(i, 1), 3);
          }
          break;
        case SIZE:
          for(int j = 0; j < SIZE; j++) {
            setSkyscraper(iRow(i, j), iCol(i, j), j + 1);
          }
          break;
    }
  }
  
  static void generateEmptySquare() {
    square3d = new int[SIZE][SIZE][SIZE+1];
    for(int r = 0; r < SIZE; r++) {
      for(int c = 0; c < SIZE; c++) {
        for(int d = 0; d < SIZE + 1; d++) {
          square3d[r][c][d] = d;
        }
      }
    }
    count = 0;
  }
  
  static void checkSquareForOneHint() {
    for(int i = 0; i < SIZE; i++) {
      for(int j = 0; j < SIZE; j++) {
        checkIsOnlyOneHintAndSetIfYes(i, j);
      }
    }
  }
  
  static void checkLineForOneHint(int i) {
    for(int h = 1; h <= SIZE; h++) {
      int pos = 0;
      int count = 0;
      for(int j = 0; j < SIZE; j++) {
        if(square3d[iRow(i, j)][iCol(i, j)][h] > 0) {
          count++;
          pos = j;
        }
      }
      if(count == 1) {
        setSkyscraper(iRow(i, pos), iCol(i, pos), h);
      }
    }
  }
  
  static boolean checkIsOnlyOneHintAndSetIfYes(int row, int col) {
    if(square3d[row][col][0] > 0) {
      return true;
    }
    int num = 0;
    int count = 0;
    for(int dig = 1; dig <= SIZE; dig++) {
      if(square3d[row][col][dig] > 0) {
        count++;
        num = dig;
      }
    }
    if(count == 1) {
      setSkyscraper(row, col, num);
      return true;
    }
    return false;
  }
  
  static void setSkyscraper(int row, int col, int value) {
    if(square3d[row][col][0] == 0) {
      square3d[row][col][0] = value;
      for(int h = 0; h < SIZE; h++) {
        square3d[row][col][h+1] = 0;
        square3d[row][h][value] = 0;
        square3d[h][col][value] = 0;
      }
      count++;
    }
  }
  
  static int getSkyscraper(int i, int j) {
    return square3d[iRow(i, j)][iCol(i, j)][0];
  }

  static int iRow(int i, int j) {
    return row + direction[((i / SIZE) + 1) % SIZE][0] * j;
  }

  static int iCol(int i, int j) {
    return col + direction[((i / SIZE) + 1) % SIZE][1] * j;
  }

  
  static int howManySee(int i) {
    int max = 0;
    int count = 0;
    for(int j = 0; j < SIZE; j++) {
      if(square3d[iRow(i, j)][iCol(i, j)][0] > max) {
        max = square3d[iRow(i, j)][iCol(i, j)][0];
        count++;
      }
    }
    return count;
  }
  
  static void cleanAllHintsInLine(int i) {
    for(int j=0; j < SIZE; j++) {
      int v = getSkyscraper(i, j);
      if(v > 0) {
        cleanHintLine(i, v);
      }
    }
  }

  static void cleanHintLine(int i, int hint) {
    for(int j = 0; j < SIZE; j++) {
      cleanHint(i, j, hint);
    }
  }
  
  static void cleanHint(int i, int j, int hint) {
      square3d[iRow(i, j)][iCol(i, j)][hint] = 0;
  }

}

Test cases to validate our solution

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;

public class SolutionTest {

    private static int clues[][] = {
    { 2, 2, 1, 3,  
      2, 2, 3, 1,  
      1, 2, 2, 3,  
      3, 2, 1, 3 },
    { 0, 0, 1, 2,   
      0, 2, 0, 0,   
      0, 3, 0, 0, 
      0, 1, 0, 0 }
    };

    private static int outcomes[][][] = {
    { { 1, 3, 4, 2 },       
      { 4, 2, 1, 3 },       
      { 3, 4, 2, 1 },
      { 2, 1, 3, 4 } },
    { { 2, 1, 4, 3 }, 
      { 3, 4, 1, 2 }, 
      { 4, 2, 3, 1 }, 
      { 1, 3, 2, 4 } }
    };
 
    @Test
    public void testSolvePuzzle1 () {
        assertEquals (SkyScrapers.solvePuzzle (clues[0]), outcomes[0]);
    }

    @Test
    public void testSolvePuzzle2 () {
        assertEquals (SkyScrapers.solvePuzzle (clues[1]), outcomes[1]);
    }
}