Размещено на http://www.allbest.ru/

19

Размещено на http://www.allbest.ru/

Оглавление

концептуальная модель задача программа

• Введение
• Концептуальное модельное представление задачи как системы
• Программная реализация представления концептуальной модели задачи
• Решение задач посредством прямого расчёта
• Судоку
• Решение судоку
• Составление судоку
• Литература
• Приложение. Программный код

Введение

концептуальная модель задача программа

В настоящее время высокий уровень развития современных электронно-вычислительных средств даёт возможность быстро и эффективно решать вопросы, связанные с хранением и обработкой всевозможных видов информации, представлением данных и знаний в удобных для пользователя и понятных для компьютера формах. Подобные возможности реализуются посредством эффективного применения баз данных и хранилищ данных, а также автоматизированных, электронных и интеллектуальных систем. Растущие потребности человечества порождают все более сложные в качественном и количественном аспектах задачи, решение которых зачастую определяет прогресс общества.

В ходе данной работы будет рассмотрено представление концептуальной модели задачи (КМЗ) на основе триады «Задача - Данные - Решатель» и работа одного из компонентов подобной системы - генератора вспомогательных концептуальных моделей.

В процессе выполнения данной работы была создана программа (на языке Python), позволяющая решать любые задачи, связанные с вычислениями на основе вводимых пользователем исходных данных и определяемых некоторой предметной областью, для которой заданы действительные математические формулы. Программа осуществляет поиск необходимых формул на основе вводимых пользователем данных, а затем применяет данные формулы для получения конечного результата. Кроме того, данная программа позволяет решать и составлять судоку - один из видов японских кроссвордов, составляя вспомогательные концептуальные задачи и решая их и исходную задачу на основе различных рекурсивных методов.

Особенность предлагаемого метода представления задачи как концептуальной модели имеет отличительную особенность по сравнению с классической технологией, так как исходная задача не разбивается на меньшие составные подзадачи, а происходит генерация вспомогательных задач, решая которые можно решить исходную задачу.

Далее в работе будет описано представление исходной задачи как концептуальной модели задачи, формализация задачи, а также описана практическая реализация составленной программы.

Концептуальное модельное представление задачи как системы

Деятельность человека имеет две основные формы: умственную - “деятельность мозга” и физическую - “деятельность рук”. Очевидно, что и умственная и физическая деятельность сопряжены с постоянной необходимостью решения разнообразных задач. Спектр таких задач определяется многочисленными факторами, как существенными, так и малозначимыми. К существенным факторам, прежде всего, следует отнести причины возникновения задачи. В качестве первопричины, порождающей задачу, выступают потребности человека. Удовлетворение потребностей осуществляется в процессе взаимодействия человека не только с внешней, но и с собственной внутренней средой, т.е. с природой, с другими людьми или самим собой. Реализация потребностей всегда связана с решением соответствующих этим потребностям задач. Практически весь спектр потребностей человека определяется тремя сферами его деятельности: материальной, социальной и духовной. Следовательно, можно констатировать, что возникновение задач обусловлено материальными, социальными и духовными факторами. К существенным факторам, определяющим содержание и свойства задач, следует также отнести: предметную область существования задачи, её размерность и уровень сложности, степень определенности, возможности формализации, полноту исходных данных, требования к конечному результату, а также ряд других свойств, характеристик, параметров и особенностей.

Размещено на http://www.allbest.ru/

19

Размещено на http://www.allbest.ru/

На представленном выше рисунке отражена концептуальная архитектура задачного решающего комплекса. Интеллектуальная решатель взаимодействует с концептуальной моделью, которая, в свою очередь, взаимодействует с интеллектуальными интерфейсами, посредством которых в решатель загружаются пользовательские задачи.

Концептуальная модель задачи разрабатывалась на основе методов системно-комплексного анализа (СК - анализа) “внутреннего устройства задачи”, как целостной системы, и её внешнего окружения - среды существования задачи. Для успешного разрешения проблемы создания КМЗ использовались:

системно-комплексный подход и СК-анализ;

основы теории концептуального моделирования;

методологические аспекты метамоделирования;

технология концептуального метамоделирования (КММ - технология), а также метод раскрытия неопределённости системной задачи на уровне её концептуального представления, основанный на метазадачной технологии и рекурсивных механизмах, приводящий к рекурсивным и взаимнорекурсивным структурам системной КМЗ.

Изложенный подход к созданию и использованию КМЗ по своей сути может быть определен как концептуальная метамодельная технология автоматизированного описания, представления, постановки и решения системных задач.

Многоуровневое представление концептуальной модели системной задачи осуществляется на основе метода стратификации. Для формирования страт - уровней организации задачи необходим критерий или основание стратификации. В качестве такого критерия в рассматриваемом случае целесообразно выбрать показатель неопределённости системной задачи . В соответствие с указанным критерием введём качественную шкалу неопределённости. На шкале неопределённости ранжируем компоненты концептуальной модели, представленной системой кортежей (1), по степени возрастания неопределённости. При этом будет иметь место следующая последовательность страт - уровней неопределённости системной задачи:

конечного результата -- решения - ;

исходных данных (начальной информации) - ;

показателя адекватности - ;

программы решения задачи - ;

алгоритма решения задачи - ;

метода решения задачи - ;

цели системной задачи - ;

среды существования задачи - .

Графическая интерпретация шкалы неопределённости имеет вид, представленный на рис.1. В последовательности страт (см. рис. 1) определённость задачи возрастает при движении по шкале сверху вниз. При этом, каждый выделенный на шкале уровень - страта разбивает её на две части. Верхняя часть шкалы включает все известные (определённые) компоненты, а нижняя - компоненты, которые необходимо определить, т.е. неизвестные.

Рис. 2. Ранжированное представление компонентов системной задачи по шкале неопределённости

Полное описание концептуальной модели задачи, а также методов и теорий их возникновения и т. п. даны в статье [1]. В рамках данной работы мы рассмотрим работу компонента генератора вспомогательной задачи.

Размещено на http://www.allbest.ru/

19

Размещено на http://www.allbest.ru/

На рисунке выше представлены компоненты концептуальной модели системной задачи.

КМСЗ - концептуальная модель системной задачи

ПЦНД - критерии полноты, целостности, необходимости, достаточности

Ан-р - анализатор

ГВЗ - генератор вспомогательных задач

КМВЗ - концептуальная модель вспомогательной задачи

На основании концептуальной модели системной задачи, которая представляется концептом 0го ранга (К) мы разворачиваем пирамиду, каждым уровнем которой будут соответствующие концептуальные вспомогательные задачи (В).

Размещено на http://www.allbest.ru/

19

Размещено на http://www.allbest.ru/

На рисунке выше представлена многоуровневая рекурсивная концептуальная модель задачной системы. От компонента 0го ранга мы рекурсивно переходим вниз на компоненты более низких рангов, причём каждый из них может быть рассмотрен как вершина своей пирамиды. По достижению результата мы возвращаемся наверх к первоначальной задаче.

Программная реализация представления концептуальной модели задачи

Решение задач посредством прямого расчёта

Первая технология, которая реализуется в представленном программной средстве - прямой расчёт. Сначала пользователь выбирает предметную область. Для примера рассмотрим задачу на простое прямолинейное движение.

Рис.5. Окно программы - загрузка данных по предметной области

Программа загружает исходные данные предметной области, которые представляют собой формулы для вычисления всех возможных параметров. В нашем случае эти формулы таковы:

Набор переменных:

x - текущая координата

xs - начальная координата

v - текущая скорость

vs - начальная скорость

astart - начальное ускорение

t - время

to - время (1й корень решения уравнения движения относительно t)

tt - время (2й корень решения уравнения движения относительно t)

Формулы для вычисления:

Затем пользователь загружает непосредственно задачу.

После нажатия кнопки решить мы получаем вывод вида:

Ввод (exec) начальной информации: xs = 30.0

Ввод (exec) начальной информации: vs = 10.0

Ввод (exec) начальной информации: astart = -10.0

Ввод (exec) начальной информации: x = 10.0

Step 0:

Применение шаблона to = ((-1)*(vs) + math.sqrt(((vs)**2) - 2*((xs)-(x))*(astart)))/(astart) для переменной to (to = ((-1)*(vs) + math.sqrt(((vs)**2) - 2*((xs)-(x))*(astart)))/(astart))

to

to = -1.23606798

Переменная to не удовлетворяет параметрам внешней среды (to > 0)

Step 1:

Применение шаблона tt = ((-1)*(vs) - math.sqrt(((vs)**2) - 2*((xs)-(x))*(astart)))/(astart) для переменной tt (tt = ((-1)*(vs) - math.sqrt(((vs)**2) - 2*((xs)-(x))*(astart)))/(astart))

tt

tt = 3.23606798

Таким образом, мы получаем решение задачи (подсчёт переменных посредством прямого математического расчёта, то есть подстановки) и проверку на удовлетворение полученного параметрам внешней среды.

Непосредственно рекурсия здесь не применяется, но если мы изменим условия задачи следующим образом:

Рис.7. Окно программы - другие варианты исходных данных

То есть приведём задачу к виду «на какую максимальную высоту поднялось тело», то получим следующий вывод:

Ввод (exec) начальной информации: xs = 30.0

Ввод (exec) начальной информации: vs = 10.0

Ввод (exec) начальной информации: astart = -9.8

Step 0:

Применяем правило v=0

Применение шаблона x = (xs) + (vs)*t + (astart)*(t**2)/2 для переменной x (x = (xs) + (vs)*t + (astart)*(t**2)/2)

Какая-то из переменных правой части правил не может быть найдена в условиях и/или других правилах, ожидается name 't' is not defined

Поиск 't'

Применение шаблона t = (v-vs)/astart для переменной t (t = (v-vs)/astart)

t

t = 1.02040816

Step 1:

Применение шаблона x = (xs) + (vs)*t + (astart)*(t**2)/2 для переменной x (x = (xs) + (vs)*t + (astart)*(t**2)/2)

x

x = 35.10204082

Таким образом видно, что программа попыталась применить искомый шаблон для нахождения переменной x, но, так как не смогла его найти, то начала рекурсивный поиск шаблонов для решения концептуальной подзадачи - нахождения t как переменной, которая требуется для нахождения x. После того, как данная шаблон (формула) для нахождения t была найдена, идёт её применения. В случае ошибки программа бы рекурсивно перешла дальше и так до тех пор, пока не кончились бы все формулы. После того, как шаблон для t был найден, идёт вторая попытка применения шаблона для x. В случае успеха происходит вывод.

Следует отметить, что процесс поиска вспомогательных концептуальных задач последовательный, так как интерпретатор языка выводит ошибку при нахождения первого несоответствия и не просматривает строку дальше.

Таким образом, можно решать задачи практически любой сложности. Глубину рекурсии также можно регулировать во избежание попадания в бесконечный цикл. Можно выделить две базовые задачи эксперта по моделированию. Первая - это наполнение базы данных и знаний (по сути - математических формул) для предметной области. Вторая - правильное описание данных для нахождения решения данной конкретной задачи.

Принципиальная схема решения:

Размещено на http://www.allbest.ru/

19

Размещено на http://www.allbest.ru/

Рис.8. Принципиальная схема работы программы

Судоку

Судоку (яп. ђ”“Ж су:доку) -- популярная головоломка-пазл с числами. В переводе с японского «су» -- «цифра», «доку» -- «стоящая отдельно». Иногда судоку называют «магическим квадратом», что в общем-то не верно, так как судоку является латинским квадратом 9-го порядка. Судоку активно публикуют газеты и журналы разных стран мира, сборники судоку издаются большими тиражами. Решение судоку -- популярный вид досуга.

Игровое поле представляет собой квадрат размером 9x9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), так как незаполненное игровое поле не имеет смысла. В зависимости от того, сколько клеток уже заполнены, конкретную судоку можно отнести к лёгким или сложным.

Существует несколько методов решения судоку. Условно их можно разделить на две категории - логические и вычислительные. К вычислительным методам относится метод полного перебора (BruteForce). Логические - метод одиночного квадрата, закрытого кандидата, голой и скрытой пары, крыло, slicing and dicing и методы предположений различного уровня.

Методы составления судоку начинаются с составления правильного латинского квадрата. Дальнейшее составление идёт либо постепенным вычёркиванием чисел и проверкой на возможность решения, с оценкой сложности по количеству итераций и применяемому методы, либо открытием определённого числа закрытых клеток. Причём как в первом, так и во втором случае вообще говоря судоку может получиться недетерменированным (то есть допускающим несколько вариантов решения для одних и тех же исходных данных).

Исходный вид разработанной программы при решении судоку такой:

Рис.9. Вид окна программы в режиме решения судоку

Решение судоку

Сначала рассмотрим решение при помощи вспомогательных концептуальных моделей. При нажатии на эту кнопку вызывается окно, в котором можно переключать просмотр по столбцам, строкам или малым квадратам. Элементами вспомогательной концептуальной модели являются непосредственно столбцы, строки или малые квадраты.

Рассмотрим на примере простого судоку:

Рис.10. Пример простого судоку

Рис.11. Одна из вспомогательных концептуальных моделей для простого судоку

При нажатии на кнопку «Решить текущие вспомогательные модели» программа выполнит решение для выделенной вспомогательной концептуальной модели, то есть в нашем случае попытается разрешить все квадраты.

Разрешение вспомогательной модели возможно только в том случае, если в данном конкретном элементе (в нашем случае это квадрат с левым верхним углом A4) отсутствует только одна цифра. В данном случае это верно, поэтому после нажатия данной кнопки мы получим результат:

Рис.12. Решение всех возможных концептуальных моделей для малых квадратов

В случае нажатия на кнопку «Разрешить все вспомогательные модели» программа в бесконечном цикле будет проходить по всем возможным вспомогательным моделям до тех пор, пока они имеют решение. Принципиально это выглядит следующим образом:

Размещено на http://www.allbest.ru/

19

Размещено на http://www.allbest.ru/

Рис.13. Принципиальная схема разрешения вспомогательных концептуальных моделей

Метод полного перебора действует следующим образом:

1. Ведётся поиск первого вхождения 0 (то есть пустой клетки)

2. Если вхождений нет, значит мы получили решение

3. Определяются цифры, которые могут входить в данную клетку (с учётом столбца, строки и малого квадрата). Определение осуществляется функцией:

c = [s[j] for j in range(81)

if not ((i-j)%9 * (i//9^j//9) * (i//27^j//27 | (i%9//3^j%9//3)))]

1. (i-j)%9 - вхождение в столбец

2. (i//9^j//9) - вхождение в строку

3. (i//27^j//27 | (i%9//3^j%9//3)) - блок из трёх строк

4. В случае вхождения получается 0

4. Для всех чисел, которые могут стоять в данной строке рекурсивно вызывается функция перебора, где на месте пустой клетке стоит некоторое число

5. Если нет чисел, которые мы можем вставить в данную клетку, значит метод зашёл в тупик и следует выход из рекурсии на шаг выше.

Несмотря на то, что существует порядка финальных вариантов судоку (то есть всех возможных расположений), метод брутфорса может быть полезен для решения задачи судоку на компьютере. Действительно, для указанного простого судоку подобный метод перебора получил решения за 0.0163с.

Рис.14. Пример работы алгоритма полного перебора для решения простого судоку

Но существуют задачи, которые алгоритм полного перебора будет решать очень долго. Возьмём для примера судоку под названием «Star Burst Leo»

Рис.9. Вид окна программы в режиме решения судоку

Рис.16. Распределение позиций при решении судоку

Было оценено, что для решения данного судоку потребуется 641 580 331 итерация, причём в данном случае в итерации не входит процесс поиска цифр, которые можно внести в данную клетку.

На рисунке 16 показано распределение числа заполненных клеток (ось ординат) от уровня рекурсии (ось абсцисс). Таким образом можно оценить, что процесс перебора доходит до 72 заполненных клеток, а затем встречает несоответствие и ему приходится возвращаться, причём мы видим чёткие полосы в районе 33, 43 и 60 заполненных клеток.

Логические методы решения

Очевидно, что предложенный выше метод хорош для компьютерного моделирования. Но очевидно, что человек на практике никогда не будет пользоваться таким методом. Для этого существуют другие методы.

Обычно решение судоку начинают с расставления чисел, которые могут стоять в данной клетке. Первая часть метода аналогична методу полного перебора, но в отличие от него, сначала мы просто оцениваем элементы, которые могут стоять в клетках, а затем минимизируем количество вариантов. Пример подобного анализа представлен на рисунке ниже:

Рис.17. Пример анализа клеток на предмет подбора кандидатов

Все методы рассматриваются в статье [2], но здесь я опишу несколько из них.

Первый метод - Х-крыло.

«X-крыло» -- позиция, когда один из кандидатов дважды (и только дважды) встречается в двух строчках головоломки. Эти кандидаты должны входить в две колонки, что обеспечивает формирование прямоугольного Х-крыла. Также две колонки с двумя (и только с двумя) клетками, которые содержат одинаковых кандидатов (входящие в две строки) также формируют X-крыло. Эти четыре клетки -- единственные возможные места расположения для «настоящих» кандидатов в этих строках или колонках. Другие подобные кандидаты, расположенные по периметру прямоугольника, образованного «настоящими» кандидатами, должны быть удалены. Возможно эта комбинация была названа X-крылом потому, что

Рассмотрим пример решения Х-крыла (рисунок вверху). Как видим, для легкости восприятия из кандидатов отображены только шестерки (был применен фильтр кандидатов -- программа Simple Sudoku это умеет делать).

Синие и ярко-зеленые ячейки формируют классическое «X-крыло» -- первая и девятая строчки имеют только по две ячейки с кандидатом 6, их разделяют две колонки (седьмая и восьмая), кандидаты образуют прямоугольник. «Настоящих» кандидатов представляют синие, или ярко-зеленые ячейки. Потому другие кандидаты в шестой и девятой колонках нужно удалить (они выделены желтым контуром).

Рис.18. Использование метода Х-крыло

Slicind and dacing

Рассмотрим метод slicing and dacing на примере:

Рис.19. Пример судоку для алгоритма slicing and dicing

Рис.20. Первый шаг алгоритма

На первом шаге рассматриваются пересечения столбца и строки для цифры 1 в рамках квадрата G1-I3. Получается, что 1 может стоять либо на позиции H1 либо на позиции I1.

Рис.21. Второй шаг алгоритма

На основе полученного результата на первом шаге просматривается полученная строка. В квадрате D1-F3 с учётом стоящей на позиции E8 единицы и полученной на первом шаге строки остаётся только одна позиция - D2. Таким образом, после работы алгоритма получаем судоку:

Рис.22. Результат работы алгоритма

Аналогичным образом можно получить единицы во всех остальных малых клетках.

Метод предположений похож на метод полного перебора. Но применяется он после применения вышеуказанных методов. Рассмотри на примере:

Рис.9. Вид окна программы в режиме решения судоку

При решении стандартными логическими методами (скрытые пары, скрытые квадраты и т. п.) решение не найдено:

Рис.24. Судоку после выполнения первых логических методов

Но мы видим, что в клетках B3 и C3 может стоять только пара 46. Алгоритм делает предположение, что стоит в B3 стоит 4, доходит до несоответствия, ставит 6 и получает результат:

Рис.24. Судоку после выполнения предположений

Таким образом исходное судоку разрешено.

Блок-схема алгоритма выглядит следующим образом:

Размещено на http://www.allbest.ru/

19

Размещено на http://www.allbest.ru/

Рис.25. Блок-схема работы алгоритма

Составление судоку

Составление судоку может осуществляться двумя методами - либо сокрытием случайной ячейки после составления правильного латинского квадрата, либо наоборот открытием случайных ячеек. В первом случае после каждого шага выполняется решение и проверяется количество итераций и их сложность (применение методов первичных, slicing and dicing, предположений).

Составление открытием

Размещено на http://www.allbest.ru/

19

Размещено на http://www.allbest.ru/

Рис.25. Блок-схема работы алгоритма составления открытыием

Но несмотря на то, что цифры из доски выполняется в порядке, обратном заполнению, всё равно возможно получение недетерменированного судоку и данную проблему разрешить невозможно.

Решение вычёркиванием

Решение вычёркиванием состоит в получении правильного латинского квадрата. Затем в полученном латинском квадрате рекурсивно осуществляются перестановки строк, столбцов и малых квадратов в соответствие с требованиями. Затем происходит вычёркивание случайного элемента и решение полученного судоку на основе методов решения. Сложность алгоритма определяется количеством итераций, которые необходимы для решения.

Переносимость и интегрируемость

Так как программа написана на Python, программа является переносимой на любую платформу (Windows, Linux, MacOS).

В целях интегрируемости программа принимает параметры в командной строке. Перечень параметров:

-t, --type - [math | sudoku] - тип шаблона, математические формулы по предметной области или судоку

-a, --task - [solve | generate] - задание, решить или создать, для шаблона math по умолчанию - решить

-m, --method - [[None] | [brute | analytic] | [opening | cut]] - метод, не применим для шаблона math, принимает значения brute или analytic при задании solve или opening или cut при задании generate

-q, --template - шаблон для математических формул

-i, --input - входной файл

-o, --output - выходной файл

Литература

1. Нечаев В.В. Концептуальное модельное представление задачи как системы. Информационные технологии, № 2009.с.

2. http://www.angusj.com/sudoku/hints.php

Приложение

Программный код

Решатель математических моделей

# -*- coding: cp1251 -*-

import math

import codecs

import re

import sys

import string

import graphWindow

import copy

class solver():

def __init__(self, data, rules, goals, **kwargs):

self._recursionLevel = 0

self.data = (data.lower()).split("\n")

self.rules = (rules.lower()).split("\n")

self.goals = (goals.lower()).split("\n")

self.rawgoals = self.goals

self.templateVars = kwargs.get('templateVars', {})

self.templateFull = kwargs.get('templateFull', {})

self.sErrTxt = ''

self.sSolveTxt = ''

self.env = kwargs.get('env', {})

self.__globals = {}

self.__locals = {}

self.fString = []

self.parent = kwargs.get('parent', None)

self.analyzeData()

self.analyzeRules()

self.analyzeGoals()

self.makeSolveFor()

#for g in self.goals:

#self.makeSolveFor(g)

def analyzeData(self):

self.definiedVariables = []

for q in self.data:

r = q.split('=')

self.definiedVariables.append(r[0].strip())

self.definiedVariablesFirst = copy.copy(self.definiedVariables)

def analyzeRules(self):

print self.rules

self.ruledVariablesLeft = []

self.ruledVariablesRight = []

l = 0

for q in self.rules:

r = q.split('=')

self.ruledVariablesLeft.append(r[0])

try:

r[1]

except IndexError:

self.solveErr = 31

self.solveErrExtend = { 'vString' : r}

self.solveErrorsText()

return

splRules = re.split('([A-Za-z]+)([0-9]*)', r[1])

self.ruledVariablesRight.append([])

print splRules

for sId in range(len(splRules)-1):

sRule = splRules[sId]

nsRule = splRules[sId+1]

if re.match('^[A-Za-z]+$', sRule) and ('' == nsRule or re.match('^[0-9]+$', nsRule)):

print sRule+nsRule

self.ruledVariablesRight[l].append(str(sRule+nsRule))

l = l + 1

def analyzeGoals(self):

goals = self.goals

self.goals = []

for i in goals:

goalParts = re.split('(^[A-Za-z]+)([0-9]+)$', i)

self.goals.append({ 'goalLine' : i,

'goalParts' : goalParts if goalParts[0] != '' else goalParts[1:3]

})

def makeSolveFor(self):

print 'Solving'

print self.ruledVariablesLeft

print self.ruledVariablesRight

print self.goals

self.solveErr = 0

self.solveErrExtend = {}

self.solution = 0

self.solutionString = 'крабе'

exec('import math', self.__globals, self.__locals)

for cGoal in self.goals:

if cGoal['goalParts'][0] not in self.templateVars['vars'].lower().split(','):

self.solveErr = 24

self.solveErrExtend = { 'vName' : cGoal['goalParts'][0], 'dVars' : self.templateVars['vars']}

for cGoal in self.goals:

print 'definded: '+ ''.join(self.definiedVariables)

print 'goal:'+cGoal['goalLine']

if cGoal['goalLine'] in self.definiedVariables:

print 'Found'

self.solveErr = 14

self.solveErrExtend = cGoal['goalLine']

self.solveErrorsText()

return

if self._recursionLevel == 0:

for iData in self.data:

if iData.strip() == '':

break

try:

exec(iData+';', self.__globals, self.__locals)

self.log("Ввод (exec) начальной информации: %s"%(iData))

except NameError as err:

print 'NameError %s' %(err)

self.solveErr = 1

self.solveErrExtend = { 'vName' : err }

return

except:

print 'Unknown exception %s'%sys.exc_info()[0]

self.solveErr = 3

self.solveErrExtend = {}

for m in range(len(self.goals)):

self.log('Step %d:\n'%m)

for iRule in self.rules:

if iRule.strip() == '':

break

try:

self.log('Применяем правило %s' %iRule)

exec(iRule+';', self.__globals, self.__locals)

except NameError as err:

print 'NameError %s' %(err)

self.solveErr = 15

self.solveErrExtend = { 'vName' : err }

self.solveErrorsText()

return

except:

print 'Unknown exception'

self.solveErr = 18

self.solveErrExtend = {}

self.solveErrorsText()

return

l = self.preFind()

#l = [0]

if (l[0] not in (0, 2, 5, 13)):

if 12 == l[0]:

self.solveErrorsText()

if self._recursionLevel < 2:

self._recursionLevel = self._recursionLevel + 1

self.makeSolveFor()

pass

else:

self.solveErrorsText()

return

elif 2 == l[0]:

self.solveErrorsText()

elif 5 == l[0]:

try:

self.solveErrorsText()

exec(l[1]['ruleString'], self.__globals, self.__locals)

self.log(l[1]['varName'])

self.log("%s = %2.8lf" %(l[1]['varName'], eval(l[1]['varName'], self.__globals, self.__locals)))

return

except NameError as s:

print 'NameError in right solving %s' %s

self.solveErr = 21

self.solveErrExtend = l[1]

self.solveErrorsText()

return

for (key, val) in self.templateFull.iteritems():

if (key == self.goals[m]['goalParts'][0]):

print 'Found %s'%key

try:

if -1 != self.goals[m]['goalParts'][1]:

# заменяем шаблон

lf = val.lower()

for ctr in self.templateVars['vars'].lower().split(','):

lf = string.replace(lf, ctr, ctr+str(self.goals[m]['goalParts'][1]))

except IndexError as s:

print 'IndexError %s'%s

lf = val.lower()

pass

self.log('Применение шаблона %s = %s для переменной %s (%s = %s)' % (key, val, self.goals[m]['goalLine'], self.goals[m]['goalLine'], lf))

try:

exec("%s=%s"%(self.goals[m]['goalLine'], lf), self.__globals, self.__locals)

self.fString.append((self.goals[m]['goalLine'], lf))

self.log(self.goals[m]['goalLine'])

r = eval(self.goals[m]['goalLine'], self.__globals, self.__locals)

self.log("%s = %2.8lf" %(self.goals[m]['goalLine'], r))

self.data.append(r)

self.definiedVariables.append(self.goals[m]['goalLine'])

self.checkEnv(self.goals[m]['goalLine'], r)

continue

except NameError as err:

self.solveErr = 36

self.solveErrExtend = { 'line' : "%s=%s"%(self.goals[m]['goalLine'], lf), 'err' : err}

return

except:

self.solveErr = 37

self.solveErrExtend = { 'line' : "%s=%s"%(self.goals[m]['goalLine'], lf), 'err' : sys.exc_info()[0]}

return

# if (key == self.goals[m]['goalLine']):

def preFind(self):

print 'Analyzing'

print self.goals, self._recursionLevel

for sGoal in self.goals:

goalLine = sGoal['goalLine']

for sRule in self.ruledVariablesRight:

if goalLine in sRule:

self.solveErr = 2

self.solveErrExtend = {'vName' : goalLine}

return (2, {})

if goalLine in self.ruledVariablesLeft:

self.solveErr = 5

rS = self.retRuleStringByVal(goalLine)

self.solveErrExtend = { 'vName' : goalLine, 'ruleString' : rS }

return (5, {'ruleString' : rS, 'varName' : goalLine})

err = 0

for sRule in self.ruledVariablesRight:

for l in sRule:

if l in self.definiedVariables:

err = 1

if l in self.ruledVariablesLeft:

err = 2

if 1 == err:

return (0, {})

elif 2 == err:

self.solveErr = 13

return (0, {})

else:

q = self.analyzeGoalsNeeded()

print q

if q == '':

return (0, {})

else:

self.solveErr = 12

line = self.analyzeGoalsNeeded()

self.solveErrExtend = { 'vName' : line }

#self.goals = ('%s' %(line)).split('\'')[1]+"\n".join(self.rawgoals)

self.goals = []

self.goals.append(('%s' %(line)).split('\'')[1])

for i in self.rawgoals:

self.goals.append(i)

self.log('Поиск \'%s\''%('%s' %(line)).split('\'')[1])

print 'Поиск \'%s\''%('%s' %(line)).split('\'')[1]

self.analyzeGoals()

return (12, {})

def analyzeGoalsNeeded(self):

for goalLine in self.goals:

gL = goalLine['goalLine']

gP = goalLine['goalParts']

for (key, val) in self.templateFull.iteritems():

if key == gP[0]:

try:

if -1 != gP[1]:

# заменяем шаблон

lf = val.lower()

for ctr in self.templateVars['vars'].lower().split(','):

lf = string.replace(lf, ctr, ctr+str(self.goals[m]['goalParts'][1]))

except IndexError as s:

print 'IndexError %s'%s

lf = val.lower()

pass

try:

print lf

exec(lf, self.__globals, self.__locals)

except NameError as err:

return err

return ''

def simpleCheckEnv(self, varName, envVar, envParts, envElem):

try:

envParts[1]

except:

return

if envVar == varName:

l = eval(envElem, self.__globals, self.__locals)

if l:

print 'TRUE'

else:

self.log('Переменная %s не удовлетворяет параметрам внешней среды (%s)'%(varName, envElem))

print 'FALSE'

def checkEnv(self, varName, res):

print 'Checking %s by %lf'%(varName, res)

print self.env

for (envKey, envElem) in self.env.iteritems():

envParts = envElem.split('>=')

envVar = envParts[0].lower().strip()

self.simpleCheckEnv(varName, envVar, envParts, envElem)

envParts = envElem.split('<=')

envVar = envParts[0].lower().strip()

self.simpleCheckEnv(varName, envVar, envParts, envElem)

envParts = envElem.split('>')

envVar = envParts[0].lower().strip()

self.simpleCheckEnv(varName, envVar, envParts, envElem)

envParts = envElem.split('<')

envVar = envParts[0].lower().strip()

self.simpleCheckEnv(varName, envVar, envParts, envElem)

def retRuleStringByVal(self, val):

for i in self.rules:

if val == i.split('=')[0].strip():

return i

def retSolving(self, **kwargs):

ret = { 'err' : self.solveErr,

'errTxt' : self.sSolveTxt,

'sol' : self.solution,

'solStr' : self.sSolveTxt

}

return ret

def solveErrorsText(self):

self.log({

0 : lambda q: 'ОК',

1 : lambda q: "Переменная %s используется, но не задана" %(q['vName']),

2 : lambda q: "Переменная %s задана для поиска и в то же время используется в правиле. Возможна рекурсия"%(q),

3 : lambda q: 'Неизвестная ошибка при задании начальных условий',

5 : lambda q: "Переменная %s прямо вычисляется по правилу %s"%(q['vName'], q['ruleString']),

6 : lambda q: "Не задана переменная %s" %(q['vName']),

12 : lambda q: 'Какая-то из переменных правой части правил не может быть найдена в условиях и/или других правилах, ожидается %s'%(q['vName']),

13 : lambda q: 'Переменная правой части условий найдена в задании левой. Может вызвать ошибку',

14 : lambda q: 'Избыточные данные: переменная %s задана и требуется найти'%(q),

15 : lambda q: "Попытка использовать незаданную переменную %s в правилах" %(q['vName']),

18 : lambda q: 'Неизвестная ошибка при задании правил',

21 : lambda q: 'Ошибка прямого подсчёта, строка %s, переменная %s: '%(q['ruleString'], q['varName']),

24 : lambda q:

"Переменная %s не найдена среди возможных (%s)" %(q['vName'], q['dVars']),

31 : lambda q: 'Не заданы правило: строка должна быть формата A=(B) (дано: %s'%(''.join(q['vString'])),

36 : lambda q: 'Ошибка обработки строки %s: %s'%(q['line'], q['str'])

}[self.solveErr](self.solveErrExtend), True)

def log(self, txt, error=False, onlyError=False):

if error:

self.sErrTxt = self.sErrTxt + "\n" + txt

if not onlyError:

self.sSolveTxt = self.sSolveTxt + "\n" + txt

def graph(self, event):

print self.definiedVariables

print self.definiedVariablesFirst

graphWindow.graphWindow(self.parent, globals=self.__globals, locals=self.__locals,

defined=self.definiedVariablesFirst,

data=self.data,

fString=self.fString)

Решатель судоку методом полного перебора

def solve(s):

try:

i = s.index(0)

except ValueError:

# No empty cell left: solution found

return s

c = [s[j] for j in range(81)

if not ((i-j)%9 * (i//9^j//9) * (i//27^j//27 | (i%9//3^j%9//3)))]

for v in range(1, 10):

if v not in c:

r = solve(s[:i]+[v]+s[i+1:])

if r is not None:

return r

class Sudoku(list):

'''Sudokus with nicer IO'''

def __init__(self, content):

list.__init__(self, [int(i) for i in content.split()]

if isinstance(content, str) else content)

def __str__(self):

return '\n'.join(

' '.join([(str(j) if j != 0 else '-')

for j in self[i*9:(i+1)*9]]) for i in range(9))

Решатель судоку аналитическими методами

TRIPLETS = [[0,1,2],[3,4,5],[6,7,8]]

#Row/Col/3x3 iteration list, each is nine lists of nine (row,col) pairs

ROW_ITER = [[(row,col) for col in range(0,9)] for row in range(0,9)]

COL_ITER = [[(row,col) for row in range(0,9)] for col in range(0,9)]

TxT_ITER = [[(row,col) for row in rows for col in cols] for rows in TRIPLETS for cols in TRIPLETS]

class sudoku:

def __init__(self, start_grid=None) :

#Setup list of lists (the rows), each row is a list of 9 cells, which are each a list of integers 1-9 inclusive.

self.squares =[ [range(1,10) for col in range(0,9)] for row in range(0,9)]

if start_grid is not None:

if len(start_grid)==81 :

for row in range(0,9) :

self.set_row(row, start_grid[(row*9):((row+1)*9)])

else :

assert len(start_grid)==9, "Bad input!"

for row in range(0,9) :

self.set_row(row, start_grid[row])

#self.check()

self._changed=False

def solved(self) :

for row in range(0,9) :

for col in range(0,9) :

if len(self.squares[row][col]) > 1 :

return False

return True

def copy(self) :

sudoku_copy = sudoku(None)

for row in range(0,9) :

for col in range(0,9) :

sudoku_copy.squares[row][col] = self.squares[row][col][:] #copy!

sudoku_copy._changed=False

return sudoku_copy

def set_row(self,row, x_list) :

assert len(x_list)==9

for col in range(0,9) :

try :

x = int(x_list[col])

except :

x = 0

#self.set_cell(row,col,x)

self.set_cell(row,col,x)

def set_cell(self,row,col,x):

if self.squares[row][col] == [x] :

#Already done!

pass

elif x not in range(1,9+1) :

#Set to unknown

pass

else:

assert x in self.squares[row][col], \

"Told to set square (%i,%i) to an impossible entry, %i" % (row,col,x)

self.squares[row][col] = [x]

self.update_neighbours(row,col,x)

self._changed=True

def cell_exclude(self, row,col,x) :

assert x in range(1,9+1)

if x in self.squares[row][col] :

#Remove it...

self.squares[row][col].remove(x)

#Should be one or more entries left...

assert len(self.squares[row][col]) > 0, \

"Removed last possible entry for square (%i,%i) which was %i" \

% (row, col, x)

#Now, has this confirmed the value for this square?

if len(self.squares[row][col]) == 1 :

#This cell is now definate..

#Need to update its friends...

#print "After exluding %i, square (%i,%i) must be %i" \

#% (x, self.row, self.col, self[0])

self._changed=True

self.update_neighbours(row,col,self.squares[row][col][0])

else :

#Don't need to remove this, already done!

pass

return

def row_exclude(self, row, x) :

assert x in range(1,9+1)

for col in range(0,9) :

self.cell_exclude(row,col,x)

def col_exclude(self, col, x) :

assert x in range(1,9+1)

for row in range(0,9) :

self.cell_exclude(row,col,x)

def update_neighbours(self,set_row,set_col,x) :

"""Call this when the square is set to x, either directly,

or as a side effect of an exclude leaving only one entry"""

#print "Updating (%i,%i) to be %i..." % (self.row, self.col, x)

#Update the possibilies in this row...

for row in range(0,9) :

if row <> set_row :

self.cell_exclude(row,set_col,x)

#Update the possibilies in this col...

for col in range(0,9) :

if col <> set_col :

self.cell_exclude(set_row,col,x)

#Update the possibilies in this 3x3 square...

for triplet in TRIPLETS :

if set_row in triplet : rows = triplet[:]

if set_col in triplet : cols = triplet[:]

#Only need to do four of the eight possibles (well, 9 if you count the cell itself)

#as did two on the row, and two on the col

rows.remove(set_row)

cols.remove(set_col)

for row in rows :

for col in cols :

assert row <> set_row or col <> set_col

#print "Updating (%i,%i) to be %i, excluding %i from (%i, %i)" \

#% (self.row, self.col, x, x, row, col)

self.cell_exclude(row,col,x)

def get_cell_int(self,row,col) :

if len(self.squares[row][col])==1 :

return int(self.squares[row][col][0])

else :

return 0

def get_cell_str(self,row,col) :

if len(self.squares[row][col])==1 :

return "(%i,%i) = %i" % (row, col, self.squares[row][col][0])

else :

return ("(%i,%i) = " % (row, col)) + ",".join([str(x) for x in self.squares[row][col]])

def get_cell_digit_str(self,row,col) :

if len(self.squares[row][col])==1 :

return str(self.squares[row][col][0])

else :

return "0"

def as_test_81(self) :

"""Return a string of 81 digits"""

return "".join(self.as_test_list())

def simple_text(self) :

return "\n".join(self.as_test_list())

def as_test_list(self) :

return [ ("".join( [self.get_cell_digit_str(row,col) for col in range(0,9)])) for row in range(0,9) ]

"""

answer=[]

for row in range(0,9) :

line=""

for col in range(0,9) :

line = line + self.get_cell_digit_str(row,col)

answer.append(line)

return answer

"""

def __repr__(self):

answer="[" + ",".join([ \

("[" + ",".join( [self.get_cell_digit_str(row,col) for col in range(0,9)]) + "]") \

for row in range(0,9) ])

return answer

def __str__(self):

answer = " 123 456 789\n"

for row in range(0,9) :

answer = answer + str(row+1) \

+ " [" + "".join([self.get_cell_digit_str(row,col).replace("0","?") for col in range(0,3)]) \

+ "] [" + "".join([self.get_cell_digit_str(row,col).replace("0","?") for col in range(3,6)]) \

+ "] [" + "".join([self.get_cell_digit_str(row,col).replace("0","?") for col in range(6,9)]) \

+ "]\n"

if row+1 in [3,6] :

answer = answer + " --- --- ---\n"

return answer

def retArr(self):

data = []

for row in range(0,9) :

data.append([])

for col in range(0, 9):

data[row].append(self.get_cell_digit_str(row,col))

return data

def check(self, level=0) :

self._changed=True

while self._changed:

#print "checking..."

self._changed=False

self.check_for_single_occurances()

self.check_for_last_in_row_col_3x3()

if level >= 1 :

self.overlapping_3x3_and_row_or_col() #(aka slicing and dicing)

if level >= 2 :

self.one_level_supposition()

if level >= 3 :

self.two_level_supposition()

#If nothing happened, then self.changed==False (still)

#and we break the loop

return

def check_for_single_occurances(self):

#Want to see if x only occurs once in this row/col/3x3...

for check_type in [ROW_ITER, COL_ITER, TxT_ITER]:

for check_list in check_type :

for x in range(1,9+1) : #1 to 9 inclusive

x_in_list = []

for (row,col) in check_list :

if x in self.squares[row][col] :

x_in_list.append((row,col))

if len(x_in_list)==1 :

(row,col) = x_in_list[0]

#This position MUST be be x

if len(self.squares[row][col]) > 1 :

self.set_cell(row,col,x)

def check_for_last_in_row_col_3x3(self):

#Now, for each row/col/3x3 want to see if there is a single

#unknown entry...

for (type_name, check_type) in [("Row",ROW_ITER),("Col",COL_ITER),("3x3",TxT_ITER)]:

for check_list in check_type :

unknown_entries = []

unassigned_values = range(1,9+1) #1-9 inclusive

known_values = []

for (row,col) in check_list :

if len(self.squares[row][col]) == 1 :

assert self.squares[row][col][0] not in known_values, \

"Already have %i (%i,%i) in known list [%s] for %s" % (self.squares[row][col][0],row,col, ",".join(map(str,known_values)), type_name)

known_values.append(self.squares[row][col][0])

assert self.squares[row][col][0] in unassigned_values, \

"Expected %i (%i,%i) in list [%s] for %s" % (self.squares[row][col][0],row,col, ",".join(map(str,unassigned_values)), type_name)

unassigned_values.remove(self.squares[row][col][0])

else :

unknown_entries.append((row,col))

assert len(unknown_entries) + len(known_values) == 9

assert len(unknown_entries) == len(unassigned_values)

if len(unknown_entries) == 1 :

#This cell must be the only number 1-9 not in known_values

x = unassigned_values[0]

(row,col) = unknown_entries[0]

#assert x not in known_values

#print "Because its the last cell in its row/col/3x3 entry (%i,%i) must be %i" \

#% (row,col,x)

self.set_cell(row,col,x)

"""

for row in range(0,9) : self.check_row(row)

for col in range(0,9) : self.check_col(col)

#Check the 3x3 squares...

for rows in TRIPLETS :

for cols in TRIPLETS :

for x in range(0,9) :

x_in_location=[]

for row in rows:

for col in cols :

if x in self.squares[row][col] :

x_in_location.append((row,col))

if len(x_in_location)==1 :

(row,col) = x_in_location[0]

#This position MUST be be x

if len(self.squares[row][col]) > 1 :

self.set_cell(row,col,x)

"""

return

def diagnosis(self) :

answer=""

df = long(1)

for row in range(0,9) :

for col in range(0,9):

if len(self.squares[row][col]) > 1 :

answer = answer + str(self.squares[row][col]) + "\n"

df = df * len(self.squares[row][col])

answer = answer + "Degrees of freedom: %i" % df

return answer

def overlapping_3x3_and_row_or_col(self):

"""Block and Column / Row Interactions (name from Simon Armstrong)

http://www.simes.clara.co.uk/programs/sudokutechnique3.htm

Also known as 'slicing and dicing'

"""

#For a given 3x3, and a given digit, want to see if

#all the remaining candidates are in a single row or column..

#Want to see if x only occurs once in this row/col/3x3...

for check_list in TxT_ITER :

for x in range(1,9+1) : #1 to 9 inclusive

#print "Checking %i in 3x3" % x, check_list

rows_for_x = []

cols_for_x = []

for (row,col) in check_list :

if x in self.squares[row][col] :

#print "Found possible %i at (%i,%i)" % (x, row, col)

if row not in rows_for_x : rows_for_x.append(row)

if col not in cols_for_x : cols_for_x.append(col)

#Are they all in the same row?

if len(rows_for_x)==1 and len(cols_for_x) > 1 :

#print "%i must be in row %i using cols %s" % (x, rows_for_x[0]+1, ",".join(map(lambda i : str(i+1),cols_for_x)))

#print self

#This means, we can remove X from all the rest of the row...

row = rows_for_x[0]

for col in range(0,9) :

if col not in cols_for_x :

self.cell_exclude(row,col,x)

#We can also remove x from all the rest of this 3x3...

for (row,col) in check_list :

if col not in cols_for_x :

if row not in rows_for_x :

self.cell_exclude(row,col,x)

#Are they all in the same col?

if len(cols_for_x)==1 and len(rows_for_x) > 1 :

#print "%i must be in col %i using rows %s" % (x, cols_for_x[0]+1, ",".join(map(lambda i : str(i+1),rows_for_x)))

#print self

#This means, we can remove X from all the rest of the row...

col = cols_for_x[0]

for row in range(0,9) :

if row not in rows_for_x :

self.cell_exclude(row,col,x)

#We can also remove x from all the rest of this 3x3...

for (row,col) in check_list :

if col not in cols_for_x :

if row not in rows_for_x :

self.cell_exclude(row,col,x)

def one_level_supposition(self):

"""Probably what is known as 'Nishio', try a number and see if it leads to a dead end.

For all the ambigous squares, try each possible each entry and see

if its OK, or if it leads to a contradiction. In the case of a contradiction

we can remove it as a possibility...

Two level suppositions (two guess) may be required for extreme puzzles..."""

progress=True

while progress :

progress=False

#print "Doing one level supposition..."

for row in range(0,9) :

for col in range(0,9):

if len(self.squares[row][col]) > 1 :

bad_x = []

for x in self.squares[row][col] :

#print "/-- Trying setting (%i,%i) to %i" % (row,col,x)

sudoku_copy = self.copy()

try:

sudoku_copy.set_cell(row,col,x)

sudoku_copy.check(level=1)

except AssertionError, e :

#Leads to an error :)

#This means that this square cannot be x

#print e

#print "%s cannot be %i" % (str(self.squares[row][col]), x)

bad_x.append(x)

del sudoku_copy

#print "\-- End of exp"

if len(bad_x) == 0 :

pass

elif len(bad_x) < len(self.squares[row][col]) :

for x in bad_x :

self.cell_exclude(row,col,x)

self.check()

progress=True

else :

assert False, "Bugger! All possible values for square (%i,%i) fail" \

% (row,col)

#print "One level supposition done"

def two_level_supposition(self) :

progress=True

while progress :

progress=False

#print "Doing two level supposition..."

for row in range(0,9) :

for col in range(0,9):

if len(self.squares[row][col]) > 1 :

bad_x = []

for x in self.squares[row][col] :

#print "/-- Trying setting (%i,%i) to %i" % (row,col,x)

sudoku_copy = self.copy()

try:

sudoku_copy.set_cell(row,col,x)

#sudoku_copy.check()

#sudoku_copy.one_level_supposition()

sudoku_copy.check(level=2)

except AssertionError, e :

bad_x.append(x)

del sudoku_copy

#print "\-- End of exp"

if len(bad_x) == 0 :

pass

elif len(bad_x) < len(self.squares[row][col]) :

for x in bad_x :

self.cell_exclude(row,col,x)

self.check()

progress=True

else :

assert False, "Bugger! All possible values for square (%i,%i) fail" \

% (row,col)

Генератор судоку методом открытий

# sudoku.py

# Robert Wohleb

# 20051115

import random

class board:

boardlist = []

partialboardlist = []

def generate(self, numFilled=(9*9)):

slots = []

fillOrder = []

random.seed()

# setup board

row = [0,0,0,0,0,0,0,0,0]

for i in range(0, 9):

self.boardlist.append(row[:])

for j in range(0, 9):

for i in range(0, 9):

slots.append((i,j))

self.search(slots, 0)

while len(slots) > 0:

i = random.randint(0, len(slots)-1)

fillOrder.append(slots[i])

del slots[i]

# setup board

for i in range(0, 9):

self.partialboardlist.append(row[:])

for i in range(0, numFilled):

j = fillOrder[i]

self.partialboardlist[j[0]][j[1]] = self.boardlist[j[0]][j[1]]

def search(self, slots, index):

nums = []

fillOrder = []

if len(slots) == index:

return self.check()

for i in range(1, 10):

nums.append(i)

while len(nums) > 0:

i = random.randint(0, len(nums)-1)

fillOrder.append(nums[i])

del nums[i]

for i in fillOrder:

x = slots[index][0]

y = slots[index][1]

self.boardlist[x][y] = i

#print

#print x, y, i

#self.printBoard()

if (self.check()):

if self.search(slots, index+1):

return True

self.boardlist[x][y] = 0

return False

def check(self):

for i in range(0, 9):

if (not self.checkRow(i)) or (not self.checkCol(i)) or (not self.checkSquare(i)):

return False

return True

def checkRow(self, row):

found = []

for i in range(0, 9):

if not self.boardlist[i][row] == 0:

if self.boardlist[i][row] in found:

#print 'checkRow', i, row, self.boardlist[i][row]

return False

found.append(self.boardlist[i][row])

return True

def checkCol(self, col):

found = []

for j in range(0, 9):

if not self.boardlist[col][j] == 0:

if self.boardlist[col][j] in found:

#print 'checkCol', j, col, self.boardlist[col][j]

return False

found.append(self.boardlist[col][j])

return True

def checkSquare(self, square):

found = []

xoffset = (3*(square % 3))

yoffset = int(square / 3) * 3

#print 'checkSquare(', xoffset, yoffset, ')'

for j in range(0, 3):

for i in range(0, 3):

if not self.boardlist[xoffset+i][yoffset+j] == 0:

if self.boardlist[xoffset+i][yoffset+j] in found:

#print 'checkSquare -- ', i, j, self.boardlist[xoffset+i][yoffset+j]

return False

found.append(self.boardlist[xoffset+i][yoffset+j])

return True

def getList(self): # setup board

row = [0,0,0,0,0,0,0,0,0]

for i in range(0, 9):

self.boardlist.append(row[:])

return self.boardlist

def printBoard(self):

for j in range(0, 9):

for i in range(0, 9):

if self.boardlist[i][j] == 0:

print '.',

else:

print self.boardlist[i][j],

print

def printPartialBoard(self):

for j in range(0, 9):

for i in range(0, 9):

if self.partialboardlist[i][j] == 0:

print '.',

else:

print self.partialboardlist[i][j],

print

def getBoard(self):

data = []

for j in range(0, 9):

data.append([])

for i in range(0, 9):

data[j].append(self.boardlist[i][j])

return data

def getPartialBoard(self):

data = []

for j in range(0, 9):

data.append([])

for i in range(0, 9):

data[j].append(self.partialboardlist[i][j])

return data

Размещено на Allbest