Home > Programming > Illustration of solving sudoku puzzle using Brute Force, Generate and Test, and Arc consistency

Illustration of solving sudoku puzzle using Brute Force, Generate and Test, and Arc consistency

There are different ways of solving Sudoku puzzles. Brute force, Generate and Test both perform pretty well for easy puzzles but Arc Consistency beats them all in speed and solving very complex puzzles with less CPU.  Peter Norvig has a robust solution that solve any puzzle .

Brute force, Generate and Test are easy to implement. but what about using Arc Consistency. For adventure I attempted to try out using arc consistency to solve sudoku puzzles. I did manage to implement the concept though my implementation is not as fast as Norvig’s.

To ease the implementation, I modeled the sudoku as follows:-

  • A Cell knows about  the row, column, block, general sudoku reference and its domain.
  • Both Column, Block and Row  know about the sudoku reference and the cells that are in it
  • Sudoku class itself knows its blocks, rows, columns and cells.
  • I also keep a list of constraints cell-to-row, cell-to-block and cell-to-column

With the arrangement above I perform arc consistency on the constraints.

import copy
import time

class Cell(object):
    row=None
    column=None
    block=None
    domain=None
    value=None
    sudoku=None
    def __init__(self,sudoku, value):
        self.sudoku=sudoku
        self.value=value
        self.domain=[]
    def __hash__(self):
        return int(str(self.row.index)+str(self.column.index))
    
    def __eq__(self,other):
        try:
            return self.row.index == other.row.index and self.column.index == other.column.index
        except:
            return False
    def __str__(self):
        return "Cell " + str(self.row.index) + str(self.column.index)
    
class Row(object):
    sudoku=None
    index=None
    cells=None
    def __init__(self,sudoku, index):
        self.sudoku=sudoku
        self.index=index            
        self.cells=[]
    def addCell(self, cell):
        self.cells.append(cell)
        cell.row=self
    def __hash__(self):
        return int("9"+str(self.index))
    def __eq__(self, other):
        return isinstance(other, Row) and self.index == other.index
    def __str__(self):
        return "Row " + str(self.index)
    

class Column(object):
    sudoku=None
    index=None
    cells=None
    def __init__(self, sudoku,index):
        self.sudoku=sudoku
        self.index=index
        self.cells=[]
    def addCell(self,cell):
        self.cells.append(cell)
        cell.column=self
    def __hash__(self):
        return int("10"+str(self.index))
    def __eq__(self, other):
        return isinstance(other, Column) and self.index == other.index
    def __str__(self):
        return "Column " + str(self.index)
    
class Block(object):
    sudoku=None
    index=None
    cells=None
    def __init__(self,sudoku, index):
        self.sudoku=None
        self.index=index
        self.cells=[]
    def addCell(self, cell):
        self.cells.append(cell)
        cell.block=self
    def __hash__(self):
        return int("11"+str(self.index))
    def __eq__(self, other):
        return isinstance(other, Block) and self.index == other.index
    def __str__(self):
        return "Block " + str(self.index)
    
class Sudoku(object):
    columns=None
    rows=None
    blocks=None
    cells=None
    TDA = None
    __width=9
    
    def getBlockIndex(self, rowIndex, columnIndex):
        if rowIndex <= 2:
            if columnIndex <= 2:
                return 0
            elif columnIndex <= 5:
                return 1
            elif columnIndex <= 8:
                return 2
        elif rowIndex <= 5:
            if columnIndex <= 2:
                return 3
            elif columnIndex <= 5:
                return 4
            elif columnIndex <= 8:
                return 5
        elif rowIndex <= 8:
            if columnIndex <= 2:
                return 6
            elif columnIndex <= 5:
                return 7
            elif columnIndex <= 8:
                return 8
        return None
    
    def __init__(self, puzzle):
        self.TDA=dict()
        self.cells=[]
        self.blocks=[ Block(self,n) for n in range(self.__width)]
        self.columns=[ Column(self,n) for n in range(self.__width)]
        self.rows = [ Row(self,n) for n in range(self.__width)]
        
        for row in range(self.__width):
            for column in range(self.__width):
                cell = Cell(self,puzzle[row][column])                
                self.cells.append(cell)
                self.columns[column].addCell(cell)
                self.rows[row].addCell(cell)
                self.blocks[self.getBlockIndex(row,column)].addCell(cell)
                
                if cell.value:
                    cell.domain.append(cell.value)
                else:
                    cell.domain.extend(range(1, self.__width+1))                    
                    self.TDA[(cell, cell.row)]=1
                    self.TDA[(cell, cell.column)]=1
                    self.TDA[(cell, cell.block)]=1
                    
    def ArcConsistency(self):                
        while (1 in self.TDA.values()):            
            for cell, constraint in self.TDA:                
                if self.TDA[(cell, constraint)] == 0: continue
                cellDomainModified=False
                for constraintCell in constraint.cells:
                    if cell != constraintCell and constraintCell.value != None and constraintCell.value in cell.domain:
                        cell.domain.remove(constraintCell.value)
                        cellDomainModified=True
                self.TDA[(cell, constraint)]=0
                if cellDomainModified:
                    for primeConstraint in [cell.row, cell.column, cell.block]:
                        if primeConstraint != constraint:
                            for primeConstraintCell in primeConstraint.cells:
                                if  primeConstraintCell.value==None:
                                    self.TDA[(primeConstraintCell, primeConstraint)]=1
        cellConstraintsToRemove=[]
        for cell, constraint in self.TDA:
            if len(cell.domain)==1:
                cell.value = cell.domain[0]
                cellConstraintsToRemove.append((cell, constraint))
        for cellConstraintToRemove in cellConstraintsToRemove:
            del self.TDA[cellConstraintToRemove]
                    
    def solve(self):	
	start=time.clock()
        self.ArcConsistency()
	if self.isSolved():	    
	    return self, time.clock()-start	
	sol=self.search()
	return sol, time.clock()-start
	
    def isInconsistent(self):
	invalid=False
	for cell in self.cells:
	    if cell.value==None and len(cell.domain) == 0:
		invalid=True
		break
	if not invalid:
	    for row  in self.rows:
		if not self.areCellsValid(row.cells):
		    invalid=True
		    break
	if not invalid:
	    for block  in self.blocks:
		if not self.areCellsValid(block.cells):
		    invalid=True
		    break
	if not invalid:
	    for column  in self.columns:
		if not self.areCellsValid(column.cells):
		    invalid=True
		    break
		
	return invalid
    
    def areCellsValid(self, cells):
	noneNullCells = [cell for cell in cells if cell.value != None]
	return len(noneNullCells) == len(set(cell.value for cell in noneNullCells))

    def search(self):
	try:
	    if threading.currentThread().stopFlag:
		return None
	except:
	    pass
	
	sudokuCopy = copy.deepcopy(self)
	count, cell = min((len(cell.domain), cell) for cell in sudokuCopy.cells if cell.value == None)
	if( cell == None): return
	cellIndex = sudokuCopy.cells.index(cell)
	for value in copy.deepcopy(cell.domain):
	    sudokuTemp = copy.deepcopy(sudokuCopy)
	    sudokuTemp.cells[cellIndex].value=value
	    sudokuTemp.cells[cellIndex].domain=[]
	    sudokuTemp.cells[cellIndex].domain.append(value)
	    del sudokuTemp.TDA[(sudokuTemp.cells[cellIndex], sudokuTemp.cells[cellIndex].row)]
	    del sudokuTemp.TDA[(sudokuTemp.cells[cellIndex], sudokuTemp.cells[cellIndex].column)]
	    del sudokuTemp.TDA[(sudokuTemp.cells[cellIndex], sudokuTemp.cells[cellIndex].block)]
	    for tdaDictKey in sudokuTemp.TDA:
		sudokuTemp.TDA[tdaDictKey]=1
	    sudokuTemp.ArcConsistency()
	    if sudokuTemp.isInconsistent():
		continue
	    elif sudokuTemp.isSolved():
		return sudokuTemp
	    else:
		solution=sudokuTemp.search()
		if solution and solution.isSolved():
		    return solution
	return None
    
    def isSolved(self):
        value=True
        for cell in self.cells:
            if cell.value == None:
                value=False
                break
        return value
    
    def toPuzzle(self):
        return [ [ cell.value for cell in row.cells ] for row in self.rows ]
                    
if __name__ == "__main__":

    
    def printSudoku(sudokuPuzzle):
	for row in sudokuPuzzle.toPuzzle():
	    print str(row)
    
    puzzle=[[None,None,None,None,None,None,None,None,1],
            [None,None,None,None,None,None,None,None,None],
            [None,None,None,None,None,None,None,None,None],
            [None,None,None,None,None,None,None,None,None],
            [None,None,None,None,1,None,None,None,None],
            [None,None,None,None,None,None,None,None,None],
            [None,None,None,None,None,None,None,None,None],
            [None,None,None,None,None,None,None,None,None],
            [1,None,None,None,None,None,None,None,None]]
    
        
    sudoku = Sudoku(puzzle)    
    solvedSudoku, elapsed=sudoku.solve()

    index=0
    for row in solvedSudoku.toPuzzle():
	print str(row) + "\t\t\t" + str(puzzle[index])
	index=index+1
    print "Took " + str(elapsed)
Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: