You can offer. Nothing about it being NP should prevent your implementing an exact solution, though. It'll be slow as balls on (at least) some inputs, and you should surface that, but maybe they only need something that works for N<5 or something.
That's different than it being undecidable, in which case you have to insist on providing something other than an exact algorithm that handles every input.
