algorithm - Variation of n-queens -

you given nxm matrix. have k battle ships. given 3 parameters each of battle ship - rowattack, columnattack , diagonalattack. each telling how many cells in row/column/diagonal(on each direction) ship can attack. task find whether ships can placed in board such no 1 attacks each other.

to shed more light on attacks, if ship placed @ (5,5) , if it's column attack range 3, can attack ship (5,2) (5,8).

if no such combination possible, return false. sample java class...

class battleship {      public final int rowattack;      public final int columnattack;      public final int diagonalattack; } 

and need code

boolean ispossible(int m, int n, battleship battleships[]) 

where m number of rows in board, n number of columns in board , battleships.length k , k irrelevant both m , n. (so 1 obvious checks check if k >= m x n).

i couldn't think of solution other examining every possibility go upto o(m x n x k!)

it's not explicit in description, since diagonalattack parameter specified separately rowattack , columnattack parameters, seems ship's "attack zone" shaped asterisk or star, rather solid rectangle. in case, tight packing placing ships @ offset of (2, 1) (or (1, 2)) each other: e.g. first @ (0, 0), @ (2, 1), @ (4, 2), , on. (nonzero vertical , horizontal offsets between ships guarantee no ships can hit horizontal or vertical attacks, respectively; , fact x , y offsets differ guarantees diagonal attack zones never hit ships either.)

once reach (right or top) edge of board need start again @ (left or bottom) edge. things become more complicated now, since must take care not let new ships hit or hit existing ships below them (in case of hitting right edge). can proceed same x positions before, adjust each ship's y position upwards enough avoid hitting or being hit ship below it; alternatively, may able tighter packing using same x positions before offsetting them 1, eliminate possibility of hits in vertical attack zones.

this heuristic: if fails pack ships onto board, doesn't mean cannot packed. should find answer quickly, , if want develop exact method uses backtracking (e.g. best-first search), think "number of ships placed after running heuristic" serve useful way of ordering partial solutions.