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:
public static int[][] solvePuzzle (int[] clues)
Code language: Java (java)
  • 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; } } }
Code language: Java (java)

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; } }
Code language: Java (java)

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]); } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments