8
$\begingroup$

Sherlock is solving a case where he came across a puzzle. Suppose you are given a square matrix of size $N$, and a gun with Power $F$. Every cell in the matrix is filled with some number, $x$ (thickness or toughness of the cell), such that $1 < x < F$. Not every cell will contain the same value of $x$

Sherlock can shoot the matrix from UP, DOWN, LEFT, or RIGHT to destroy cells. Each shot destroys cells in a line, until the sum thickness of the cells is $>F$, and each cell must be destroyed outright, in a single shot.

Here is the catch! He has to destroy the matrix in strictly less than $M$ shots! Here $M = min(A, B)$, where $A$ is the number of shots required to destroy the matrix by using only horizontal (LEFT or RIGHT) shots, and $B$ is the number of shots required to destroy the matrix by using only vertical (UP and DOWN) shots.

What is the optimal strategy for Sherlock to take to destroy the matrix in $O<M$ shots?


Example: $N=3$, $F=5$

[2][2][2]
[2][3][2]
[2][2][2]

$A=6$, $B=6$, $M=6$

►[X][X][2]   [ ][ ][2]   [ ][ ][2]
 [2][3][2]  ►[X][X][2]   [ ][ ][2]
 [2][2][2]   [2][2][2]  ►[X][X][2]


►[ ][ ][X]   [ ][ ][ ]   [ ][ ][ ]
 [ ][ ][2]  ►[ ][ ][X]   [ ][ ][ ]
 [ ][ ][2]   [ ][ ][2]  ►[ ][ ][X]

$O=5$

                    ▼              
►[X][X][2]   [ ][ ][X]   [ ][ ][ ] 
 [2][3][2]   [2][3][X]   [2][3][ ] 
 [2][2][2]   [2][2][2]   [2][X][X]◄

                 ▼       
 [ ][ ][ ]   [ ][ ][ ]   
 [X][3][ ]  ►[ ][X][ ]◄  
 [X][ ][ ]   [ ][ ][ ]   
  ▲              ▲      

NOTE: All the values of cells will never be >F/2 and the sum entries in each row or column >=F. O is guaranteed to exist.

$\endgroup$
  • 1
    $\begingroup$ The puzzle is about an arbitrary matrix but you say "you need to show ... the moves". Are you looking for a description of how to determine those moves, given the matrix? $\endgroup$ – Gareth McCaughan May 6 at 10:34
  • 3
    $\begingroup$ It doesn't seem like O is guaranteed to exist. For example, if the sum of entries in each row is < F then I think the best we can do is A. $\endgroup$ – hexomino May 6 at 12:44
  • 2
    $\begingroup$ Similarly, if all the cells have values $>F/2$, then every shot always clears exactly 1 cell and $M=A=B=n^2$, and there is no way to get $O<M$. $\endgroup$ – Jaap Scherphuis May 6 at 12:57
  • 1
    $\begingroup$ @Chronocidal thanks for editing the question with an example to it $\endgroup$ – puzzledose May 6 at 13:32
  • 2
    $\begingroup$ I upvoted the puzzle because the idea is fun, but hexomino and Jaap Scherphuis definitely both have a point that needs to be addressed before one can make anything from this. $\endgroup$ – Arnaud Mortier May 6 at 20:24
4
$\begingroup$

This appears to be a variation on a Bin-Packing or Guillotine problem...

I am going to start with a fairly naïve algorithm, which is far from optimal - but hopefully gives other people something to build from.

For every Row and Column, write down how many cells will be destroyed by shooting it from either end, and What they sum to.

Start with the shot which destroys the highest number of cells.

- In case of a draw, choose the shot with the highest Sum destroyed

  - If this is also a draw, start with the clockwise-most shot on the side of the matrix clockwise from the last shot taken, and move counter-clockwise until you reach a drawing shot

    (If no shot has yet been taken, start at the top-left horizontal shot)

Repeat until all cells have been destroyed

Reasoning:

To Minimise $O$, we need to destroy as many cells as we can with each shot. We also want to try to minimise "unused" power from each shot

How I know this is not an optimal solution:

Sometimes, and optimal solution many require destroying a short line to open up a long liner:
Example, $F=5$
Algorithm, 13 shots
. ▼ .
[4][4][2][1] [4][4][2][X] [4][4][2][ ] [4][4][2][ ] [4][4][2][ ]
[4][4][1][4] [4][4][1][X] [4][4][1][ ] [4][X][X][ ] [4][ ][ ][ ]
[4][4][4][2] [4][4][4][2] [4][4][4][X] [4][4][4][ ] [4][4][4][ ]
[4][4][2][2] [4][4][2][2] [4][4][2][X] [4][4][2][ ] [4][4][2][ ]
. ▲ .
3 shots taken. Remaining 10 cells require 1 shot each

No Algorithm, 12 shots:
. .
[4][4][2][1] [4][4][2][1] [4][4][2][X] [4][4][2][ ] [4][4][X][ ]
[4][4][1][4] [4][4][X][X]◄ [4][4][ ][ ] [4][X][ ][ ] [4][4][ ][ ]
[4][4][4][2] [4][4][4][2] [4][4][4][X] [4][4][X][ ]◄ [4][4][ ][ ]
[4][4][2][2] [4][4][2][2] [4][4][2][X] [4][4][2][ ] [4][4][X][ ]
. ▲ ▲ .
[4][4][ ][ ]
[4][4][ ][ ]
[4][4][ ][ ]
[4][4][ ][ ] 4 shots taken, remaining 8 cells require 1 shot each

| improve this answer | |
$\endgroup$

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