CODEWITHSUNDEEP
algorithmbacktrackingbrute-force
Mohan
Mohan

Reputation: 1955

Variation of n-queens

You are given NxM matrix. You have K battle ships. You are also given 3 parameters for each of the battle ship - rowAttack, columnAttack and diagonalAttack. Each telling how many cells in a row/column/diagonal(on each direction) the ship can attack. Your task is find whether the ships can be placed in the board such that no one attacks each other.

To shed more light on the attacks, say if the ship is placed at (5,5) and if it's column attack range is 3, then it can attack any ship from (5,2) to (5,8).

If no such combination possible, return false. A sample java class...

class BattleShip
{
     public final int rowAttack;
     public final int columnAttack;
     public final int diagonalAttack;
}

And you need to code

boolean isPossible(int m, int n, BattleShip battleShips[])

where m is the number of rows in the board, n is the number of columns in the board and the battleShips.length is k and k is irrelevant to both m and n. (So one obvious checks would be to check if k >= m x n).

I couldn't think of any solution other than examining every possibility which could go upto O(m x n x k!)

Upvotes: 3

Views: 741

Answers (2)

j_random_hacker
j_random_hacker

Reputation: 51226

It's not explicit in the description, but since a diagonalAttack parameter is specified separately from the rowAttack and columnAttack parameters, it seems that a ship's "attack zone" is shaped like an asterisk or star, rather than a solid rectangle. In that case, you will get a very tight packing by placing ships at an offset of (2, 1) (or (1, 2)) from each other: e.g. the first at (0, 0), another at (2, 1), another at (4, 2), and so on. (Nonzero vertical and horizontal offsets between ships guarantee that no ships can be hit by horizontal or vertical attacks, respectively; and the fact that the x and y offsets differ guarantees that diagonal attack zones will never hit ships either.)

Once you reach the (right or top) edge of the board you will need to start again at the (left or bottom) edge. Things become slightly more complicated now, since you must take care not to let the new ships hit or be hit by the existing ships below them (in the case of hitting the right edge). You can proceed with the same x positions as before, but adjust each ship's y position upwards just enough to avoid hitting or being hit by any ship below it; alternatively, you may be able to get a tighter packing by using the same x positions as before but offsetting them by 1, to eliminate the possibility of hits in the vertical attack zones.

This is just a heuristic: if it fails to pack all the ships onto the board, it doesn't necessarily mean that they cannot be packed. But it should often find an answer quickly, and if you want to develop an exact method that uses backtracking (e.g. best-first search), then I think that "number of ships successfully placed after running this heuristic" would serve as a useful way of ordering partial solutions.

Upvotes: 1

user2566092
user2566092

Reputation: 4661

This isn't a guaranteed polynomial time solution but in practice it can be much faster than brute force: For every square on the board and every battleship index, have a 0/1 integer variable that indicates whether the battleship is in the square. Then you can have linear constraints that say that every battleship is placed on the board in exactly one spot, and that every battleship is placed on the board, and that for a given square and battleship you cannot have any battleships within the "firing distances" of that battleship in any direction. This gives you O(mnk) constraints in O(mnk) variables, so polynomial problem description complexity. Then you can feed your problem into a 0/1 integer programming solver to see if there's a solution. There has been a lot of research into 0/1 integer programming solvers and a lot of optimizations in software that have been made, so this will probably work faster than brute force in practice. By the way, I'm not sure how you got your quoted bound for brute force...the bound I get for brute force is much worse, namely O((mn)^k).

Upvotes: 1

Related Questions