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:
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]);
}
}