wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Battleships
        
(Message started by: mattian on Dec 2^nd, 2005, 12:44pm)

Title: Battleships
Post by mattian on Dec 2^nd, 2005, 12:44pm

Consider a battleships board - 10x10 grid with rows and columns marked by letters and numbers respectively such that A1 is diagonally across the board from J10.

A battleship spanning five blocks in any direction (horizontally, vertically or diagonally) is placed somewhere on the board.

Establish an optimum strategy which will lead to the first successful strike. In other words, minimise the number of misses on the field before the first hit on the ship.

Now consider that the ship has been placed in the worst possible position given your strategy - in other words, assume your opponent knew your strategy and chose the position of the ship in order to maximise the number of attempts before the first hit.

How many misses would your strategy yield?

Title: Re: Battleships
Post by JocK on Dec 2^nd, 2005, 1:13pm

To minimise the maximum number of misses, I would simply place the first [hide]20 shots on the main diagonal and the two parallel half diagonals (i.e. from A1 till J10, from A6 till E10, and from F1 till J5.[/hide] many other configurations are possible, but this one is simplest to describe.

Maximum number of misses is [hide]20[/hide].

This problem is in 'hard', so I guess there must be a better strategy that utilises the fact that this board is of finite size? (The above strategy leading to [hide]20% [/hide]of the gridpoints to be aimed at, works for boards of any size.)

[edit]Ooops... I see: a special variant of battleships.. (I overlooked the word 'diagonal'... ) [/edit]

Title: Re: Battleships
Post by mattian on Dec 2^nd, 2005, 1:23pm

No - the ship may be positioned DIAGONALLY as well.

And I don't know that this problem is necessarily hard... but I am not convinced that I have the optimum solution, so it's hard for slow guys like ME! :-)

Title: Re: Battleships
Post by JocK on Dec 2^nd, 2005, 1:27pm

In that case we are playing Go-moku...

I'd simply place my shots according to a grid of [hide]'knight moves'[/hide]...

Number of misses < [hide]20[/hide]...

Title: Re: Battleships
Post by SMQ on Dec 2^nd, 2005, 1:47pm

An observation: since we are looking for the minimal worst case firing order doesn't matter, we just need to find a minimal grid of points which covers all 192 possible ship positions (60 vertical, 60 horizontal, and 36 each diagonal).

Title: Re: Battleships
Post by mattian on Dec 2^nd, 2005, 1:57pm

Right! With as much reuse as possible.

Title: Re: Battleships
Post by rmsgrey on Dec 3^rd, 2005, 7:19am

I would go for [hide]take out rows 3 and 8 and columns C and H[/hide]. Worst case [hide]36[/hide]

Not sure about the optimal order of shots to get that pattern, but the pattern would leave the ship with nowhere left to hide...

Title: Re: Battleships
Post by JocK on Dec 3^rd, 2005, 7:29am

on 12/02/05 at 13:57:19, mattian wrote:

Right! With as much reuse as possible.

What do you mean by 'reuse'?

Can you do better than a worst case of [hide]19[/hide]..? I have reasons to believe that the above [hide]regular grid[/hide] solution leading to a maximum of [hide]19[/hide] misses is optimal, but cant prove it.
Interestingly, for arbitary large grids, whether ships can only be placed in horizontal orientation, or both in horizontal and vertical fashion, or even horizontal, vertical and diagonal (the current problem), doesn't matter for the minimum shot density that is guarenteed to lead to a hit. In all cases it is [hide]1/5[/hide].

Title: Re: Battleships
Post by Grimbal on Dec 3^rd, 2005, 1:08pm

You can place 20 ships simultaneously on the grid. However cleverly you shoot, after 19 shots, one ship will remain.

Title: Re: Battleships
Post by JocK on Dec 3^rd, 2005, 1:33pm

on 12/03/05 at 13:08:17, Grimbal wrote:

You can place 20 ships simultaneously on the grid. However cleverly you shoot, after 19 shots, one ship will remain.

Indeed.

So the riddle was solved within an hour after posting. I wondered wether I missed something. Everyone kept on posting...

Title: Re: Battleships
Post by rmsgrey on Dec 4^th, 2005, 4:31am

on 12/03/05 at 13:33:33, JocK wrote:

Indeed.

So the riddle was solved within an hour after posting. I wondered wether I missed something. Everyone kept on posting...

In my case, it's because I misread your stated bound for some reason...

Oh well.