19
$\begingroup$

An entry in Fortnightly Topic Challenge #32: Grid Deduction Hybrids

You are a knight in the king's army, and you've been tasked with constructing some walls. The problem is, as a knight, you are confined in your movement abilities. But, when the king orders you to do something, you'll have to figure out a way to do it.

Rules (essentially a Kuromasu filled in using a knight chess piece):

  • Move around the grid using a knight chess piece (starting wherever you wish)
  • Spaces you land on become a "wall" (black square)
  • You may not re-visit spaces you've already landed on
  • Cells with numbers are indicate how many cells can be "seen" from that spot (including itself)
  • "Seen" cells are ones in the same row/column up to the first wall
  • Numbered cells cannot be walls (so you cannot land on them)
  • Walls cannot be side-by-side (diagonal is acceptable)
  • All white cells must be connected horizontally or vertically

Kuromasu

Attempted text version: 

+---+---+---+---+---+---+---+---+---+---+---+---+
| 11|   |   |   |   |   |   |   |   | 6 |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   | 3 |   |   | 6 |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   | 10|   |   | 15|   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   | 9 |   |   |   |   |   |   | 12|   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   | 8 |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   | 11|   |   |   | 12|   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | 10|   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   | 17| 13|
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   | 9 |   | 9 |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   | 7 |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | 11|   |   |   | 11|   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   | 4 |   |   |   |   |   |   |   | 7 |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ Heh. I play a game called '0h h1' which is essentially this without the knight moves $\endgroup$
    – Beastly Gerbil
    Jun 20, 2017 at 14:50
  • $\begingroup$ @BeastlyGerbil You mean this game? $\endgroup$
    – Rand al'Thor
    Jun 20, 2017 at 16:42
  • $\begingroup$ @Randal'Thor ya. Great game. $\endgroup$
    – Beastly Gerbil
    Jun 20, 2017 at 20:24
  • $\begingroup$ Does a numbered cell see itself? $\endgroup$
    – greenturtle3141
    Jun 21, 2017 at 7:08
  • 1
    $\begingroup$ I've come to the conclusion that my brute force solution has time-complexity O(too-much). It's the dumbest possible brute force, test every legal path starting from every board position, what is the time complexity? O(n^n)? (haven't had the patience to sit through first start position) $\endgroup$
    – Adam
    Jun 21, 2017 at 20:18

1 Answer 1

Reset to default
9
$\begingroup$

Coded b1 as initial position, bn as position before n'th jump

+---+---+---+---+---+---+---+---+---+---+---+---+
| 11| w | w | w |b23| w | w | w | b1| 6 | w | w |
+---+---+---+---+---+---+---+---+---+---+---+---+
| w | w |b24| 3 | w |b21| 6 | w | w | w | b2| w |
+---+---+---+---+---+---+---+---+---+---+---+---+
| w | w | w |b22| 10| w | w | 15| w | w | w | w |
+---+---+---+---+---+---+---+---+---+---+---+---+
| w |b25| w | 9 | w | w |b20| w | w | w | 12| b3|
+---+---+---+---+---+---+---+---+---+---+---+---+
| w | w | w | w |b19| w | w | w | 8 | b4| w | w |
+---+---+---+---+---+---+---+---+---+---+---+---+
| w | 11| w | w | w | 12|b18| w | w | w | w | w |
+---+---+---+---+---+---+---+---+---+---+---+---+
| w | w | w | w |b17| w | w | 10| b5| w | w | w |
+---+---+---+---+---+---+---+---+---+---+---+---+
| w | w |b16| w | w | w | w | w | w | w | 17| 13|
+---+---+---+---+---+---+---+---+---+---+---+---+
|b15| w | 9 | w | 9 | w | w |b10| w | b6| w | w |
+---+---+---+---+---+---+---+---+---+---+---+---+
| w | w | w |b13| w |b11| w | w | 7 | w | w | b7|
+---+---+---+---+---+---+---+---+---+---+---+---+
| w |b14| w | w | w | w | 11| w | b9| w | 11| w |
+---+---+---+---+---+---+---+---+---+---+---+---+
| w | 4 | w | w |b12| w | w | w | w | 7 | b8| w |
+---+---+---+---+---+---+---+---+---+---+---+---+

As for methodology, I started by deducing the following:

+---+---+---+---+---+---+---+---+---+---+---+---+
| 11|   |   |   |   |   |   |   |   | 6 |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
| w |   |   | 3 |   |   | 6 |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
| w |   | w | b | 10|   | w | 15| w | w |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
| w |   |   | 9 |   |   |   | w |   |   | 12|   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | w | 8 |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   | 11|   |   |   | 12|   | w |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | 10|   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   | w | w | w | w | w | 17| 13|
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   | 9 |   | 9 |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   | 7 |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | 11|   |   |   | 11|   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   | 4 |   |   |   |   |   |   |   | 7 |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+

From there it seemed as if there were three points of high tension,

The top left 3, the bottom left 4, and the top right pair of sixes. I tried connecting the top left and top right a few different ways with trial and error, and came to the conclusion it was impossible.

From this conclusion I started working on solving the 6-area at the top right, because I had to work around a fair amount of filled squares, knowing I needed to head down rather than left.

Knowing there was an 'end' in the top right quadrant let me build a skeleton of knight moves out of that area, over to the 4, up around the pair of 9s, and almost connect back to the 3. I don't remember exactly the moves here, but I believe my chart looked something like this: (g being 'pencil' b) 

+---+---+---+---+---+---+---+---+---+---+---+---+
| 11|   |   |   | g |   |   |   | g | 6 |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
| w |   | g | 3 |   | g | 6 |   |   |   | g |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
| w |   | w | b | 10|   | w | 15| w | w |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
| w | g |   | 9 |   |   | g | w |   |   | 12| g |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   | g |   |   | w | 8 | g |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   | 11|   |   |   | 12|   | w |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   | g |   |   | 10| g |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   | g |   |   | w | w | w | w | w | 17| 13|
+---+---+---+---+---+---+---+---+---+---+---+---+
| g |   | 9 |   | 9 |   |   | g |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   | g |   | g |   |   | 7 |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   | g |   |   |   |   | 11|   |   |   | 11|   |
+---+---+---+---+---+---+---+---+---+---+---+---+
|   | 4 |   |   | g |   |   |   |   | 7 |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+

Doing some counting, I was clearly missing something in the bottom right, fortunately I saw a cycle which could be safely added.

+---+---+---+---+---+
| g |   | g |   |   |
+---+---+---+---+---+
|   | 7 |   |   | g |
+---+---+---+---+---+
|   | g |   | 11|   |
+---+---+---+---+---+
|   |   | 7 | g |   |
+---+---+---+---+---+

A little more counting let me verify that these were basically right, shade them to black and white, and put the last one to the right of the central 12 to link the top and bottom halves of the left side leading to the graph at the top of this post.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What was your methodology? Brute? $\endgroup$
    – Forklift
    Jun 22, 2017 at 18:04
  • $\begingroup$ @Forklift added some of my methodology $\endgroup$
    – Sconibulus
    Jun 22, 2017 at 18:50

Your Answer

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

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