# Tutorial 12 — Constraint Solving with Backtracking# Python 3; standard library only. Q1–10 core; Q11–12 optional.# Run one question: python3 constraints.py 1def seat_people(people, forbidden, middle_only): # Decide who sits at position len(path). path = [] used = set() answers = [] # TODO: check the end-seat and adjacency rules before each choice. raise NotImplementedError("Q01")def assign_lockers(allowed): assignment = [] used = set() answers = [] # TODO: candidates for person i come from allowed[i], not all lockers. raise NotImplementedError("Q02")def color_map(graph, k): colors = [-1] * len(graph) answers = [] # TODO: check every already-colored neighbor, not only the previous region. raise NotImplementedError("Q03")def solve_lock(digits, length, clues): path = [] used = set() answers = [] # TODO: a partial code must not exceed a clue's hit count. # It must also have enough remaining positions to reach that count. raise NotImplementedError("Q04")def solve_sudoku(board): grid = [row[:] for row in board] # TODO: validate existing clues; locate an empty cell. # Try digits that do not conflict with its row, column or 2x2 box. # Restore a failed choice to 0. Stop after finding one full solution. raise NotImplementedError("Q05")def fill_crossword(board, slots, words): grid = [list(row) for row in board] used = set() # TODO: before writing a word, save the OLD content of every slot cell. # Undo must restore old letters, not replace the entire slot with dots. raise NotImplementedError("Q06")def tile_dominoes(rows, cols, blocked): occupied = set(blocked) placement = [] answers = [] # TODO: always cover the FIRST empty cell next. # A single choice occupies two cells; undo must free both. raise NotImplementedError("Q07")def visit_all(graph, start): path = [start] used = {start} answers = [] # TODO: only extend along an edge; save only paths visiting EVERY vertex. # Remove a vertex from used when returning to try another route. raise NotImplementedError("Q08")def assemble_tiles(tiles): placement = [] used = set() answers = [] # TODO: a new tile must match both its placed left and upper neighbors. raise NotImplementedError("Q09")def solve_letters(left, right, total): letters = sorted(set(left + right + total)) assignment = {} used = set() answers = [] # TODO: enforce distinct digits and leading-zero rules. # Once all letters are assigned, evaluate the actual equation. raise NotImplementedError("Q10")def solve_nonogram(row_clues, col_clues): # TODO: generate row patterns matching each row clue. # Choose one pattern per row, then verify all column runs. # Extra: reject a column prefix as soon as it cannot match its clue. raise NotImplementedError("Q11")def n_queens(n): placement = [] columns, down_diagonals, up_diagonals = set(), set(), set() answers = [] # TODO: (r,c) occupies column c and diagonals r-c and r+c. # Undo all three sets when returning. raise NotImplementedError("Q12")# Checks; itertools is used only by checks.import copyimport itertoolsdef freeze(value): if isinstance(value, dict): return tuple(sorted((k,freeze(v)) for k,v in value.items())) if isinstance(value,(list,tuple)): return tuple(freeze(v) for v in value) return valuedef check_unique(result, count): assert isinstance(result,list), "Return a list" assert len(result)==count, f"Expected {count} solutions; got {len(result)}" assert len({freeze(row) for row in result})==count, "Duplicate solutions"def check_same_rows(actual, expected): check_unique(actual,len(expected)) assert {freeze(row) for row in actual}=={freeze(row) for row in expected}def check_q01(): people = ['A','B','C','D'] forbidden = [('A','B')] original = people[:] result = seat_people(people, forbidden, {'C'}) check_unique(result, 8) for row in result: assert set(row) == set(people) and len(row) == 4 assert row[0] != 'C' and row[-1] != 'C' assert all(set(row[i:i+2]) != {'A','B'} for i in range(3)) assert people == original assert seat_people(['A'], [], {'A'}) == [] check_unique(seat_people(['A','B','C'], [], {'A'}), 2)def check_q02(): allowed = [[1,2], [1], [2,3]] original = copy.deepcopy(allowed) assert assign_lockers(allowed) == [[2,1,3]] assert allowed == original assert assign_lockers([[1], [1]]) == [] assert assign_lockers([]) == [[]] result = assign_lockers([[1,2,3], [1,2,3]]) check_unique(result, 6) assert all(len(r)==2 and len(set(r))==2 and set(r)<={1,2,3} for r in result)def check_q03(): triangle = [[1,2],[0,2],[0,1]] assert color_map(triangle, 2) == [] result = color_map(triangle, 3) check_unique(result, 6) assert all(len(r)==3 and set(r)=={0,1,2} for r in result) check_unique(color_map([[1],[0,2],[1]], 2), 2) check_unique(color_map([[],[]], 2), 4) assert color_map([], 2) == [[]]def check_q04(): assert set(solve_lock('012', 3, [('012',1),('021',0)])) == {'102','210'} assert solve_lock('012', 3, [('012',3),('012',0)]) == [] result = solve_lock('0123', 2, []) check_unique(result, 12) assert all(len(r)==2 and len(set(r))==2 and set(r)<=set('0123') for r in result) assert solve_lock('01', 3, []) == []def check_q05(): puzzle = [[1,0,0,4],[0,4,1,0],[0,1,4,0],[4,0,0,1]] original = copy.deepcopy(puzzle) solved = solve_sudoku(puzzle) assert solved is not None assert len(solved)==4 and all(len(row)==4 for row in solved) assert all(set(row)=={1,2,3,4} for row in solved) assert all({solved[r][c] for r in range(4)}=={1,2,3,4} for c in range(4)) assert all({solved[r+i][c+j] for i in range(2) for j in range(2)}=={1,2,3,4} for r in (0,2) for c in (0,2)) assert all(not puzzle[r][c] or solved[r][c]==puzzle[r][c] for r in range(4) for c in range(4)) assert puzzle == original bad = [[1,1,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]] assert solve_sudoku(bad) is None assert solve_sudoku(solved) == solveddef check_q06(): board = ['...','#.#','#.#'] slots = [[(0,0),(0,1),(0,2)],[(0,1),(1,1),(2,1)]] assert fill_crossword(board, slots, ['DOG','CAT','APE']) == ['CAT','#P#','#E#'] assert board == ['...','#.#','#.#'] assert fill_crossword(board, slots, ['ANT','DOG']) is None assert fill_crossword(['.A.','#.#','#.#'], slots, ['CAT','APE']) == ['CAT','#P#','#E#'] # A shared cell must survive undoing a later word. s = [[(0,0),(0,1)],[(0,1),(1,1)],[(1,0),(1,1)]] assert fill_crossword(['..','..'], s, ['AB','BC','BD','ED']) == ['AB','ED']def check_q07(): for rows,cols,blocked,count in [(2,2,set(),2),(2,3,set(),3),(3,3,set(),0), (2,2,{(0,0)},0),(1,2,{(0,0),(0,1)},1)]: original = set(blocked) result = tile_dominoes(rows,cols,blocked) canonical = [] for tiling in result: cells = [] for a,b in tiling: assert abs(a[0]-b[0])+abs(a[1]-b[1])==1 cells.extend((a,b)) assert len(cells)==len(set(cells)) assert set(cells)=={(r,c) for r in range(rows) for c in range(cols)}-blocked canonical.append(tuple(sorted(tuple(sorted(d)) for d in tiling))) assert len(canonical)==len(set(canonical))==count assert blocked==originaldef check_q08(): graph = [[1,2],[0,2],[0,1]] result = visit_all(graph,0) check_unique(result,2) for path in result: assert path[0]==0 and set(path)=={0,1,2} and len(path)==3 assert all(b in graph[a] for a,b in zip(path,path[1:])) assert visit_all([[1],[0,2],[1]],1)==[] assert visit_all([[1],[0],[]],0)==[] assert visit_all([[]],0)==[[0]]def check_q09(): tiles=[('x','a','b','x'),('x','x','c','a'),('b','d','x','x'),('c','x','x','d')] result=assemble_tiles(tiles) expected=[] for p in itertools.permutations(range(4)): if (tiles[p[0]][1]==tiles[p[1]][3] and tiles[p[2]][1]==tiles[p[3]][3] and tiles[p[0]][2]==tiles[p[2]][0] and tiles[p[1]][2]==tiles[p[3]][0]): expected.append(list(p)) check_same_rows(result,expected) check_unique(assemble_tiles([('a','a','a','a')]*4),24) assert assemble_tiles([(str(i),)*4 for i in range(4)])==[]def check_q10(): result=solve_letters('A','A','B') assert {tuple(sorted(d.items())) for d in result}=={ (('A',1),('B',2)),(('A',2),('B',4)),(('A',3),('B',6)),(('A',4),('B',8))} assert len(result)==4 result=solve_letters('AB','BA','CC') expected={(a,b,a+b) for a in range(1,10) for b in range(1,10) if a!=b and a+b<=9} assert len(result)==len(expected) assert {(d['A'],d['B'],d['C']) for d in result}==expected assert solve_letters('A','B','A')==[{'A':a,'B':0} for a in range(1,10)]def check_q11(): assert solve_nonogram([[1],[3],[1]],[[1],[3],[1]])==[[0,1,0],[1,1,1],[0,1,0]] assert solve_nonogram([[]],[[]])==[[0]] assert solve_nonogram([[1]],[[]]) is None result=solve_nonogram([[1],[1]],[[1],[1]]) assert result in ([[1,0],[0,1]],[[0,1],[1,0]])def check_q12(): for n,count in [(1,1),(2,0),(3,0),(4,2),(5,10),(6,4)]: result=n_queens(n) check_unique(result,count) for row in result: assert len(row)==n and set(row)==set(range(n)) assert len({r-c for r,c in enumerate(row)})==n assert len({r+c for r,c in enumerate(row)})==nimport sysCHECKS = {1: check_q01, 2: check_q02, 3: check_q03, 4: check_q04, 5: check_q05, 6: check_q06, 7: check_q07, 8: check_q08, 9: check_q09, 10: check_q10, 11: check_q11, 12: check_q12}GROUPS = {"core": list(range(1,11)), "extra": [11,12], "all": list(range(1,13))}if __name__ == "__main__": name = sys.argv[1] if len(sys.argv)>1 else "core" if name.isdigit() and int(name) in CHECKS: selected = [int(name)] elif name in GROUPS: selected = GROUPS[name] else: print("Choose core, extra, all, or a question number from 1 to 12.") sys.exit(2) for number in selected: try: CHECKS[number]() except Exception as error: print(f"Q{number:02d} failed: {type(error).__name__}: {error}") sys.exit(1) print(f"Q{number:02d} passed.") print(f"{len(selected)}/{len(selected)} checks passed.")