CMU 15-112: Fundamentals of Programming and Computer Science
Sudoku Hints (from lecture on 22-Nov)

State class
  * state.board
  * state.legals
  * copy.deepcopy(state)

Debug printing
  * def printBoard(self):
        # copy print2dList from here:
        # https://www.cs.cmu.edu/~112/notes/notes-2d-lists.html#printing
        print2dList(self.board)
  * def printLegals(self):
        colWidth = 4
        for col in range(9):
            colWidth = max(colWidth, 1+max([len(self.legals[row][col]) for row in range(9)]))
        for row in range(9):
            for col in range(9):
                label = ''.join([str(v) for v in sorted(self.legals[row][col])])
                if label == '': label = '-'
                print(f"{' '*(colWidth - len(label))}{label}", end='')
            print()
  * def print(self): self.printBoard(); self.printLegals()

Board loading
  * def loadBoardPaths(filters):
        boardPaths = [ ]
        for filename in os.listdir(f'boards/'):
            if filename.endswith('.txt'):
                if hasFilters(filename, filters):
                    boardPaths.append(f'boards/{filename}')
        return boardPaths

    def hasFilters(filename, filters=None):
        if filters == None: return True
        for filter in filters:
            if filter not in filename:
                return False
        return True

    def loadRandomBoard(filters=None):
        ...

State set, ban, unban
  * state.set(self, row, col, value)
  * state.ban(self, row, col, values)
  * state.unban(self, row, col, values)

State Constructor
  * create board + legals
  * set each non-zero value in the starting board 
    (use state.set so legals are updated)

Regions
  * A region is a list of 9 (row,col) tuples
  * def getRowRegion(self, row):
    def getColRegion(self, col):
    def getBlockRegion(self, block):
    def getBlock(self, row, col):
    def getBlockRegionByCell(self, row, col):
    def getCellRegions(self, row, col):
    def getAllRegions(self):
    def getAllRegionsThatContainTargets(self, targets):

Backtracking Solver
  * Basic backtracker: expand first empty cell
  * Faster backtracker: expand cell with fewest legals

Hints
  * Hint 1: obvious (naked) single
  * Hint 2: obvious (naked) tuple (pair, triple, quad, quint)
    def getHint2(self):
        for region in self.getAllRegions():
            for N in range(2, 6):
                result = self.applyRule2(region, N)
                if result != None:
                    return result
        return None

    def applyRule2(self, region, N):
        '''
        This method uses:
            * itertools.combinations(region, N)
            * self.valuesAreOnlyLegals(values, targets)
            * self.getBansForAllRegions(values, targets)
        '''

    def getBansForAllRegions(self, values, targets):
        # The values (to ban) can stay in the targets, but they must be
        # banned from all other cells in all regions that contain all
        # the targets
        bans = [ ]
        for region in self.getAllRegionsThatContainTargets(targets):
            ...

Testing the backtracker
  * def testBacktracker(filters):
        time0 = time.time()
        boardPaths = sorted(loadBoardPaths(filters))
        failedPaths = [ ]
        for boardPath in boardPaths:
            board = loadBoard(boardPath)
            print(boardPath)
            solution = solveWithBacktracking(board, verbose=False)
            if not solution:
                failedPaths.append(boardPath)
        print()
        totalCount = len(boardPaths)
        failedCount = len(failedPaths)
        okCount = totalCount - failedCount
        time1 = time.time()
        if len(failedPaths) > 0:
            print('Failed boards:')
            for path in failedPaths:
                print(f'    {path}')
        percent = round(100 * okCount/totalCount)
        print(f'Success rate: {okCount}/{totalCount} = {percent}%')
        print(f'Total time: {round(time1-time0, 1)} seconds')

    Call like so:
        testBacktracker(filters=['easy'])