Kakuro Solver

#!/usr/bin/python
# -*- coding: windows-1251 -*-
from types import *


class Kakuro:
   # таблица с какурой
   _table=None
   # группы
   _groups=None
   # размеры таблицы
   _lines = 0
   _columns = 0

   # Таблица возможных слагаемых
   # в виде _sum_variants[число слагаемых][сумма] = [ вариант1, вариант2 ... ]
   _sum_variants = None

   # Исключения
   class KakuroException(Exception): pass
   class ParseException(KakuroException): pass
   class SolveMaxIteration(KakuroException): pass

   def to_string(self):
      ''' Возвращает какуро в читабельном виде '''
      if self._table==None:
         return ''

      result=''
      for line in self._table:
         for cell in line:

            cell_text=''
            assert ( type(cell) == TupleType and len(cell) == 2 ) or cell=='#' or isinstance(cell, Cell)

            if cell=='#':              # серая клетка
               cell_text = '###'
            elif isinstance(cell, Cell):   # ячейка
               if len(cell) == 9:
                  cell_text = '.'
               else:
                  cell_text = cell
            elif type(cell) == TupleType and len(cell)==2:   # начало группы
               cell_list = list(cell)
               cell_list = map(lambda x: str(x) if x != 0 else '##', cell_list)
               cell_text += '\\'.join(cell_list)
            else:
               pass
               #raise TypeError('unexpected cell type (%s)' % cell)

            result += '{:^23}'.format(cell_text)
         result += '\n'

      return result[:-1]   # удаляем завершающий перенос строки



   def parse(self, text):
      ''' Чтение какуры из строки
      @type text: string
      @param text: строковое представление какуры

      @raise ParseException
      '''
      table=[]
      lines=text.split('\n');
      for line in lines:
         # разбиваем по пробелам
         nodes=line.split()

         # пропускаем пустые строки
         if len(nodes)==0:
            continue

         # добавляем строку
         table.append([])

         for node in nodes:

            if node[0]=='.':
               table[-1].append(Cell())
            elif node[0]=='#':
               table[-1].append('#')
            else:
               pieces=node.split('\\')
               if len(pieces)==2:   # значит ячейка с суммой блока
                  table[-1].append((self._to_int(pieces[0], 0) , self._to_int(pieces[1], 0)))
               else:                # пробуем получить числовое значение
                  number=self._to_int(node)
                  if number==None:
                     raise Kakuro.ParseException('except number (%s)' % node)
                     #raise ValueError('except number (%s)'%node)
                  else:
                     table[-1].append(Cell(number))

      self._table = table

      self._lines = len(table)   # количество строк
      self._columns = len(table[0]) # по длине первой строка

      self._groups = None

   def solve(self):
      if self._sum_variants == None:
         self._get_sum_variants()

      if self._groups == None:
         self._get_groups()

      table_changed = True

      iteration = 0
      max_iterations = 500

      while table_changed:
         iteration += 1

         print '\n',self

         if iteration >= max_iterations: raise self.SolveMaxIteration()

         table_changed = False
         for i,group in enumerate(self._groups):

            if group.solved():
               continue

            group.solve()

            table_changed |= group.changed()

   def _get_sum_variants(self):
      ''' Генерирует таблицу вариантов сумм '''
      variants = {}

      for n in range(1,10):      # n - длина блока (количество слагаемых)
         # Генерируем первую группу слагаемых
         # Так как слагаемые повторяться не могут, первая группа будет иметь вид 1, 2, 3, ... n
         summands = range(1,n+1);
         # создаём коллекцию для текущей длины групп
         variants[n] = {}

         # флаг, что все варианты для текущего n перебраны
         next_n = False

         while not next_n:
            group_sum = sum(summands)

            if not group_sum in variants[n]:
               variants[n][group_sum] = []

            # помещаем в группу с суммой текущий вариант разложения
            variants[n][group_sum].append(tuple(summands))


            # Рассчитываем следующий вариант разложения
            # Для этого пробегаемся по слагаемым с конца, прибавив к последнему единицу
            # Если значение слагаемого больше, чем 10 - n + i, то прибавляем цифру к порядку старше
            # Так например для группы из 5ти слагаемых _ _ _ _ _, начальная группы будет 1 2 3 4 5,
            # а последняя 5 6 7 8 9, и в позиции 2 не может быть больше семёрки (7)
            # i - индекс слагаемого
            for i in range(n-1,-2,-1):
               if i==-1:
                  next_n=True
                  break

               # прибавляем единицу в текущем порядке
               summands[i]+=1
               # если это число здесь может быть, то последующие цифры будут последовательными, т.е
               # если 1 3 _ _ _, , тройка быть может (10 - 5 + 1 = 6 >= 3), значит следующие цифры: 1 3 4 5 6
               if summands[i] <= 10-n+i:
                  summands[i+1:] = range( summands[i]+1 ,10)[:n-i-1]
                  break

      self._sum_variants = variants


   def _get_groups(self):
      ''' Получить группы из таблицы '''
      groups = []
      for line_index,line in enumerate(self._table):
         for column_index,cell in enumerate(line):

            if type(cell) == TupleType and len(cell)==2:   # найдён начало блока
               for i,sum in enumerate(cell):
                  if sum != 0:
                     groups.append( self._get_group( line_index, column_index, sum, bool(i) ) )

      self._groups = groups

   def _get_group(self,line,column,sum,horizontal=False):
      ''' Получить группу по координатам начальной ячейки
      @type line: int
      @param line: Номер строки
      @type column: int
      @param columns:  Номер столбца
      @type sum: int
      @param sum: Сумма группы
      @type horizontal: bool
      @param horizontal: Группа горизонтальная
      @rtype: Group
      @return: Группа
      '''
      cells = []

      if horizontal: # горизонтальное направление
         cols_range = range(column + 1,self._columns)
         lines_range = [line] * len(cols_range)
      else:    # вертикальное
         lines_range = range(line + 1,self._lines)
         cols_range = [column] * len(lines_range)

      coords = zip(lines_range,cols_range)
      for line,column in coords:
         cell=self._table[line][column]

         if cell=='#' or type(cell) == TupleType:  # конец группы
            break

         cells.append(cell)

      return Group(sum,cells, self._sum_variants[len(cells)][sum] )

   def _to_int(self, value, default_value = None):
      """ конвертирование строки в целое число
      @type value: string
      @param value: строковое представление числа
      @type default_value: variable
      @param default_value: значение, при ошибке конвертирования [None]
      @rtype: int | type(default_value)
      @return: число или default_value
      """
      try:
         result=int(value)
      except ValueError:
         result=default_value
      finally:
         return result

   def __repr__(self):
      return self.to_string()

class Group:
   # Коллекция ячеек
   _cells = None
   # Сумма группы
   _sum = 0
   # Варианты сумм
   _sum_variants = None
   # Отгаданные цифры
   _solved_digits = None
   # Цифры, которых нет в группе
   _invalid_digits = None

   # Изменена ли группа
   _changed = False

   def __init__(self,sum,cells,sum_variants):
      self._sum = sum
      self._cells = tuple(cells)
      self._sum_variants = map(lambda group: Digits(group), sum_variants)
      self._solved_digits = Digits([])
      self._invalid_digits = Digits([])

   def solve(self):
      self._invalid_digits = Digits()

      for cell in self._cells:
         # собираем отгаданные
         if cell.solved():
            self._solved_digits += cell

         # убираем из невозможных, возможные в текущей ячейка. В конце останутся невозможные вообще
         self._invalid_digits -= cell


      # отсеиваем варианты
      self._filter_sum_variants()

      assert len(self._invalid_digits) != 9

      # из отсавшизся вариантов получаем невозможные цифры
      self._invalid_digits += self._select_invalid_digits()

      assert len(self._invalid_digits) != 9

      # изменение ячеек
      self._changed = False
      for cell in self._cells:
         if cell.solved(): continue

         # убираем из ячейки невозможные цифры
         cell -= self._invalid_digits
         # и уже отгаданные в этой группе
         cell -= self._solved_digits

         self._changed |= cell.changed()

   def solved(self):
      ''' Решена ли группа '''
      return len(self._solved_digits) == len(self._cells)

   def changed(self):
      ''' Изменелась ли группа '''
      return self._changed

   def _filter_sum_variants(self):
      ''' Оставляем варианты которые содержат все разгаданные слагаемые и не содержат ниодного недопустимого слагаемого '''
      self._sum_variants = filter(lambda summands: self._solved_digits - summands == [] and summands & self._invalid_digits == [], self._sum_variants)

   def _select_invalid_digits(self):
      ''' отсеиваем цифры, которые не могут быть в любом из возможных вариантов '''

      # отсеиваем цифры, которые не могут быть в любом из возможных вариантов
      invalid = Digits()

      # нет ни в одной группе слагаемых
      for summands in self._sum_variants:
         invalid -= summands

      return invalid

   def __repr__(self):
      result =  'Group ({sum}):'.format(sum=self._sum)
      if self.solved():
         result += '\n\tSOLVED'
      result += '\n\tsolved=' + str(self._solved_digits)
      result += '\n\tinvalid=' + str(self._invalid_digits)

      for i,cell in enumerate(self._cells):
         result += '\n\t\t'+str(i+1)+'. ' + str(cell)

      return result

class Menu(object):
   ''' Реализует многоуровневое консольное меню '''
   # Шаблон меню, title - Заголовок меню/подменю, items - пункты
   menu_template = "\n --- {title:^13} --- \n{items}"
   # Разделитель пунктов меню
   items_delimiter = '\n'
   # Шаблон пункта меню index - номер пункта, title - заголовок
   items_template = "{index}. {title}"
   # Приглашение ввода:
   prompt = "Input item index: "
   # Заголовок  меню
   menu_title = 'Menu'
   # Текст пункта меню «наверх» (пункт скрыт, если None)
   back_title = None
   # Текст пункта выход (пункт скрыт, если None)
   exit_title = None


   # Структура меню
   _struct = None
   # Активная позиция
   _active_position = 0
   # Заголовок активного меню
   _active_title = None
   # Активное подменю
   _submenu = None


   def __init__(self,struct):
      if type(struct) != TupleType:
         raise TypeError('type of struct must be a tuple (%s)' % type(struct))

      self._struct = struct
      self._submenu = struct
      self._active_position = 0
      self._active_title = self.menu_title

   def select(self,num,execute=True):
      ''' Выбор пункта меню
      @num: (int) Выбираемая позиция
      @execute: (bool) Выполнить, если выбранный элемент это функция или выбросить исключение
      '''
      if num==0:
         self.position = self.position/10    # Сдвигаем на порядок
      else:
         index = num-1
         item = self._submenu[index]
         if type(item[1]) == TupleType: # если второй элемент - это список
            self._active_title = item[0]
            self._submenu = item[1]
            self._active_position = self._active_position*10 + num
         elif execute:                 # в противном случае это функция, выполняем если разрешено
            self._call_func(item[1],item[2:])   # выполняем функцию (item[1]) с параметрами item[2:]
         else:
            raise Exception('except sumbenu element in %s' % self._active_position*10+num)  # а значит ожидается подменю


   @property
   def position(self):
      return self._active_position

   @position.setter
   def position(self,position):
      ''' Устанавливает текущую позицию в меню относительно корня'''
      if type(position) != IntType:
         raise TypeError('type of position must be a int (%s)' % type(position))

      # получаем подменю по индексам
      submenu = self._struct

      if position>0:
         position = str(position)   # переводим в строку, чтобы получать посимвольно
         position = filter(lambda c: c != '0',position) # удаляем нулевые элементы
         for i,level in enumerate(position):
            index = int(i)-1
            self.select(index,  level == len(position) - 1 ) # level == len(position) - 1 - элемент находится в конце позиции, значит выполняем его
      else:
         self._active_position = 0
         self._active_title = self.menu_title

      self._submenu = submenu

   def show(self,position=None):
      ''' Показать меню в текущей или заданной позиции
      @position: (int) задать позицию
      '''
      if position!=None:
         self.position = position

      items = []
      for index,menu_item in enumerate(self._submenu):
         items.append( self.items_template.format(index=index+1,title=menu_item[0]) )

      # Активно подменю
      if self.position > 0 and self.back_title != None:
         items.append(self.items_template.format(index=0,title=self.back_title))
      elif self.exit_title != None:
         items.append(self.items_template.format(index='Q',title=self.exit_title))

      print self.menu_template.format( title=self._active_title, items=self.items_delimiter.join(items) )


   def activate(self):
      ''' Активация интерактивного меню '''
      self.show()
      while True:
         pos = raw_input(self.prompt)

         # выход, если введено 'q'
         if pos=='q':
            break
         # повторный вывод меню, если пустой ввод
         if pos=='':
            self.show()
            continue

         try:
            pos = int(pos)
         except ValueError:
            continue

         try:
            self.select(pos)
         except:
            continue

         self.show()



   def _call_func(self,func,args):
      ''' Вызов функции с агрументами в виде списка '''
      func(*args)

class Cell:
   # допустимые цифры
   _digits=None

   # результат последней операции
   _last_operation_change=False

   def __init__(self, value = None):
      self._digits = Digits(value)
      self._test_numbers()

   def __repr__(self):
      ' вывод ячейки на печать '
      if len(self._digits)==1:
         return str(self._digits.list()[0])
      else:
         return str(self._digits)

   def __add__(self, values):
      ' операция + '
      old = self._digits

      self._digits += values

      self._last_operation_change = old == self._digits
      self._test_numbers()
      return self

   def __sub__(self, values):
      ' операция - '
      old = self._digits

      self._digits -= values

      self._last_operation_change = old == self._digits
      self._test_numbers()
      return self

   def __eq__(self, other):
      ' оператор == '

      if isinstance(other, Digits):
         return self._digits==other
      elif isinstance(other, Cell):
         return self._digits==other._digits
      else:
         return self._digits==other

   def __len__(self):
      return len(self._digits)

   def solved(self):
      ' Решена ли ячейка'
      return len(self._digits)==1

   def changed(self):
      ''' Изменена ли ячейка последней операцией '''
      return self._last_operation_change

   def clone(self):
      ' Клонирование (копирование) ячейки '
      return Cell(self._digits)

   def copy(self):
      ' Клонирование (копирование) ячейки '
      return self.clone()

   def max(self):
      ' Максимальное допустимое число '
      return max(self._digits)

   def min(self):
      ' Минимальное допустимое число '
      return min(self._digits)

   def digits(self):
      ''' Получить цифры ячейки '''
      return self._digits

   def _test_numbers(self):
      ' Проверка ячейки на пустоту. Если пуста, выбрасывается исключение '
      if len(self._digits)<1:
         raise Exception('error, empty cell')

class Digits:
   '''
   Набор цифр 1-9. Реализованы операции сложения и вычтания
   '''
   _digits=[]


   def list(self):
      ' Возвращает список цифр'
      return self._digits

   def __init__(self, value = None):
      """ Инициализация класса
      @param value: цифра или список цифр
      """

      if type(value)==TupleType:
         value=list(value)

      if value==None:
         self._digits=range(1, 10)
      elif type(value) == IntType:
         self._digits=[value]
      elif type(value) == ListType:
         self._digits=self._test_values(value)
      else:
         raise ValueError('except int or list of ints(%s)'%type(value))

   def __repr__(self):
      ' на печать '
      self._digits.sort()
      return str(self._digits)


   def __add__(self, values):
      ' операция + '
      values = self._test_values(values)

      result = self._digits + values

      # удаляем повторяющиесы числа
      result=list(set(result))

      return Digits(result)

   def __and__(self,values):
      ' операция & - пересечение'
      values=self._test_values(values)

      result = list( set(self._digits) & set(values) )

      return Digits(result)

   def __or__(self,values):
      ' операция | - объединение'
      values=self._test_values(values)

      result = list( set(self._digits) | set(values) )

      return Digits(result)

   def __xor__(self,values):
      ' операция ^ - инвертированное пересечение (обединение, без общей части)'
      values=self._test_values(values)

      result = list( set(self._digits) ^ set(values) )

      return Digits(result)

   def __sub__(self, values):
      ' операция - '
      values=self._test_values(values)

      result = list(set(self._digits)-set(values))

      return Digits(result)

   def __eq__(self, other):
      ' оператор == '

      if isinstance(other, Digits):
         return self._digits==other._digits

      if type(other) != ListType:
         other=[other]
      else:
         # если передан список, то удаляем дубликаты и сортируем
         other=list(set(other))

      return self._digits==other

   def __invert__(self):
      ' инвертирование (~) '
      result = list(set(range(1, 10)) - set(self._digits))
      return Digits(result)

   def __len__(self):
      ' количество возможных цифр '
      return len(self._digits)

   def __contains__(self, num):
      ' оператор in '
      return num in self._digits

   def _test_values(self, values):
      ''' Проверка значения для операций.
      @param values: значение list или int или Digits или Cell
      @return: список значений
      @rtype: list
      '''
      # если параметр не список, то оборачиваем его
      if isinstance(values, Cell):
         values = values.digits().list()
      elif isinstance(values, Digits):
         values = values.list()
      elif type(values) == TupleType:
         values = list(values)
      elif type(values) != ListType:
         values = [values]

      values = list(set(values))
      for val in values:
         if type(val) != IntType:
            raise TypeError('value must be a int (%s)' % type(val))
         if val<1 or val>9:
            raise ValueError('value out of range 1...9 (%i)'%val)

      return values

'''
# Digits и Cell тесты
c = Cell()
d = Digits()
c_copy = c
print 'd: ',d
print 'c: ',c
print

c -= [1,2,3]
d -= [1,2,3]
print 'd: ',d
print 'c: ',c
print 'c2:',c_copy
print

~d
~c
print 'd: ',d
print 'c: ',c
print 'c2:',c_copy
print

d -= [4,2,9]
c -= [4,2,9]
print 'd: ',d
print 'c: ',c
print 'c2:',c_copy
print

d_copy = d
d += ~d
c += Digits([3,2,5,2,6,8])
print 'd: ',d
print 'd2: ',d_copy
print 'c: ',c
print 'c2:',c_copy
print Digits([1,5,3,1,1,1,1,1,1])
'''

'''
# Menu тесты
def action(val):
   print 'do action %s' % val


menu = Menu((
               ('Submenu 1',(
                    ('Item 1',action,1),
                    ('Item 2',action,2)
               )),
               ('Submenu 2',(
                    ('Action 3',action,3),
                    ('Action 4',action,4),
                    ('Action 5',action,5),
               )),
               ('Main action',action,'main')
             ))
menu.back_title = 'Back'
menu.exit_title = 'Quit'
menu.activate()
'''


# Kakuro тесты
kak = Kakuro()
f = open("kak1.txt",'r')
kak.parse(f.read())

kak.solve()
print kak