rrampage/sudoku-easy.py Secret

## 91 changes: 91 additions & 0 deletions sudoku-easy.py
@@ -0,0 +1,91 @@

    # Easy Sudoku Solver - No backtracking
# Easy Sudoku Solver - No backtracking


    """
"""

    Functions for pretty printing the board
Functions for pretty printing the board

    """
"""


    # Pretty print board
# Pretty print board

    def pp(a):
def pp(a):

        r = len(a)
    r = len(a)

        for x in range(r):
    for x in range(r):

            print(''.join((str(e) for e in a[x])))
        print(''.join((str(e) for e in a[x])))


    # Pretty print the neighborhood of a cell
# Pretty print the neighborhood of a cell

    def pn(i,j):
def pn(i,j):

        b = [['-' for x in range(9)] for y in range(9)]
    b = [['-' for x in range(9)] for y in range(9)]

        b[i][j] = 'O'
    b[i][j] = 'O'

        for x,y in N[(i,j)]:
    for x,y in N[(i,j)]:

            b[x][y] = 'X'
        b[x][y] = 'X'

        pp(b)
    pp(b)


    def box(i,j):
def box(i,j):

        # Calculate the "box number" from row and column
    # Calculate the "box number" from row and column

        return 3*(i//3) + (j//3)
    return 3*(i//3) + (j//3)


    def box_pairs(b):
def box_pairs(b):

        i = 3*(b // 3)
    i = 3*(b // 3)

        j = 3*(b % 3)
    j = 3*(b % 3)

        return [(i,j),(i,j+1),(i,j+2),(i+1,j),(i+1,j+1),(i+1,j+2),(i+2,j),(i+2,j+1),(i+2,j+2)]
    return [(i,j),(i,j+1),(i,j+2),(i+1,j),(i+1,j+1),(i+1,j+2),(i+2,j),(i+2,j+1),(i+2,j+2)]


    def neighbors():
def neighbors():

        # Generate all neighbor pairs for the 81 cells
    # Generate all neighbor pairs for the 81 cells

        boxes = [box_pairs(x) for x in range(9)] # Generate all possible pairs for each "box number"
    boxes = [box_pairs(x) for x in range(9)] # Generate all possible pairs for each "box number"

        ng = {}
    ng = {}

        for i,j in PAIRS:
    for i,j in PAIRS:

            s = set(boxes[box(i,j)]+[(i,x) for x in range(9)]+[(x,j) for x in range(9)])
        s = set(boxes[box(i,j)]+[(i,x) for x in range(9)]+[(x,j) for x in range(9)])

            s.remove((i,j))
        s.remove((i,j))

            ng[(i,j)] = s
        ng[(i,j)] = s

        return ng
    return ng


    def dup(a):
def dup(a):

        # Utility method to create duplicate of board
    # Utility method to create duplicate of board

        return [list(a[i]) for i in range(len(a))]
    return [list(a[i]) for i in range(len(a))]


    def check(a):
def check(a):

        # Checks if Sudoku is solved
    # Checks if Sudoku is solved

        for x in range(9):
    for x in range(9):

            if REF != set(a[x]) or REF != {a[i][x] for i in range(9)} or REF != {a[i][j] for i,j in box_pairs(x)}:
        if REF != set(a[x]) or REF != {a[i][x] for i in range(9)} or REF != {a[i][j] for i,j in box_pairs(x)}:

                return False
            return False

        return True
    return True


    def allowed(a, i, j):
def allowed(a, i, j):

        # Returns allowed values for a particular cell
    # Returns allowed values for a particular cell

        if a[i][j] != 0: # If already filled, ignore
    if a[i][j] != 0: # If already filled, ignore

            return set()
        return set()

        s = {a[x][y] for x,y in N[(i,j)] if a[x][y] != 0} #values of neighbors
    s = {a[x][y] for x,y in N[(i,j)] if a[x][y] != 0} #values of neighbors

        return REF - s
    return REF - s


    def instance(a):
def instance(a):

        # Solves easy Sudoku
    # Solves easy Sudoku

        if check(a):
    if check(a):

            return a
        return a

        s = {}
    s = {}

        b = dup(a)
    b = dup(a)

        for i,j in PAIRS:
    for i,j in PAIRS:

            e = allowed(a,i,j)
        e = allowed(a,i,j)

            if len(e) == 1:
        if len(e) == 1:

                v = e.pop()
            v = e.pop()

                b[i][j] = v
            b[i][j] = v

            s[(i,j)] = e
        s[(i,j)] = e

        if a == b:
    if a == b:

            # If no progress has been made, return
        # If no progress has been made, return

            return b
        return b

        return instance(b)
    return instance(b)


    REF = set(range(1,10)) # The Set we use to check if a row/col/box is filled correctly
REF = set(range(1,10)) # The Set we use to check if a row/col/box is filled correctly

    PAIRS = [(i,j) for i in range(9) for j in range(9)] # Generate all pairs from 0 to 9
PAIRS = [(i,j) for i in range(9) for j in range(9)] # Generate all pairs from 0 to 9

    N = neighbors() # One time call, generate and store all possible neighbors for a cell
N = neighbors() # One time call, generate and store all possible neighbors for a cell


    # A test instance
# A test instance

    puzzle = [[5,3,0,0,7,0,0,0,0],
puzzle = [[5,3,0,0,7,0,0,0,0],

              [6,0,0,1,9,5,0,0,0],
          [6,0,0,1,9,5,0,0,0],

              [0,9,8,0,0,0,0,6,0],
          [0,9,8,0,0,0,0,6,0],

              [8,0,0,0,6,0,0,0,3],
          [8,0,0,0,6,0,0,0,3],

              [4,0,0,8,0,3,0,0,1],
          [4,0,0,8,0,3,0,0,1],

              [7,0,0,0,2,0,0,0,6],
          [7,0,0,0,2,0,0,0,6],

              [0,6,0,0,0,0,2,8,0],
          [0,6,0,0,0,0,2,8,0],

              [0,0,0,4,1,9,0,0,5],
          [0,0,0,4,1,9,0,0,5],

              [0,0,0,0,8,0,0,7,9]]
          [0,0,0,0,8,0,0,7,9]]


    # Pretty print completed Sudoku
# Pretty print completed Sudoku

    pp(instance(puzzle))
pp(instance(puzzle))