This is a surprisingly complicated problem, and you will probably be best served by looking at backtracking:
backtracking C# - Google Search[
^] - none of those will directly solve your problem, but they do explain the methodology you will need to use to complete this homework assignment.