Pastebin

import math
import sys
import time
from random import random
from collections import defaultdict
from logger import *
start_time = time.time()

def usage():
    print """Usage: %s <file> <size> [reverse]
    
    Examples:
        %s puzzle-tiny.txt 4
        %s puzzle-small.txt 9
        %s puzzle.txt 16 reverse
""" % (sys.argv[0], sys.argv[0], sys.argv[0], sys.argv[0])

def cputime():
    import resource
    return (resource.getrusage(resource.RUSAGE_SELF).ru_utime + 
            resource.getrusage(resource.RUSAGE_SELF).ru_stime)

class Row:
    def __init__(self, pos, cells=[]):
        self.pos = pos
        self.cells = cells

    def __str__(self):
        return "Row(p:%s, %s)" % (self.pos, self.cells)

    def __repr__(self):
        return str(self)

class Cell:
    def __init__(self, pos, value, square, row):
        self.pos = pos
        self.value = value
        self.square = square
        self.row = row
    
    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return "C(p:%s,val:%s,sq:%s)" % (self.pos, self.value, self.square)

class Node:
    #def __init__(self, pos, queue, value, depth):
    def __init__(self, queue, value, depth):
        #self.pos = pos
        self.queue = queue
        self.value = value
        self.depth = depth
    def __str__(self):
        return repr(self)

    def __repr__(self):
        return "N(p:%s, val:%s, d:%s)" % (self.pos, self.value, self.depth)


def load(filename, size):
    """Global function to load a sudoku puzzle from a file"""
    row_num, cell_num = 1, 1
    rows = []
    row_vals = defaultdict(dict)
    col_vals = defaultdict(dict)
    square_vals = defaultdict(dict)
    square_size = int(math.sqrt(size))

    # Load rows
    for line in open(filename).readlines():
        line = line.strip()
        debug("line: %s  row_num: %s" % (line, row_num))
        cells = []
        row = Row(row_num)
        pos = 0
        rd = math.ceil(float(row_num)/float(square_size))
        # Load the cells in each row
        for cell in line.strip().split(","):
            debug("cell: %s, cell_num: %s, pos: %s" % (cell, cell_num, pos))
            cd = math.ceil(float(pos+1)/float(square_size))
            square_num = int((rd-1)*square_size+cd)
            debug("square_num: %s" % square_num)
            cell_value = int(cell)
            cells.append(Cell(pos, cell_value, square_num, row))
            # remember which cells that have already been given a value
            if cell_value:
                row_vals[row_num][cell_value] = 1
                col_vals[pos][cell_value] = 1
                square_vals[square_num][cell_value] = 1
            pos += 1
            cell_num += 1
        row.cells = cells
        rows.append(row)
        row_num += 1

    return (rows, row_vals, cells, col_vals, square_vals)

stat_depth = 0
def expand(parent):
    """Returns true if problem is solved, expands the given node otherwise"""
    global queue, num_blanks, cur_node_pos, SIZE

    # Statistics begin
    global stat_depth, rows, num_expanded
    num_expanded += 1
    if parent.depth + 1 > stat_depth: 
        stat_depth = parent.depth + 1
        info("stat_depth: %s, num_blanks: %s, num_expanded: %s" % (stat_depth, num_blanks, num_expanded))
        pp(rows, SIZE)
    # Statistics end

    if not parent.depth + 1 > num_blanks - 1:
        children = []
        for i in range(SIZE):
            cur_node_pos += 1
            #children.append(Node(cur_node_pos, queue, i + 1, parent.depth + 1))
            children.append(Node(queue, i + 1, parent.depth + 1))
        if do_reverse:
            children.reverse()
        for child in children:
            queue.append(child)
    else:
        return True

try: 
    import psyco
    psyco.full()
    print "Using psyco specializing compiler"
except ImportError: 
    print "Psyco not available"
    pass

if len(sys.argv) < 3:
    error("Not enough parameters")
    usage()
    sys.exit(1)

if len(sys.argv) > 3:
    do_reverse = True
    info("reverse: on")
else:
    do_reverse = False
    info("reverse: off")

puzzle_file = sys.argv[1]
SIZE = int(sys.argv[2])

## INITIALIZATION
# Current node's position
cur_node_pos = 0

# Current depth starts on zero
cur_depth = 0

# Number of expanded nodes so far
num_expanded = 0

# Load rows from file
(rows, row_vals, cells, col_vals, square_vals) = load(puzzle_file, SIZE)

# Show the loaded puzzle
pp(rows, SIZE)

# list of empty cells
blanks = []
for row in rows:
    for cell in row.cells:
        if not cell.value:
            blanks.append(cell)
num_blanks = len(blanks)

#queue = Queue()
queue = []

# Create root node and expand it
root = Node(queue, 0, -1)
expand(root)

while queue:
    # Get next node from the queue
    cur_node = queue.pop()

    # Set value to current node's value
    value = cur_node.value

    # Set depth to the current node's depth
    node_depth = cur_node.depth

    cell        = blanks[node_depth]
    cell_row    = cell.row.pos
    cell_col    = cell.pos
    cell_square = cell.square

    for i in range(node_depth, cur_depth + 1):
        cur         = blanks[i]
        cur_row     = cur.row.pos
        cur_col     = cur.pos
        cur_square = cur.square
        if cur.value:
            del row_vals[cur_row][cur.value]
            del col_vals[cur_col][cur.value]
            del square_vals[cur_square][cur.value]
            cur.value = 0

    cur_depth = node_depth

    if not (row_vals[cell_row].has_key(value) or
        col_vals[cell_col].has_key(value) or
        square_vals[cell_square].has_key(value)):

        cell.value = value
        finished = expand(cur_node)

        if finished:
            info("FINISHED")
            pp(rows, SIZE)
            break

        row_vals[cell_row][value]       = 1
        col_vals[cell_col][value]       = 1
        square_vals[cell_square][value] = 1
    else:
        debug("Value: %s is already used" % value)


    #for r in cur_node.queue:
    #    print map(repr, [r.value, r.pos, r.depth])

    del cur_node

pp(rows, SIZE)

info("Expanded nodes: %s" % num_expanded)

info("CPU time used: %s" % cputime())
log("Time used: %s" % (time.time() - start_time), INFO)