I wrote this program and got 13,858,992. I have not tested the program so it might be buggy; you can manually check some cases with smaller numbers of ships and smaller grids if you want.
Edit: This mistakenly assumes there is a single 2x3 ship instead of two 1x3 ships. So this would have to be changed in the ship definition. Also, do you consider the two 1x3 ships distinguishable?
def genpoints(x, y, w, h):
for dx in range(w):
for dy in range(h):
yield x + dx, y + dy
def f(points, ships, width, height):
if not ships:
return 1
total = 0
for w, h in (ships[0], reversed(ships[0])):
for x in range(width - (w-1)):
for y in range(height - (h-1)):
p = set(genpoints(x, y, w, h))
if not (points & p):
total += f(points | p, ships[1:], width, height)
return total
def main():
points = set()
ships = [(1, 5), (1, 4), (2, 3), (1, 2)]
print f(points, ships, 8, 8)
main()