python-ai / src / sudoku / sudoku.py

#!/usr/bin/env python

import math
import array
import copy
import csp

class Board(object):
    """Class for a Sudoku board.
    
    The constructor takes two optional arguments. If the filename argument
    is given, the board is loaded from a file with the following format:
    
        <board size>
        <number of initial values>
        <row> <col> <val>
    
    The two-dimensional Sudoku board is backed by a one-dimensional Python
    array type, which can get accessed using row/column indexing through the
    get(row, col) and set(row, col, val) methods.
    
    In addition, this class can differentiate in-progress board states from
    Sudoku goal states through the complete() method."""
    
    def __init__(self, size=None, filename=None, mapping=None):
        """Constructor. See class doc string."""
        if filename:
            f = open(filename, 'r')
            self.initBoard(int(f.readline()))
            vals = int(f.readline())
            for i in range(vals):
                line = f.readline()
                chars = line.split()
                row = int(chars[0]) - 1
                col = int(chars[1]) - 1
                val = int(chars[2])
                self.set(row, col, val)
            f.close()
        elif mapping:
            size = int(math.sqrt(len(mapping)))
            self.initBoard(size)
            for k in mapping:
                self.board[k] = mapping[k]
        else:
            if not size:
                size = 9
            self.initBoard(size)
    def initBoard(self, size):
        self.size = size
        self.width = int(math.sqrt(size))
        self.board = array.array('H', [0 for i in range(size*size)])
    def idx(self, row, col):
        return row*self.size + col
    def boxIdx(self, box):
        w = self.width
        rs = w*(box//w)
        cs = w*(box%w)
        return [(i, j) for i in range(rs, rs+w) for j in range(cs, cs+w)]
    def get(self, row, col):
        return self.board[self.idx(row, col)]
    def set(self, row, col, val):
        self.board[self.idx(row, col)] = val
    def complete(self):
        return self.filled() and self.valid()
    def filled(self):
        return not 0 in self.board
    def valid(self):
        for i in range(self.size):
            if not self.rowValid(i): return False
            if not self.colValid(i): return False
            if not self.boxValid(i): return False
        return True
    def rowValid(self, row):
        s = self.size
        for i in range(s):
            for j in range(s):
                if i == j:
                    continue
                if self.get(row, i) == self.get(row, j):
                    return False
        return True
    def colValid(self, col):
        s = self.size
        for i in range(s):
            for j in range(s):
                if i == j:
                    continue
                if self.get(i, col) == self.get(j, col):
                    return False
        return True
    def boxValid(self, box):
        s = self.size
        w = self.width
        rs = w*(box//w)
        cs = w*(box%w)
        for i in range(rs, rs+w):
            for j in range(cs, cs+w):
                for m in range(rs, rs+w):
                    for n in range(cs, cs+w):
                        if i == m and j == n:
                            continue
                        if self.get(i, j) == self.get(m, n):
                            return False
        return True
    def toCSP(self, constructor):
        variables = list(range(len(self.board)))
        domains = dict()
        for v in variables:
            if self.board[v]:
                domains[v] = [self.board[v]]
            else:
                domains[v] = list(range(1,self.size+1))
        constraints = list()
        for row in range(self.size):
            c = csp.AllDiffConstraint([self.idx(row, col) for col in range(self.size)])
            constraints.append(c)
        for col in range(self.size):
            c = csp.AllDiffConstraint([self.idx(row, col) for row in range(self.size)])
            constraints.append(c)
        for box in range(self.size):
            c = csp.AllDiffConstraint([self.idx(row, col) for (row, col) in self.boxIdx(box)])
            constraints.append(c)
        return constructor(variables, domains, constraints)
    def __str__(self):
        s = self.size
        t = '+--'*s + '+\n'
        for i in range(s):
            for j in range(s):
                t += '|%2d' % (self.get(i, j),)
            t += '|\n' + '+--'*s + '+\n'
        return t
    def __repr__(self):
        return str(self)
    def __eq__(self, other):
        return self.size == other.size and self.board == other.board

def cspNumChecks(board, constructor):    
    problem = board.toCSP(constructor)
    try:
        (mapping, checks) = problem.solveWithCount()
        return str(checks)
    except csp.SolutionNotFound as e:
        return str(e)
    except csp.MaxDepthExceeded as e:
        return str(e)

if __name__ == "__main__":
    inputs = ['4x4', '9x9', '16x16', '25x25']
    for f in inputs:
        fname = "boards/mandatory/%s.sudoku" % (f,)
        board = Board(filename=fname)
        print("Test File:", f)
        print("Board:")
        print(board)
        print("Backtracking Checks:", cspNumChecks(board, csp.BacktrackingSolver))
        print("Arc Consistency Checks:", cspNumChecks(board, csp.ArcConsistencySolver))
        print("Forward Checking Checks:", cspNumChecks(board, csp.ForwardCheckingSolver))
            
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.