0

Here is my problem :

Let's say we have a two dimensionnal array of $n \times n$ squares. In this array there are m targets and the player knows this value. Each turn you can shoot a square,

  • if there is a target the target disappears and you get informed that you "killed" a target ;

  • if there is no target where you shot you are being informed of the number of targets in diagonals, row and column in every direction.

You win if every target has been shot down.

I need to make the most efficient algorithm to this problem but I can't find where to look at or where to start, can you help me ?

Ps : I am french so excuse my poor language.

Jean Marie
  • 81,803
Luca Antoine
  • 1
  • I would suggest starting with an attempt to find an algorithm for a $3\times 3$ grid. It is sufficiently difficult to not be trivial, but not so bad as to be overwhelming. Then, can you take your work and extrapolate to a $4\times 4$ grid. If so, then can you expand the grid indefinitely. – user317176 Mar 11 '20 at 22:27
  • yes that seems like a good start, thanks – Luca Antoine Mar 11 '20 at 22:29
  • If you shoot a target, do you know that you shot it? – Jack M Mar 11 '20 at 22:33
  • 1
    Yes you know it, I forget to specify it, I'll edit the post – Luca Antoine Mar 11 '20 at 22:38
  • Do you know the targets locations separately? For example would you get that there are 2 horizontal, 3 vertical, and 2 diagonally, or would you just receive that there are 7 targets together in that range? – wjmccann Mar 11 '20 at 22:42
  • You just receive that there are 7 targets wjmccann – Luca Antoine Mar 11 '20 at 22:52
  • Thanks cher Jean Marie, it's better indeed :) – Luca Antoine Mar 11 '20 at 22:52
  • 2
    Isn't this the minesweeper game? – Deepak Mar 11 '20 at 22:57
  • 1
    @Deepak: It is minesweeper but you don't lose if you hit a mine. Our criterion is now minimum number of shots to find all the targets. – Ross Millikan Mar 12 '20 at 04:24
  • @Deepak No, as Ross said the first difference is that you need to touch the "mines" and the second one is that when you "touch" a square you don't know how many mines there is in the blocks around you, you get to know how many mines there is in every direction ( the directions are similar to the moves allowed to the queen in chess so it goes til the edge of the "board") – Luca Antoine Mar 12 '20 at 09:24
  • @LucaAntoine (and Ross), thanks for clarifying. – Deepak Mar 12 '20 at 13:52

0 Answers0