#!/usr/bin/env python

# Copyright (c) 2005-2008, Simon Budig

import urllib, re
from math import log

class Sudoku (object):
   def __init__ (self, txt=None):
      self.board = [0] * 81
      self.can_hold = [2**10-2] * 81
      self.has_vals = [0] * 27  # 9 rows, 9 columns, 9 blocks

      if txt:
         txt = txt.replace ("+", "")
         txt = txt.replace ("-", "")
         txt = txt.replace ("|", "")
         txt = txt.replace (".", "0")
         content = [int (i) for i in txt.split ()]
         if len (content) != 81:
            raise TypeError, "unrecognized koordinate for board constructor"
         for row in range (9):
            for col in range (9):
               index = row * 9 + col
               value = content[index]
               if value:
                  self.set (index, value)


   # a group of fields (rows, columns, blocks)
   def groupindexes (self, group):
      if group < 9:
         row = group
         return "Row %c" % (row+ord('a')), [i + row * 9 for i in range (9)]
      if group < 18:
         col = group - 9
         return "Column %d" % (col+1), [i * 9 + col for i in range (9)]
      if group < 27:
         block = group - 18
         brow, bcol = divmod (block, 3)
         return "Block %d" % (block+1), [brow * 3 * 9 + bcol * 3 + i * 9 + j
                                          for i in range(3) for j in range (3)]
      raise TypeError, "illegal group id (must be 0 - 26)"


   def __str__ (self):
      ret = ""
      ret += "      1 2 3   4 5 6   7 8 9  \n"
      ret += "    +-------+-------+-------+\n"
      for i in range (3):
         for j in range (3):
            ret += ("  %s | %d %d %d | %d %d %d | %d %d %d |\n" %
                    ((chr (ord ("a") + i * 3 + j),) +
                     tuple (self.board [i*27+j*9:i*27+j*9+9])))
         ret += "    +-------+-------+-------+\n"
      return ret.replace ("0", ".")[:-1]


   def set (self, index, value):
      row, col = divmod (index, 9)
      block = (row / 3) * 3 + (col / 3)

      if value < 0 or value > 9:
         raise TypeError, "value must be an int in the range from 1 to 9"

      if self.board [index] == value:
         return

      if self.board [index] != 0:
         raise RuntimeError, ("index %d (%d,%d) already occupied" %
                              (index, row, col))
      coverage = (self.has_vals[row] |
                  self.has_vals[col + 9] |
                  self.has_vals[block + 18])

      if coverage & 2**value:
         raise RuntimeError, ("index %d (%d,%d) can no longer hold value %d" %
                              (index, row, col, value))

      self.board [index] = value
      self.has_vals[row]        |= 2**value
      self.has_vals[col + 9]    |= 2**value
      self.has_vals[block + 18] |= 2**value

      for i in self.groupindexes (row)[1]:
         self.can_hold [i] &= 2**10-1 - 2**value

      for i in self.groupindexes (col+9)[1]:
         self.can_hold [i] &= 2**10-1 - 2**value

      for i in self.groupindexes (block+18)[1]:
         self.can_hold [i] &= 2**10-1 - 2**value

      self.can_hold [index] = 0


   def is_solved (self):
      return self.board.count (0) == 0

   def search (self):
      def ind2coo (index):
         row, col = divmod (index, 9)
         return chr (ord ('a') + row) + chr (ord ('1') + col)

      def ind2grp (index):
         row, col = divmod (index, 9)
         block = (row / 3) * 3 + (col / 3)
         return row, col, block

      ret = []

      # looking for numbers that have exactly one legal position in a group
      for group in range (27):
         groupname, idx = self.groupindexes (group)
         for number in range (1,10):
            if self.has_vals[group] & 2**number == 0:
               positions = []
               for i in range (9):
                  if self.can_hold [idx[i]] & 2**number:
                     positions.append (idx[i])

               if len (positions) == 1:
                  action = (positions[0], number)
                  if not action in ret:
                     print ("%10s: %s = %d" % (groupname,
                                               ind2coo (positions[0]), number))
                     ret.append ((positions[0], number))

      if ret:
         return ret

      # Looking for cells with exact one legal number
      for i in range (81):
         if self.board[i]:
            continue

         row, col, block = ind2grp (i)

         coverage = (self.has_vals[row] |
                     self.has_vals[col + 9] |
                     self.has_vals[block + 18])
         candidates = (2**10-2 - coverage) & self.can_hold[i]

         if candidates == 0:
            print "oops, no possibilities for index %d (%d,%d)", i, row, col

         l = log (candidates) / log(2)
         if abs (l - int (l)) < 0.00001:
            print "Field %s can only have value %d" % (ind2coo(i), int(l))
            ret.append ((i, int(l)))

      if ret:
         return ret

      bak = self.can_hold[:]

      # Looking for additional restraints for numbers
      for group in range (27):
         groupname, idx = self.groupindexes (group)
         for value in range (1,10):
            if self.has_vals[group] & 2**value == 0:
               # value not yet in this group
               rows = []
               cols = []
               blocks = []
               for i in range (9):
                  if self.can_hold [idx [i]] & 2**value:
                     positions.append (idx [i])
                     row, col, block = ind2grp (idx [i])
                     if row not in rows:
                        rows.append (row)
                     if col not in cols:
                        cols.append (col)
                     if block not in blocks:
                        blocks.append (block)

               # active groups intersecting with the current group:
               actgrps = []
               if len (rows) == 1 and rows[0] != group:
                  actgrps.append (rows[0])
               if len (cols) == 1 and cols[0] != group:
                  actgrps.append (cols[0] + 9)
               if len (blocks) == 1 and blocks[0] != group:
                  actgrps.append (blocks[0] + 18)
               
               for actgrp in actgrps:
                  chb = self.can_hold[:]
                  actname, actidx = self.groupindexes (actgrp)
                  for i in actidx:
                     if i not in idx:
                        self.can_hold[i] &= 2**10-1 - 2**value
                  if self.can_hold != chb:
                     print ("%s requires value %d in %s" %
                            (groupname, value, actname))

      if not bak == self.can_hold:
         return ret

      bak = self.can_hold[:]

      # TODO: Noch zu suchende pattern:
      # p1: 2,3; p2: 3,4; p3 = 2,3,4
      # Verodern von moeglichen Plaetzen

      # Looking for "closed groups" of fields in a group
      # (e.g. 2 fields that can hold the same two values, preventing
      # other fields to hold these numbers)

      for group in range (27):
         groupname, idx = self.groupindexes (group)
         combos = {}
         for i in idx:
            if self.board[i] > 0:
               continue
            ch = self.can_hold [i]
            if combos.has_key (ch):
               combos[ch].append (i)
            else:
               combos[ch] = [i]
         for ch, cand in combos.items ():
            if len (cand) <= 1:
               continue
            ch_cand = 0
            for i in cand:
               ch_cand |= self.can_hold [i]

            if ch_cand == ch:
               bitcount = 0
               for value in range (1,10):
                  if ch & 2**value:
                     bitcount += 1
               if len (cand) == bitcount:
                  chb = self.can_hold[:]
                  for i in idx:
                     if i not in cand:
                        self.can_hold [i] &= 2**10-1 - ch
                  if self.can_hold != chb:
                     print ("Matching fields in %s: only %s can contain %s" %
                            (groupname, [ind2coo (i) for i in cand],
                             [value for value in range(1,10) if 2**value & ch]))
                        
      if not bak == self.can_hold:
         return ret

      bak = self.can_hold[:]

      # Looking for "closed groups" of values in a group
      # (e.g. 2 values that can only be in the same two fields, preventing
      # other values to be stored in these fields)

      for group in range (27):
         groupname, idx = self.groupindexes (group)
         combos = {}
         places = [0] * 10
         for value in range (1,10):
            if self.has_vals [group] & 2**value:
               continue
            places[value] = 0
            for i in range (9):
               if self.can_hold [idx[i]] & 2**value:
                  places[value] |= 2**i
            if combos.has_key (places[value]):
               combos[places[value]].append (value)
            else:
               combos[places[value]] = [value]

         for plcs, cand_vals in combos.items ():
            if len (cand_vals) <= 1:
               continue
            plcs_cand = 0
            for i in cand_vals:
               plcs_cand |= places [i]

            if plcs_cand == plcs:
               bitcount = 0
               for place in range (9):
                  if plcs & 2**place:
                     bitcount += 1
               if len (cand_vals) == bitcount:
                  chb = self.can_hold[:]
                  num_mask = 0
                  for value in cand_vals:
                     num_mask |= 2**value
                  for place in range (9):
                     if plcs & 2**place:
                        self.can_hold [idx[place]] &= num_mask
                  if self.can_hold != chb:
                     print ("Matching numbers in %s: %s can only be in %s" %
                            (groupname, cand_vals,
                             [ind2coo(idx[place]) for place in range(9)
                                      if 2**place & plcs]))
                        
      
      return ret



def retrieve_websudoku (level = 4, id = ""):
   def foo (stuff):
      if stuff == None:
         return "0"
      else:
         return stuff.group (1)

   f = urllib.urlopen ("http://play.websudoku.com/",
                       "level=%d&set_id=%s" % (level, id))
   html = f.read ()
   f.close ()

   inputs = re.findall ("<INPUT.[^>]*>", html)
   board = [foo (re.search ("VALUE=\"([1-9])\"", i)) for i in inputs[:81]]

   for i in inputs[81:]:
      type = re.search ("NAME=([^ ]*)", i)
      if type != None:
         type = type.group (1)
      if type == "id":
         id = re.search ("VALUE=\"([^\"]*)\"", i).group (1)
      if type == "level":
         level = int (re.search ("VALUE=\"([^\"]*)\"", i).group (1))
         
   print "http://play.websudoku.com/?level=%d&set_id=%s" % (level, id)

   return Sudoku (" ".join (board))


txt = """
  +-------+-------+-------+
  | . . . | 3 . . | 6 9 . |
  | . . 3 | . . . | . 5 . |
  | . . . | 6 . . | . . 2 |
  +-------+-------+-------+
  | 5 . . | 4 9 . | . . . |
  | . 8 7 | . 1 . | 9 2 . |
  | . . . | . 6 2 | . . 7 |
  +-------+-------+-------+
  | 1 . . | . . 4 | . . . |
  | . 7 . | . . . | 3 . . |
  | . 2 8 | . . 5 | . . . |
  +-------+-------+-------+
"""

# http://play.websudoku.com/?level=4&set_id=2205114969

if __name__=='__main__':
   # b = retrieve_websudoku (4, 2205114969)
   # b = retrieve_websudoku (4, 2574113934)
   b = retrieve_websudoku (4)
   # print repr (b.board)
   fill = [1]
   while not b.is_solved():
      print
      print b
      fill = b.search ()
      if 0 and raw_input ():
         print
         for row in range (9):
            for col in range (9):
               if not b.board[row*9+col]:
                  print "(%d,%d):" % (row, col),
                  for i in range (1, 10):
                     if b.can_hold[row*9+col] & 2**i:
                        print i,

                  print

      for index,value in fill:
         b.set (index, value)

   print
   print b