-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?

Improve this question
$\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, 2021 at 16:16
  • $\begingroup$ You are right I copied that field wrong from my solver. I fixed it. $\endgroup$
    – Sandro4912
    Mar 31, 2021 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, 2021 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, 2021 at 20:03

1 Answer 1

Reset to default
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).

Improve this answer
$\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, 2021 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, 2021 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, 2021 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, 2021 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, 2021 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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