The
Game An
Example Applet
Instructions Applet
Notes Quest
Solver (Updated!)| Skyscrapers
Quest |
The
Game
An
Example
Applet
Instructions
Applet
Notes
Quest
Solver (Updated!)
Download
Applet (33kb,
for offline play)
Download
Source (130kb)
Skyscrapers (as
I call this game cause I don't know if it has a name and if yes what this name
is) is a logic-based number placement puzzle, similar to Sudoku. The
objective is to fill a NxN-grid so that each column and each row contains the
digits from 1 to N, only time each (that means exclusively). But as you see
there are also some numbers along the four edges of the grid - that's the special
thing. Each number in the grid represents a skyscraper and the height of one
skyscraper is exactly this number; where 1 stands for the lowest and N for the
highest skyscraper. So when filling the grid, you have in each row and in each
column N different high skyscrapers.
But what about the numbers along the edges? These numbers tell you how many
skyscrapers must be visible when you look into the corresponding column/row.
A skyscraper is only visible if all skyscrapers in front of it are lower.
Let's do a little example to make it more clearly :-) . I use a coordinate system for a better explanation.
1 |
2 |
3 |
4 |
5 |
6 |
|
A |
||||||
B |
3 |
|||||
C |
4 |
|||||
D |
||||||
E |
||||||
F |
3 |
Ok, let's start... In C6 is a 4 which means that we must see 4 skyscrapers when we "look" from C6 into row C. We have a 4x4-grid so 4 is the heighest skyscraper. In order to see 4 skyscrapers there is just on possibility to fill the row C (think about it):
1 |
2 |
3 |
4 |
5 |
6 |
|
A |
||||||
B |
3 |
|||||
C |
4 |
3 |
2 |
1 |
4 |
|
D |
||||||
E |
||||||
F |
3 |
View row B; Starting from B6 must be 3 skyscrapers visible. The 4 cannot be in B2 cause in C2 is the 4 already. It can also not be in B4 and B5 cause in this case we cannot find a solution where 3 are visible. So 4 must be in B3.
1 |
2 |
3 |
4 |
5 |
6 |
|
A |
||||||
B |
4 |
3 |
||||
C |
4 |
3 |
2 |
1 |
4 |
|
D |
||||||
E |
||||||
F |
3 |
Value in B4 must be bigger than value in B5 cause of the 4 visible skyscrapers starting from B6. B4=2, B5=1 and B4=3, B4=1 are not possible cause of the 1 in C5. So B4=3 and B5=2, and so B2=1.
1 |
2 |
3 |
4 |
5 |
6 |
|
A |
||||||
B |
1 |
4 |
3 |
2 |
3 |
|
C |
4 |
3 |
2 |
1 |
4 |
|
D |
||||||
E |
||||||
F |
3 |
That 3 skyscrapers are visible in Column 2 starting from F2, we have D2=3 and E2=1.
1 |
2 |
3 |
4 |
5 |
6 |
|
A |
||||||
B |
1 |
4 |
3 |
2 |
3 |
|
C |
4 |
3 |
2 |
1 |
4 |
|
D |
3 |
|||||
E |
2 |
|||||
F |
3 |
The other values can be filled in like a sudoku game, just with the knowledge that in each row and in each column each height can only be once. So we get the final solution and are finished:
1 |
2 |
3 |
4 |
5 |
6 |
|
A |
||||||
B |
1 |
4 |
3 |
2 |
3 |
|
C |
4 |
3 |
2 |
1 |
4 |
|
D |
3 |
2 |
1 |
4 |
||
E |
2 |
1 |
4 |
3 |
||
F |
3 |
*
Handling the applet should be straightforward (I hope!). The 'Load Quest' Button
opens a new frame where you can choose a quest. To fill the grid, just left-click
a spot to set a value. Several clicks toggle through all possible values. A
right-click clears the current spot. You can also type in the numbers with the
keyboard, the selected spot is highlighted with a red rectangle.
* The 'show Errors' option marks mistakes red in following
way: A given number of visible skyscrapers is marked red when less or more skyscrapers
are visible in the corresponding row/column. A number inside the grid is marked
red when the same value is found in the same row or column. So note that this
also means: a value is NOT marked if it DOES NOT violate the row/column/visible-skyscrapers
rules although it does not fit the unique solution. Hope this was a bit clear
:-)
* Following keys apply to the wireframe window (therefore it
must have the focus - click on it to make sure it has it):
A |
Rotate
the world left around the y-axis |
S |
Rotate
the world right around the y-axis |
Arrow
UP |
Move
the camera up |
Arrow
DOWN |
Move
the camera down |
Arrow
LEFT |
Move
the camera left |
Arrow
RIGHT |
Move
the camera right |
M |
Move
camera left |
N |
Move
camera right |
The applet comes
with 31 levels of size from 3x3 to 6x6. They should all be solvable with a unique
solution.
The quests were all generated with my self-coded generator. It's badly coded
and so slow that it takes very long to generate unique quests larger than 6x6.
Additionally it has quite some major bugs (e.g. returns unsolvable quests!)
so I won't release it.
I have also coded a solver! It prints all solutions to a given quest using a backtracking alogrithm but is a bit slow. Nevertheless I will publish it here (including sources of course) in a few weeks - perhaps I'm gonna improve it a bit this week, let's see.
Update October 5th 2k7: I finally improved my solver a bit but it's still quite slow. Nevertheless the source is not that ugly any more and I am not gonna change it, so here it is - have fun!
Download
the Solver (12kb)
I hope you have
fun with this and/or find my sources useful. If yes, feel free to leave some
comments in the guestbook.
Sunshine, October 2k7
This site is part of Sunshine's Homepage