Author |
Topic: Battleships (Read 1174 times) |
|
mattian
Senior Riddler
 
Gender: 
Posts: 404
|
 |
Battleships
« on: Dec 2nd, 2005, 12:44pm » |
 Quote  Modify
|
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?
|
| « Last Edit: Dec 2nd, 2005, 12:45pm by mattian » |
 IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Battleships
« Reply #1 on: Dec 2nd, 2005, 1:13pm » |
Quote Modify
|
To minimise the maximum number of misses, I would simply place the first 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. many other configurations are possible, but this one is simplest to describe.
Maximum number of misses is 20.
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 20% 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]
|
| « Last Edit: Dec 2nd, 2005, 1:23pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: Battleships
« Reply #2 on: Dec 2nd, 2005, 1:23pm » |
Quote Modify
|
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! 
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Battleships
« Reply #3 on: Dec 2nd, 2005, 1:27pm » |
Quote Modify
|
In that case we are playing Go-moku...
I'd simply place my shots according to a grid of 'knight moves'...
Number of misses < 20...
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Battleships
« Reply #4 on: Dec 2nd, 2005, 1:47pm » |
Quote Modify
|
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).
|
|
IP Logged |
--SMQ
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: Battleships
« Reply #5 on: Dec 2nd, 2005, 1:57pm » |
Quote Modify
|
Right! With as much reuse as possible.
|
| « Last Edit: Dec 2nd, 2005, 1:57pm by mattian » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Battleships
« Reply #6 on: Dec 3rd, 2005, 7:19am » |
Quote Modify
|
I would go for take out rows 3 and 8 and columns C and H. Worst case 36
Not sure about the optimal order of shots to get that pattern, but the pattern would leave the ship with nowhere left to hide...
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Battleships
« Reply #7 on: Dec 3rd, 2005, 7:29am » |
Quote Modify
|
on Dec 2nd, 2005, 1:57pm, mattian wrote:| Right! With as much reuse as possible. |
|
What do you mean by 'reuse'?
Can you do better than a worst case of 19..? I have reasons to believe that the above regular grid solution leading to a maximum of 19 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 1/5.
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Battleships
« Reply #8 on: Dec 3rd, 2005, 1:08pm » |
Quote Modify
|
You can place 20 ships simultaneously on the grid. However cleverly you shoot, after 19 shots, one ship will remain.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Battleships
« Reply #9 on: Dec 3rd, 2005, 1:33pm » |
Quote Modify
|
on Dec 3rd, 2005, 1:08pm, 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...
|
| « Last Edit: Dec 3rd, 2005, 1:34pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Battleships
« Reply #10 on: Dec 4th, 2005, 4:31am » |
Quote Modify
|
on Dec 3rd, 2005, 1:33pm, 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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print