-1
$\begingroup$

I have the following Skyscrapers puzzle:

C3 C1 C2 C3 C4 C4 C2
C2 V3 C5
C4 V1 C1
C3 C4
C2 V5 C3
C3 V7 C3
C3 V4 V2 C2
C1 V2 C2
C1 C3 C4 C2 C2 C2 C2

C -> Clues how many skyscrapers are visible V -> Skyscrapers numbers without prefix -> Nopes. Which means these Skyscrapers are not possible on the field.

Now I have a program which normally solves these boards by generating the permutations of the skyscrapers per row. Somehow it cannot solve the board completely.

I'm stuck on this step:

C3 C1 C2 C3 C4 C4 C2
C2 V5 V7 V6 2,3,5,6,7 3,5,6,7 V3 3,4,5,6,7 C5
C4 1,4,5,6,7 V1 1,2,3,6,7 V6 1,6,7 1,3,4,6,7 V7 C1
C3 4,5,6,7 1,6,7 V7 2,5,6,7 V6 1,3,6,7 5,6,7 C4
C2 V6 1,4,5,6,7 2,3,5,6,7 V5 V7 1,3,5,6,7 4,5,6,7 C3
C3 4,5,6,7 1,3,4,6,7 2,6,7 V7 5,6,7 V6 5,6,7 C3
C3 V4 V6 2,4,5,6,7 V2 2,4,5,6,7 V7 V5 C2
C1 V7 1,2,6,7 V2 1,2,5,6,7 1,2,6,7 V1 V6 C2
C1 C3 C4 C2 C2 C2 C2

My question is: How can you get the next Skyscraper on the field?

$\endgroup$
4
  • 1
    $\begingroup$ I think there must be something wrong in the partially filled grid. Why does R4C6 not have a 3 nope in it, given that R1C6 is a 3? $\endgroup$ – Jaap Scherphuis Mar 31 at 16:16
  • $\begingroup$ You are right I copied that field wrong from my solver. I fixed it. $\endgroup$ – Sandro4912 Mar 31 at 16:18
  • 4
    $\begingroup$ This is extremely hard to read. Mixing positive (Vx) notation with negative notation ("nopes") is an unnecessary hardship you impose on yourself, which is why most people use the pencil marks to denote positive information only. ("These are the values that could go to this square" and "this value must live in one of these squares" are the common things to pencil mark.) $\endgroup$ – Bass Mar 31 at 16:49
  • $\begingroup$ The reason I displayed with nopes is because it was easier to program it that way. I should probaly change it to the possible skyscrapers here like you said for the humans. $\endgroup$ – Sandro4912 Mar 31 at 20:03
0
$\begingroup$

I confirmed via constraint programming that the following solution is unique:

 5 7 6 4 2 3 1
 3 1 5 6 4 2 7
 2 3 7 1 6 5 4
 6 2 1 5 7 4 3
 1 5 4 7 3 6 2
 4 6 3 2 1 7 5
 7 4 2 3 5 1 6
 

You have narrowed the (6,5) entry to two choices: 1 or 3. The unique solution has a 1, so choose 3 instead. You will quickly get a contradiction, which therefore implies that (6,5) must instead be 1.

Alternatively, suppose the (4,6) entry is 2 (rather than 4). Then (2,6) must be 5 because you have already used 2 in column 6. Then (2,3) must be 4 because you have already used 5 in row 2. Then (4,3) must be 1 because you have already used 4 in column 3. Now row 4 has no place to put 4. This contradiction enables you to conclude that (4,6) must instead be 4 (rather than 2).

$\endgroup$
5
  • $\begingroup$ Agreed, but it verifies that there is a unique solution, which was not true of the original question. It also might help the OP debug the solver. $\endgroup$ – RobPratt Mar 31 at 17:37
  • $\begingroup$ I already know the solution but I really need to know how to deduce the next step. $\endgroup$ – Sandro4912 Mar 31 at 18:29
  • $\begingroup$ Interesting so tge approach you use is insert one number out of tge two and then try out if it works for the next numbers $\endgroup$ – Sandro4912 Apr 1 at 5:51
  • $\begingroup$ Yes, this is look-ahead or probing. Temporarily fix the value of a variable and examine the implications. $\endgroup$ – RobPratt Apr 1 at 13:47
  • $\begingroup$ That explains why my program could not solve it. This is a case were generating all permutations per row does not work. With this backtracking approach my program could solve it. $\endgroup$ – Sandro4912 Apr 7 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.