?? ?? ??? ?? ? ?? ???? (Algorithm Based on Cardinality Number of Exact Cover Problem)

? ??? ???? NP-?? ??? ???? ????? ???? ?? ???? ??? ?? ???????? ?? ? ?? ????? ?????. ??? ????? "?? ??? ??? ?? ???? ???"? ??????? ??? ?????. ?? ?? ?? ?? ?? ??? ?? ????? ???? ??? ????? ??? ??????? ?????. ?? ?????? ???? ????? ???? ?? ???. ??, ?? ??? ??? ???? ??? ?? ????? ???? ??? ??? ?????. ??? ????? ???? ???? ??? ???? ????. ???, ???? ??? ?? ???? N-? ??? ???? ??? ????? ??? ? ??????. ??, ??? ???? ????? ???? ??? ?? P-???? ?????.

To the exact cover problem that remains NP-complete to which no polynomial time algorithm is made available, this paper proposes a linear time algorithm that yields an optimal solution. The proposed algorithm makes use of the set cover problem's major feature which states that "no identical element shall be included in more than one covering set". To satisfy this criterion, the proposed algorithm initially selects a subset with the minimum cardinality and deletes those that contain the cardinality identical to that of the selected subset. This process is repeatedly performed on remaining subsets until the final solution is obtained. Provided that the solution is unattainable, it selects subsets with the maximum cardinality and repeats the same process. The proposed algorithm has not only obtained the optimal solution with ease but also proved its wide applicability on N-queens problems, hence disproving the NP-completeness of the exact cover problem.