gistfile1.txt

  # returns bool if can be solved
  # solving a sudoku board...
  # I could try all permutations and check the board
  # or I could actually fill in the board... that seems tough
  # but if I try every solution...
  
  # when the following are valid for all:
  # rows
  # cols
  # sections
  
  # 9 x 9 = 81 cells
  # if I do all permutations... that would be 
  # if I just did it for a 4x4
  #
  # 1  1 
  # 1  1
  # ----
  # 1, 1, 1, 2
  # 1, 1, 1, 3
  # 1, 1, 2, 1
  # 1, 1, 2, 2
  # 1, 1, 2, 3
  # 1, 1, 3, 1
  # 1, 1, 3, 2
  # ...
  # basically, I'm counting upwards for an 81 digits number
  # 81 digits is a LOT of permutations and for each permutation I have to do up to 81 operations
  # 81^9 * 81 -- this is a huge number
  
  # I can't do all permutations
  
  # Strategy:
  # for each row, col in a section
  # check whether we can solve the square
  # I could also list the possibilities for each square, then do another pass and fill in all the
  # squares with a single possibility
  
  # Section 1 here would become:
  # 5, 3, [1, 2, 4]
  # 6, [7, 2, 4], [2, 4, 7]
  # [1, 2], 9, 8
  
  # Major Row 2, Col 1
  # 8, [1, 2, 5], [1, 2, 5, 9]
  # 4, [2, 5], [2, 5, 6, 9]
  # 7, [1, 5, 8], [1, 3, 4, 5, 6, 9] -> 3
  
  # if any possibility list of len 1, set the value, update board? or just pass new board onward
  # for each possibility set, if a number only appears in one list, the value must go there, alternatively go by number, if any number only has one place to call home, then set it, otherwise set it as a possibility
  
  # Breakdown
  # we want a different structure, for the board
  
  # flag all cells with the possible numbers
    # for each number 1-9
      # for each cell in the matrix
        # how can I verify a number can go in a cell?
        # - check row, col, section
  #flag_possibilities(board)   
     
  # update board:
    # for each row, check if there are any cells with a single possibility
    # for each column, check if any numbers only show up in 1 cell -- that cell ust be that number
    # for each row, check if any nums only show up in 1 cell -- that cell must be that number
    # for each 9x9 sections, check if any nums only show up in 1 cell
  # update(board)
  
def not_in_row(val, board, row):
  for col_val in board[row]:
    if val == col_val:
      return False 
  return True

print('--- NOT IN ROW ---')
assert not_in_row('1', [['1','2','3','4','5','6']], 0) == False
assert not_in_row('1', [['2']], 0)
print('------')

def not_in_col(val, board, col):
  for row in board:
    if val == row[col]:
      return False
  return True

print('--- NOT IN COL---')
assert not_in_col(1, [[1]], 0) == False
assert not_in_col(1, [[2]], 0) 
print('---')

def not_in_subboard(val, board, row, col):
  # how do we check the subboard?
  # I could hardcode each of the segments and check the row and cols are within those bounds
  # or... each subboard can be described relative to a point 
  # 2,2 would be 
  # subboard is row % 3 and col % 3
  # if row is 4 and col is 4 then we are 1,1
  # the question is, how do we then explore that sub array
  # 1,1 is the middle subboard, now we iterate the whole board
  # 1 * 3 is the offset for both row and col 
  # wait, I still need to get the number of divisions
  
  # something like, I have some row, col and I just need to know what the beg of that space is
  # go right and down for the size of window
  
  # board[(row - row % 3) + floor(i / 3)][(col - col % 3) + i % 3] == chr)
  top_left_row = (row - row % 3)
  top_left_col = (col - col % 3)
  for i in range(top_left_row, top_left_row + 3):
     for j in range(top_left_col, top_left_col + 3):
        if board[i][j] == val:
          return False
  return True

print('--- NOT IN SUBBOARD ---')
subboard = [
  ['1','2','3'],
  ['.', '.', '.'],
  ['7','8','9']
]
assert not_in_subboard('1', subboard, 0, 1) == False
assert not_in_subboard('4', subboard, 1, 1) 
print('------')

# recursive permutations problem, need to do a 9 way branch on every empty cell
# 0,0 (try 1) -> 0,1 -> try 1 -> ...
# optimization: start with cell that has fewest possible candidates
def get_candidates(board, row, col):
  NUMBERS = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
  candidates = []
  for val in NUMBERS:
    # check cols, check rows, check subboard
    # we have a collision
    if (not_in_row(val, board, row) and
        not_in_col(val, board, col) and
        not_in_subboard(val, board, row, col)):
      candidates.append(val)
      
  return candidates

print('--- GET CANDIDATES---')
assert get_candidates(subboard, 0, 1) == ['4', '5', '6']
print('------')

def sudoku_solve(board):
  # for each cell, get candidates, if no candidates available for a cell, and it's empty then the board is bad, back track
  row = -1
  col = -1
  candidates = None
  for r in range(len(board)):
    for c in range(len(board[0])):
      if board[r][c] == '.':
        newCandidates = get_candidates(board, r, c)
        if candidates == None or len(newCandidates) < len(candidates):
            candidates = newCandidates
            row = r
            col = c

                   
  # if the board has an entry in all places then we are done
  # i.e. if we never set candidates, then we never encountered an empty spot
  if candidates == None:
    return True
                   
  # otherwise start with the cell with the least candidates, recurse on all possibilities
  for candidate in candidates:
    board[row][col] = candidate
    if sudoku_solve(board):
      return True
    # back track if we don't return
    board[row][col] = '.'
  
  #print(board)
  return False

subboard = [
  ['1','2','3'],
  ['.', '.', '.'],
  ['7','8','9']
]
assert sudoku_solve(subboard)
subboard = [
  ['1','2','3','4','5','6'],
  ['4','5','6','1','2','3'],
  ['7','8','9','.','.','.'],
]
print(sudoku_solve(subboard))

board = [[".",".","3","8",".",".","4",".","."],[".",".",".",".","1",".",".","7","."],[".","6",".",".",".","5",".",".","9"],[".",".",".","9",".",".","6",".","."],[".","2",".",".",".",".",".","1","."],[".",".","4",".",".","3",".",".","2"],[".",".","2",".",".",".","8",".","."],[".","1",".",".",".",".",".","5","."],["9",".",".",".",".","7",".",".","3"]]
assert sudoku_solve(board)