Should I change my proposed solution for paper rejected because of lack of novelty or originality?
Lack of Novelty is an ill-defined statement. If you and your co-authors believe the manuscript has good contributions (compared to similar papers in the field) then probably the reviewers are just not expert in the area and thus thought of your work as marginal contribution. I would suggest addressing the reviewers comments to your best and submitting to a new venue.