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:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
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:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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]);
    }
}