# 11-11-2022 LeetCode 37. Sudoku Solver # https://leetcode.com/problems/sudoku-solver/description/ # Shall we attempt to use 9 digit binary to represent possibilities? # A 1 being possible, 0 meaning not. # Shall we assume we're being passed particularly simple sudoku puzzles # as the input: ones where iteratively eliminating possibilities on a # row, col, box basis is guarenteed to work? There are of course significantly # more difficult classses of puzzles that require advanced techniques. # Oh great... we are not only given basic puzzles # Id say the next most advanced technique after basic elimination is pair-sets: # If n squares share n posibilities within a grouping (row, col, box), then no # other square within that grouping can contain any of the shared possibilites- # they are bound to the n squares. Hopefully this technique isnt needed to solve # this, as thats getting a bit out there. Still basic, but a bit of coding... # After 90 minutes I've gotten it to work!!! For the first test case only... # The logic is there and I THINK it is indeed running through and removing # possibilities for every change made/squre solved. I guess the test cases include # MORE than the most basic sudoku puzzles. Running the following test case: # [[".",".","9","7","4","8",".",".","."],["7",".",".",".",".",".",".",".","."],[".","2",".","1",".","9",".",".","."],[".",".","7",".",".",".","2","4","."],[".","6","4",".","1",".","5","9","."],[".","9","8",".",".",".","3",".","."],[".",".",".","8",".","3",".","2","."],[".",".",".",".",".",".",".",".","6"],[".",".",".","2","7","5","9",".","."]] # And printing a whacky mixed "solved squares and bin(possibilities)" I can see squares that have multiple possibilites # BUT may be the only cell available for a given number for a row, col, or box. # I guess I need to implement the NEXT level of logic. When we run out of changed squares, # iterate through all remaining unsolved cells: for each row, col, box, IF the cell is the # only possibility for a given number, change it to that number and add it to the changed stack # STILL NOT ENOUGH! I guess we will have to implement the N sets of N possibilities per group # elimination method, but frankly I'm tire of this problem and peeking at the solution it # looks as if that may STILL not be enough. The given answer is "use backtracking", which baasically # amounts to having the computer guess and check. Very frustrating that this is the listed solution. # Its an lesson in trying to outhink the problem: I've wasted a number of hourse trying to # algorithmically solve the problem as I would do it on paper. A computer can guess and check its # way through, quickly so why bother with clever algos? Its really disappointing. # Do not return anything, modify board in-place instead class Solution: def solveSudoku(self, board: List[List[str]]) -> None: # print original board for clarity: # for row in board: # print(row) # Yes, these may unnecessary/clumsy, but I'm building as I go... We'll see what I use # Surely there is an elegant way to do this simply: 1<<ord(char-'a') or so. Less readable char_to_bin = { "1": 0b000000001, "2": 0b000000010, "3": 0b000000100, "4": 0b000001000, "5": 0b000010000, "6": 0b000100000, "7": 0b001000000, "8": 0b010000000, "9": 0b100000000, ".": 0b111111111, } bin_to_char = { 0b000000001: "1", 0b000000010: "2", 0b000000100: "3", 0b000001000: "4", 0b000010000: "5", 0b000100000: "6", 0b001000000: "7", 0b010000000: "8", 0b100000000: "9", 0b111111111: ".", } # setup binary board and preload set cells in changed stack for processing solved_cells = [] bin_board = [[0 for _ in range(9)] for _ in range(9)] for row in range(9): for col in range(9): bin_board[row][col] = char_to_bin[board[row][col]] if board[row][col] != ".": solved_cells.append((row, col, char_to_bin[board[row][col]])) # Remove 0b111111111 : '.' as a valid option in bin_to_char so we can use its # keys as "valid solved squares" dictionary instead of creating another bin_to_char.pop(0b111111111) while solved_cells: # print justified base 10 possibilities grid. Note cells with powers of two are solved: # for x in bin_board: # print([str(y).rjust(3, " ") for y in x]) # pass # print base 2 possibilities grid. Note cells with single '1' are solved: # print() # v # pass row, col, cell = solved_cells.pop() for i in range(9): # AND out ~cell with all in row if bin_board[row][i] not in bin_to_char: bin_board[row][i] &= ~cell # if cell solved, add to stack if bin_board[row][i] in bin_to_char: solved_cells.append((row, i, bin_board[row][i])) # AND out ~cell with all in col if bin_board[i][col] not in bin_to_char: bin_board[i][col] &= ~cell # if cell solved, add to stack if bin_board[i][col] in bin_to_char: solved_cells.append((i, col, bin_board[i][col])) # AND out ~cell with all in BOX # Clever boy trick to iterate through box cells using single offset counter box_row = (row // 3) * 3 + i // 3 box_col = (col // 3) * 3 + i % 3 if bin_board[box_row][box_col] not in bin_to_char: bin_board[box_row][box_col] &= ~cell # if cell solved, add to stack if bin_board[box_row][box_col] in bin_to_char: solved_cells.append( (box_row, box_col, bin_board[box_row][box_col]) ) # Did we run out of of changes? Solved? New Logic Level Time? if not solved_cells: unsolved = [] for row in range(9): for col in range(9): if bin_board[row][col] not in bin_to_char: unsolved.append((row, col, bin_board[row][col])) if not unsolved: # Hey, we solved it break # Well shoot. We have unsolved cells and base 'place and eliiminate' logic # has been exhausted. Time to check if remaining unsolved cells are the # only possibility for a given number in their row, col, or box. # Should we stop and go back a level of logic after finding a single new # set cell when using this logic? Or go through ALL unsolved cells at this # depth, solving them with this "level 2" logic and adding them to the # changed stack to be processed by another round of "level 1" logic later? while unsolved: # DELETE THIS LINE: FORCED TEST FOR CELL WE KNOW CAN BE SOLVED # unsolved = [(0,8,22)] row, col, cell = unsolved.pop() row_excluder = 0b111111111 col_excluder = 0b111111111 box_excluder = 0b111111111 for i in range(9): # When & with cell, will leave only bits where 1 in unsolved cell, but 0 for all others if i != col: row_excluder &= ~bin_board[row][i] # When & with cell, will leave only bits where 1 in unsolved cell, but 0 for all others if i != row: col_excluder &= ~bin_board[i][col] # When & with cell, will leave only bits where 1 in unsolved cell, but 0 for all others # Clever boy trick to iterate through box cells using single offset counter box_row = (row // 3) * 3 + i // 3 box_col = (col // 3) * 3 + i % 3 pass if not (box_row == row and box_col == col): box_excluder &= ~bin_board[box_row][box_col] # & "anti-excluvises" with cell, leaving a single bit on if unsolved cell must be a given # digit, being the only cell in that row, col, box with the possibility of doing so row_sinlge = row_excluder & cell col_sinlge = col_excluder & cell box_sinlge = box_excluder & cell # if cell solved, add to stack if row_sinlge in bin_to_char: bin_board[row][col] = row_sinlge solved_cells.append((row, col, row_sinlge)) elif col_sinlge in bin_to_char: bin_board[row][col] = col_sinlge solved_cells.append((row, col, col_sinlge)) elif box_sinlge in bin_to_char: bin_board[row][col] = box_sinlge solved_cells.append((row, col, box_sinlge)) # print() # for x in bin_board: # print([str(bin(y))[2:].rjust(9, "0") for y in x]) # pass # Convert binary board to char board INCLUDING whacky mixed results of solved squares as base 10 and unsolved 9 binary digit base 2 strings # for row in range(9): # for col in range(9): # board[row][col] = str(bin_to_char[bin_board[row][col]]).rjust(9, " ") if bin_board[row][col] in bin_to_char else str(bin(bin_board[row][col]))[2:].rjust(9, "0") # pass # #Convert binary board to char board when it works and its actually solved... for row in range(9): for col in range(9): board[row][col] = bin_to_char[bin_board[row][col]] pass # Print solved result print() for row in board: print(row) pass return # NO RETURN. Yes... this isnt modify in place, this is creating a whole parallel board and then translating it to the # original. I dont want to work with char board as it seems cumbersome. May try it next. Binary version seemed more interesting # It DOESNT say we cant use extra memory.