Demo entry 6733571

Sudoku solution

   

Submitted by anonymous on Apr 17, 2018 at 20:33
Language: Python 3. Code size: 6.9 kB.

from copy import deepcopy
import time


class Cell:
    def __init__(self, v=0):
        self.value = v
        self.possible_values = list(range(1, 10)) if v==0 else [v]

    def __str__(self):
        return str(self.value)

    @property
    def possible_values_count(self):
        return len(self.possible_values)

    def confirm(self, v):
        if 0 < v < 10:
            self.value = v
            self.possible_values = [v]

    @property
    def confirmed(self):
        return self.possible_values_count == 1

    def eliminate(self, v):
        if v in self.possible_values:
            self.possible_values.remove(v)
            if self.confirmed:
                self.confirm(self.possible_values[0])


class Sudoku:
    def __init__(self, g=[[0]*9]*9):
        self.grid = []
        for r in g:
            row = []
            for c in r:
                row.append(Cell(c))
            self.grid.append(row)

    @property
    def show(self):
        hr = "+---------+---------+---------+"
        print(hr)
        for r in range (9):
            print("|", end="")
            for c in range(9):
                t = '.' if self.grid[r][c].value==0 else self.grid[r][c].value
                print(" {0} ".format(t), end="")
                if c == 2 or c == 5:
                    print("|", end="")
            print("|")
            if r == 2 or r == 5:
                print(hr)
        print(hr)
        print("Confirmed cells: {0}.".format(self.confirmed_cells_count))
        print()

    def matches(self, t): #tell if a sudoku is identical to another
        match = True
        for r in range (9):
            for c in range(9):
                if self.grid[r][c].value != t.grid[r][c].value:
                    match = False
                if not match:
                    break
            if not match:
                break
        return match

    @property
    def solved(self):
        solved = True
        for r in range(9):
            for c in range(9):
                if self.grid[r][c].value == 0:
                    solved = False
                if not solved:
                    break
            if not solved:
                break
        return solved

    @property
    def refresh(self):
        for r in range(9):
            for c in range(9):
                if self.grid[r][c].confirmed:
                    # clean up the same row:
                    for t in range(9):
                        if t == c:
                            continue
                        else:
                            self.grid[r][t].eliminate(self.grid[r][c].value)
                    # clean up the same column
                    for t in range(9):
                        if t == r:
                            continue
                        else:
                            self.grid[t][c].eliminate(self.grid[r][c].value)
                    # clean up the same block:
                    block_start_row = int(r/3)*3
                    block_start_col = int(c/3)*3
                    for br in range(block_start_row, block_start_row+3):
                        for bc in range(block_start_col, block_start_col+3):
                            if br == r and bc == c:
                                continue
                            else:
                                self.grid[br][bc].eliminate(self.grid[r][c].value)

    @property
    def confirmed_cells_count(self):
        count = 0
        for r in range(9):
            for c in range(9):
                if self.grid[r][c].confirmed:
                    count += 1
        return count

    @property
    def refresh_all(self):
        refresh_count = 0
        #print ("Refresh attempts begin.")
        #self.show
        while True:
            before = self.confirmed_cells_count
            refresh_count += 1
            #print ("Refresh #{0}".format(refresh_count))
            self.refresh
            #self.show
            after = self.confirmed_cells_count
            if self.confirmed_cells_count == 81 or before == after:
                break
        #print("Total refresh attempts: {0}".format(refresh_count))

    @property
    def hypothesized_sudokus(self):
        hypothesized_sudokus = []
        for r in range(9):
            for c in range(9):
                if not self.grid[r][c].confirmed:
                    for hypothesized_value in self.grid[r][c].possible_values:
                        t = deepcopy(self)
                        t.grid[r][c].confirm(hypothesized_value)
                        hypothesized_sudokus.append(t)
        return hypothesized_sudokus

    def solution(self):
        solution = deepcopy(self)
        solution.refresh_all
        if not solution.solved:
            for hypothesized_sudoku in solution.hypothesized_sudokus:
                t = deepcopy(hypothesized_sudoku.solution())
                if t.solved:
                    solution = t
                    break
        return solution


easy = [    [0,8,0,0,0,5,0,0,3],
            [5,0,0,0,8,6,0,7,2],
            [7,2,3,0,0,9,0,0,0],
            [0,0,2,7,0,0,0,5,4],
            [0,0,0,6,2,4,0,0,0],
            [6,4,0,0,0,3,9,0,0],
            [0,0,0,9,0,0,5,3,8],
            [9,7,0,1,3,0,0,0,6],
            [3,0,0,5,0,0,0,1,0]]

medium = [  [0,0,4,0,0,9,0,0,0],
            [0,0,0,0,0,0,0,1,6],
            [2,3,7,0,0,5,0,9,0],
            [0,4,0,5,8,7,0,0,9],
            [0,5,0,2,0,1,0,4,0],
            [7,0,0,9,6,4,0,5,0],
            [0,6,0,7,0,0,4,3,2],
            [4,2,0,0,0,0,0,0,0],
            [0,0,0,3,0,0,5,0,0]]

hard = [    [0,4,0,0,5,1,0,0,0],
            [5,2,0,0,0,0,4,0,9],
            [0,9,0,2,0,0,0,0,6],
            [9,0,0,0,0,0,0,2,0],
            [0,0,2,5,0,7,1,0,0],
            [0,3,0,0,0,0,0,0,7],
            [8,0,0,0,0,5,0,9,0],
            [7,0,4,0,0,0,0,8,1],
            [0,0,0,6,8,0,0,7,0]]

evil = [    [7,0,0,0,0,3,0,9,0],
            [0,0,0,0,0,7,0,6,0],
            [1,8,0,9,0,0,0,4,0],
            [0,0,0,0,0,0,4,0,0],
            [0,0,5,2,4,1,8,0,0],
            [0,0,6,0,0,0,0,0,0],
            [0,5,0,0,0,4,0,8,7],
            [0,2,0,3,0,0,0,0,0],
            [0,4,0,6,0,0,0,0,5]]

hardest = [ [8,0,0,0,0,0,0,0,0],
            [0,0,3,6,0,0,0,0,0],
            [0,7,0,0,9,0,2,0,0],
            [0,5,0,0,0,7,0,0,0],
            [0,0,0,0,4,5,7,0,0],
            [0,0,0,1,0,0,0,3,0],
            [0,0,1,0,0,0,0,6,8],
            [0,0,8,5,0,0,0,1,0],
            [0,9,0,0,0,0,4,0,0]]

start = time.time()
s = Sudoku(hardest)
# s = Sudoku(evil)
# s = Sudoku(hard)
# s = Sudoku(medium)
# s = Sudoku(easy)
s = s.solution()
s.show
end = time.time()
print ("{0} seconds.".format(end-start))

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).