Skyscrapers Quest

The Game

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.

Example

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

Applet Instructions

* 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

Applet Notes

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.

Quest solver

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!