add solve() function in cw_csp, which currently uses a simple form of backtracking + selecting minimum domain size variables
Details
add undo_ac3() in cw_csp to undo previous calls to AC-3 algorithm to support backtracking
add functions in cw_csp to overwrite crossword (overwrite_cw()) and undo overwriting (undo_overwrite_cw()) while solving to print progress
add word inequality as an additional required condition for cw_constraint to be satisfied to help prevent most duplicates (does not prevent duplicate words that do not intersect)
add enums to represent solving techniques and variable selection heuristics
changed black tile char representation to an empty space for easier reading
add assertion_failure_exception() call for ERROR and FATAL level prints in cw_utils
Testing
add dataset words_top1000.txt containing the top 1000 English words by frequency for testing
add to cw_csp test suite with tests for duplicate word prevention, and validity of finding solutions with backtracking
these tests include blank puzzles with limited/1000-word dictionary, NYT mini puzzles with dictionaries only containing clue answers, and full 15x15 NYT puzzles with full supplemented 1000-word dictionaries
tests for contents of puzzles that used backtracking not included due to possibility of multiple solutions; all conditions needed for a crossword to be valid are already tested in the backtracking validity tests
Notes
to handle duplicate word prevention, solve_backtracking() contains a base case where unassigned variables with one already-used word in their domain immediately cause a false return value. this is only efficient because the only variable selection heuristic is minimum value remaining, causing those variables to be considered immediately after an invalid word assignment; i.e. that branch of backtracking will not be explored at all. when more variable selection heuristics are added, either ac3() needs to include duplicate prevention or all new solving strategies will need to include this same base case
due to domains being very large for full word datasets, adding to prev_pruned_domains in cw_csp while executing ac3() may need to be converted to be via ptr instead of value in the future
in the future, cw_utils should be updated to include a non-printing verbosity level and/or and add global macros to enable/disable prints for each module
word_finder still may need to be updated to use RAII in the future
may want to add a feature to add/remove black tiles while solving to find better solutions in the future
Overview
solve()function incw_csp, which currently uses a simple form of backtracking + selecting minimum domain size variablesDetails
undo_ac3()incw_cspto undo previous calls to AC-3 algorithm to support backtrackingcw_cspto overwrite crossword (overwrite_cw()) and undo overwriting (undo_overwrite_cw()) while solving to print progresscw_constraintto be satisfied to help prevent most duplicates (does not prevent duplicate words that do not intersect)assertion_failure_exception()call forERRORandFATALlevel prints incw_utilsTesting
words_top1000.txtcontaining the top 1000 English words by frequency for testingcw_csptest suite with tests for duplicate word prevention, and validity of finding solutions with backtrackingNotes
solve_backtracking()contains a base case where unassigned variables with one already-used word in their domain immediately cause afalsereturn value. this is only efficient because the only variable selection heuristic is minimum value remaining, causing those variables to be considered immediately after an invalid word assignment; i.e. that branch of backtracking will not be explored at all. when more variable selection heuristics are added, eitherac3()needs to include duplicate prevention or all new solving strategies will need to include this same base caseprev_pruned_domainsincw_cspwhile executingac3()may need to be converted to be via ptr instead of value in the futurecw_utilsshould be updated to include a non-printing verbosity level and/or and add global macros to enable/disable prints for each moduleword_finderstill may need to be updated to use RAII in the future