Модель интеллектуальной рекурсивной машины – генератора вспомогательных концептуальных моделей задач – базовой исходной концептуальной модели
Концептуальное представление задачи как системы. Программная реализация представления концептуальной модели задачи. Решение задач посредством прямого расчета. Метод полного перебора. Разрешение концептуальных моделей. Составление и решение судоку.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 24.07.2013 |
| Размер файла | 2,2 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Тема: «Модель интеллектуальной рекурсивной машины - генератора вспомогательных концептуальных моделей задач - базовой исходной концептуальной модели»
Дисциплина: Моделирование систем
Оглавление
Введение
Концептуальное модельное представление задачи как системы
Программная реализация представления концептуальной модели задачи
Решение задач посредством прямого расчёта
Судоку
Решение судоку
Разрешение концептуальных моделей
Метод полного перебора
Логические методы решения
Составление судоку
Составление открытием
Решение вычёркиванием
Заключение
Литература
Приложение. Программный код
Введение
В настоящее время высокий уровень развития современных электронно-вычислительных средств даёт возможность быстро и эффективно решать вопросы, связанные с хранением и обработкой всевозможных видов информации, представлением данных и знаний в удобных для пользователя и понятных для компьютера формах. Подобные возможности реализуются посредством эффективного применения баз данных и хранилищ данных, а также автоматизированных, электронных и интеллектуальных систем. Растущие потребности человечества порождают все более сложные в качественном и количественном аспектах задачи, решение которых зачастую определяет прогресс общества.
В ходе данной работы будет рассмотрено представление концептуальной модели задачи (КМЗ) на основе триады «Задача - Данные - Решатель» и работа одного из компонентов подобной системы - генератора вспомогательных концептуальных моделей.
В процессе выполнения данной работы была создана программа (на языке Python), позволяющая решать любые задачи, связанные с вычислениями на основе вводимых пользователем исходных данных и определяемых некоторой предметной областью, для которой заданы действительные математические формулы. Программа осуществляет поиск необходимых формул на основе вводимых пользователем данных, а затем применяет данные формулы для получения конечного результата. Кроме того, данная программа позволяет решать и составлять судоку - один из видов японских кроссвордов, составляя вспомогательные концептуальные задачи и решая их и исходную задачу на основе различных рекурсивных методов.
Особенность предлагаемого метода представления задачи как концептуальной модели имеет отличительную особенность по сравнению с классической технологией, так как исходная задача не разбивается на меньшие составные подзадачи, а происходит генерация вспомогательных задач, решая которые можно решить исходную задачу.
Далее в работе будет описано представление исходной задачи как концептуальной модели задачи, формализация задачи, а также описана практическая реализация составленной программы.
Концептуальное модельное представление задачи как системы
Деятельность человека имеет две основные формы: умственную - “деятельность мозга” и физическую - “деятельность рук”. Очевидно, что и умственная и физическая деятельность сопряжены с постоянной необходимостью решения разнообразных задач. Спектр таких задач определяется многочисленными факторами, как существенными, так и малозначимыми. К существенным факторам, прежде всего, следует отнести причины возникновения задачи. В качестве первопричины, порождающей задачу, выступают потребности человека. Удовлетворение потребностей осуществляется в процессе взаимодействия человека не только с внешней, но и с собственной внутренней средой, т.е. с природой, с другими людьми или самим собой. Реализация потребностей всегда связана с решением соответствующих этим потребностям задач. Практически весь спектр потребностей человека определяется тремя сферами его деятельности: материальной, социальной и духовной. Следовательно, можно констатировать, что возникновение задач обусловлено материальными, социальными и духовными факторами. К существенным факторам, определяющим содержание и свойства задач, следует также отнести: предметную область существования задачи, её размерность и уровень сложности, степень определенности, возможности формализации, полноту исходных данных, требования к конечному результату, а также ряд других свойств, характеристик, параметров и особенностей.
Размещено на http://www.allbest.ru/
На представленном выше рисунке отражена концептуальная архитектура задачного решающего комплекса. Интеллектуальная решатель взаимодействует с концептуальной моделью, которая, в свою очередь, взаимодействует с интеллектуальными интерфейсами, посредством которых в решатель загружаются пользовательские задачи.
Концептуальная модель задачи разрабатывалась на основе методов системно-комплексного анализа (СК - анализа) “внутреннего устройства задачи”, как целостной системы, и её внешнего окружения - среды существования задачи. Для успешного разрешения проблемы создания КМЗ использовались:
системно-комплексный подход и СК-анализ;
основы теории концептуального моделирования;
методологические аспекты метамоделирования;
технология концептуального метамоделирования (КММ - технология), а также метод раскрытия неопределённости системной задачи на уровне её концептуального представления, основанный на метазадачной технологии и рекурсивных механизмах, приводящий к рекурсивным и взаимнорекурсивным структурам системной КМЗ.
Изложенный подход к созданию и использованию КМЗ по своей сути может быть определен как концептуальная метамодельная технология автоматизированного описания, представления, постановки и решения системных задач.
Многоуровневое представление концептуальной модели системной задачи осуществляется на основе метода стратификации. Для формирования страт - уровней организации задачи необходим критерий или основание стратификации. В качестве такого критерия в рассматриваемом случае целесообразно выбрать показатель неопределённости системной задачи . В соответствие с указанным критерием введём качественную шкалу неопределённости. На шкале неопределённости ранжируем компоненты концептуальной модели, представленной системой кортежей (1), по степени возрастания неопределённости. При этом будет иметь место следующая последовательность страт - уровней неопределённости системной задачи:
конечного результата -- решения - ;
исходных данных (начальной информации) - ;
показателя адекватности - ;
программы решения задачи - ;
алгоритма решения задачи - ;
метода решения задачи - ;
цели системной задачи - ;
среды существования задачи - .
Графическая интерпретация шкалы неопределённости имеет вид, представленный на рис.1. В последовательности страт (см. рис. 1) определённость задачи возрастает при движении по шкале сверху вниз. При этом, каждый выделенный на шкале уровень - страта разбивает её на две части. Верхняя часть шкалы включает все известные (определённые) компоненты, а нижняя - компоненты, которые необходимо определить, т.е. неизвестные.
Рис. 2. Ранжированное представление компонентов системной задачи по шкале неопределённости
задача система концептуальный решение
Полное описание концептуальной модели задачи, а также методов и теорий их возникновения и т. п. даны в статье [1]. В рамках данной работы мы рассмотрим работу компонента генератора вспомогательной задачи.
Размещено на http://www.allbest.ru/
На рисунке выше представлены компоненты концептуальной модели системной задачи.
КМСЗ - концептуальная модель системной задачи
ПЦНД - критерии полноты, целостности, необходимости, достаточности
Ан-р - анализатор
ГВЗ - генератор вспомогательных задач
КМВЗ - концептуальная модель вспомогательной задачи
На основании концептуальной модели системной задачи, которая представляется концептом 0го ранга (К) мы разворачиваем пирамиду, каждым уровнем которой будут соответствующие концептуальные вспомогательные задачи (В).
Размещено на http://www.allbest.ru/
На рисунке выше представлена многоуровневая рекурсивная концептуальная модель задачной системы. От компонента 0го ранга мы рекурсивно переходим вниз на компоненты более низких рангов, причём каждый из них может быть рассмотрен как вершина своей пирамиды. По достижению результата мы возвращаемся наверх к первоначальной задаче.
Программная реализация представления концептуальной модели задачи
Решение задач посредством прямого расчёта
Первая технология, которая реализуется в представленном программной средстве - прямой расчёт. Сначала пользователь выбирает предметную область. Для примера рассмотрим задачу на простое прямолинейное движение.
Размещено на http://www.allbest.ru/
Программа загружает исходные данные предметной области, которые представляют собой формулы для вычисления всех возможных параметров. В нашем случае эти формулы таковы:
Набор переменных:
x - текущая координата
xs - начальная координата
v - текущая скорость
vs - начальная скорость
astart - начальное ускорение
t - время
to - время (1й корень решения уравнения движения относительно t)
tt - время (2й корень решения уравнения движения относительно t)
Формулы для вычисления:
Затем пользователь загружает непосредственно задачу.
Размещено на http://www.allbest.ru/
После нажатия кнопки решить мы получаем вывод вида:
Ввод (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
Таким образом, мы получаем решение задачи (подсчёт переменных посредством прямого математического расчёта, то есть подстановки) и проверку на удовлетворение полученного параметрам внешней среды.
Непосредственно рекурсия здесь не применяется, но если мы изменим условия задачи следующим образом:
Размещено на http://www.allbest.ru/
То есть приведём задачу к виду «на какую максимальную высоту поднялось тело», то получим следующий вывод:
Ввод (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/
Размещено на http://www.allbest.ru/
Судоку
Судоку (яп. ђ”“Ж су:доку) -- популярная головоломка-пазл с числами. В переводе с японского «су» -- «цифра», «доку» -- «стоящая отдельно». Иногда судоку называют «магическим квадратом», что в общем-то не верно, так как судоку является латинским квадратом 9-го порядка. Судоку активно публикуют газеты и журналы разных стран мира, сборники судоку издаются большими тиражами. Решение судоку -- популярный вид досуга.
Игровое поле представляет собой квадрат размером 9x9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), так как незаполненное игровое поле не имеет смысла. В зависимости от того, сколько клеток уже заполнены, конкретную судоку можно отнести к лёгким или сложным.
Существует несколько методов решения судоку. Условно их можно разделить на две категории - логические и вычислительные. К вычислительным методам относится метод полного перебора (BruteForce). Логические - метод одиночного квадрата, закрытого кандидата, голой и скрытой пары, крыло, slicing and dicing и методы предположений различного уровня.
Методы составления судоку начинаются с составления правильного латинского квадрата. Дальнейшее составление идёт либо постепенным вычёркиванием чисел и проверкой на возможность решения, с оценкой сложности по количеству итераций и применяемому методы, либо открытием определённого числа закрытых клеток. Причём как в первом, так и во втором случае вообще говоря судоку может получиться недетерменированным (то есть допускающим несколько вариантов решения для одних и тех же исходных данных).
Исходный вид разработанной программы при решении судоку такой:
Размещено на http://www.allbest.ru/
Решение судоку
Разрешение концептуальных моделей
Сначала рассмотрим решение при помощи вспомогательных концептуальных моделей. При нажатии на эту кнопку вызывается окно, в котором можно переключать просмотр по столбцам, строкам или малым квадратам. Элементами вспомогательной концептуальной модели являются непосредственно столбцы, строки или малые квадраты.
Рассмотрим на примере простого судоку:
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
При нажатии на кнопку «Решить текущие вспомогательные модели» программа выполнит решение для выделенной вспомогательной концептуальной модели, то есть в нашем случае попытается разрешить все квадраты.
Разрешение вспомогательной модели возможно только в том случае, если в данном конкретном элементе (в нашем случае это квадрат с левым верхним углом A4) отсутствует только одна цифра. В данном случае это верно, поэтому после нажатия данной кнопки мы получим результат:
Размещено на http://www.allbest.ru/
В случае нажатия на кнопку «Разрешить все вспомогательные модели» программа в бесконечном цикле будет проходить по всем возможным вспомогательным моделям до тех пор, пока они имеют решение. Принципиально это выглядит следующим образом:
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Метод полного перебора
Метод полного перебора действует следующим образом:
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с.
Размещено на http://www.allbest.ru/
Но существуют задачи, которые алгоритм полного перебора будет решать очень долго. Возьмём для примера судоку под названием «Star Burst Leo»
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Было оценено, что для решения данного судоку потребуется 641 580 331 итерация, причём в данном случае в итерации не входит процесс поиска цифр, которые можно внести в данную клетку.
На рисунке 16 показано распределение числа заполненных клеток (ось ординат) от уровня рекурсии (ось абсцисс). Таким образом можно оценить, что процесс перебора доходит до 72 заполненных клеток, а затем встречает несоответствие и ему приходится возвращаться, причём мы видим чёткие полосы в районе 33, 43 и 60 заполненных клеток.
Логические методы решения
Очевидно, что предложенный выше метод хорош для компьютерного моделирования. Но очевидно, что человек на практике никогда не будет пользоваться таким методом. Для этого существуют другие методы.
Обычно решение судоку начинают с расставления чисел, которые могут стоять в данной клетке. Первая часть метода аналогична методу полного перебора, но в отличие от него, сначала мы просто оцениваем элементы, которые могут стоять в клетках, а затем минимизируем количество вариантов. Пример подобного анализа представлен на рисунке ниже:
Размещено на http://www.allbest.ru/
Все методы рассматриваются в статье [2], но здесь я опишу несколько из них.
Первый метод - Х-крыло.
«X-крыло» -- позиция, когда один из кандидатов дважды (и только дважды) встречается в двух строчках головоломки. Эти кандидаты должны входить в две колонки, что обеспечивает формирование прямоугольного Х-крыла. Также две колонки с двумя (и только с двумя) клетками, которые содержат одинаковых кандидатов (входящие в две строки) также формируют X-крыло. Эти четыре клетки -- единственные возможные места расположения для «настоящих» кандидатов в этих строках или колонках. Другие подобные кандидаты, расположенные по периметру прямоугольника, образованного «настоящими» кандидатами, должны быть удалены. Возможно эта комбинация была названа X-крылом потому, что
Рассмотрим пример решения Х-крыла (рисунок вверху). Как видим, для легкости восприятия из кандидатов отображены только шестерки (был применен фильтр кандидатов -- программа Simple Sudoku это умеет делать).
Синие и ярко-зеленые ячейки формируют классическое «X-крыло» -- первая и девятая строчки имеют только по две ячейки с кандидатом 6, их разделяют две колонки (седьмая и восьмая), кандидаты образуют прямоугольник. «Настоящих» кандидатов представляют синие, или ярко-зеленые ячейки. Потому другие кандидаты в шестой и девятой колонках нужно удалить (они выделены желтым контуром).
Размещено на http://www.allbest.ru/
Slicind and dacing
Рассмотрим метод slicing and dacing на примере:
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
На первом шаге рассматриваются пересечения столбца и строки для цифры 1 в рамках квадрата G1-I3. Получается, что 1 может стоять либо на позиции H1 либо на позиции I1.
Размещено на http://www.allbest.ru/
На основе полученного результата на первом шаге просматривается полученная строка. В квадрате D1-F3 с учётом стоящей на позиции E8 единицы и полученной на первом шаге строки остаётся только одна позиция - D2. Таким образом, после работы алгоритма получаем судоку:
Размещено на http://www.allbest.ru/
Аналогичным образом можно получить единицы во всех остальных малых клетках.
Метод предположений похож на метод полного перебора. Но применяется он после применения вышеуказанных методов. Рассмотри на примере:
Размещено на http://www.allbest.ru/
При решении стандартными логическими методами (скрытые пары, скрытые квадраты и т. п.) решение не найдено:
Размещено на http://www.allbest.ru/
Но мы видим, что в клетках B3 и C3 может стоять только пара 46. Алгоритм делает предположение, что стоит в B3 стоит 4, доходит до несоответствия, ставит 6 и получает результат:
Размещено на http://www.allbest.ru/
Таким образом исходное судоку разрешено.
Блок-схема алгоритма выглядит следующим образом:
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Составление судоку
Составление судоку может осуществляться двумя методами - либо сокрытием случайной ячейки после составления правильного латинского квадрата, либо наоборот открытием случайных ячеек. В первом случае после каждого шага выполняется решение и проверяется количество итераций и их сложность (применение методов первичных, slicing and dicing, предположений).
Составление открытием
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Но несмотря на то, что цифры из доски выполняется в порядке, обратном заполнению, всё равно возможно получение недетерменированного судоку и данную проблему разрешить невозможно.
Решение вычёркиванием
Решение вычёркиванием состоит в получении правильного латинского квадрата. Затем в полученном латинском квадрате рекурсивно осуществляются перестановки строк, столбцов и малых квадратов в соответствие с требованиями. Затем происходит вычёркивание случайного элемента и решение полученного судоку на основе методов решения. Сложность алгоритма определяется количеством итераций, которые необходимы для решения.
Заключение
В заключении можно отметить, что так как программа написана на 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 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],
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],
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.ru
...Подобные документы
Концептуальная модель задачи на основе триады "Задача–Данные–Решатель" и работа генератора вспомогательных концептуальных моделей. Разработка программы на языке Python, позволяющая решать любые задачи по заданным действительным математическим формулам.
курсовая работа [1,9 M], добавлен 27.11.2011Решение в среде Microsoft Excel с помощью программной модели "Поиск решения" транспортной задачи, системы нелинейных уравнений, задачи о назначениях. Составление уравнения регрессии по заданным значениям. Математические и алгоритмические модели.
лабораторная работа [866,6 K], добавлен 23.07.2012Краткий обзор решения транспортных задач. Экономическая интерпретация поставленной задачи. Разработка и описание алгоритма решения задачи. Построение математической модели. Решение задачи вручную и с помощью ЭВМ. Анализ модели на чувствительность.
курсовая работа [844,3 K], добавлен 16.06.2011Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.
контрольная работа [191,1 K], добавлен 05.04.2016Концептуальная модель операции. Математическая постановка задачи. Описание метода ветвей и границ, прямого перебора. Проектирование сценария диалога. Описание структур данных. Ручная реализация решения задачи с помощью алгоритма Литла и перебора.
курсовая работа [202,6 K], добавлен 14.12.2013Анализ и формализация задачи моделирования: построение концептуальной модели, ее формализация в виде Q-схемы. Построение имитационной модели: создание блок-схемы, представление базовой исходной имитационной модели. Исследование экономических процессов.
контрольная работа [156,0 K], добавлен 21.11.2010Построение концептуальной модели и метод имитационного моделирования. Определение переменных уравнений математической модели и построение моделирующего алгоритма. Описание возможных улучшений системы и окончательный вариант модели с результатами.
курсовая работа [79,2 K], добавлен 25.06.2011Классы и группы моделей представления знаний. Состав продукционной системы. Классификация моделей представления знаний. Программные средства для реализации семантических сетей. Участок сети причинно-следственных связей. Достоинства продукционной модели.
презентация [380,4 K], добавлен 14.08.2013Восстановление математической модели задачи нелинейного программирования. Решение уравнений прямых. Метод линеаризации: понятие, особенности применения при решении задач. Нахождение точки максимума заданной функции. Решение задачи графическим методом.
задача [472,9 K], добавлен 01.06.2013Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [607,2 K], добавлен 13.03.2015Оптимизационные модели на производстве. Компьютерное моделирование и программные средства. Трехмерное моделирование в T-Flex. Инженерный анализ в ANSYS. Интерфейс табличного процессора MS Excel. Построение математической модели задачи, ее реализация.
курсовая работа [5,2 M], добавлен 13.04.2014Информационный анализ и выявление основных сущностей предметной области и их основных свойств. Построение концептуальной модели (модель сущность-связь). Определение логической модели реляционной базы данных. Решение задач средствами проектирования СУБД.
курсовая работа [3,0 M], добавлен 25.11.2013Математические основы оптимизации. Постановка задачи оптимизации. Методы оптимизации. Решение задачи классическим симплекс методом. Графический метод. Решение задач с помощью Excel. Коэффициенты целевой функции. Линейное программирование, метод, задачи.
реферат [157,5 K], добавлен 21.08.2008Определение основных параметров грузоперевозок, их организационная структура. Виды и функции имитационного моделирования. Разработка концептуальной модели перевозки грузов, ее представление в виде системы массового обслуживания и программная реализация.
курсовая работа [761,6 K], добавлен 22.01.2012Учет книжного фонда библиотеки. Разработка концептуальной модели данных. Составление спецификации атрибутов и связей, генерация в системе PowerDesigner физической модели по концептуальной модели. Создание скрипта создания базы данных для СУБД FireBird.
контрольная работа [784,2 K], добавлен 10.04.2014Построение и использование математических и алгоритмических моделей для решения линейных оптимизационных задач. Освоение основных приемов работы с инструментом "Поиск решения" среды Microsoft Excel. Ввод системы ограничений и условий оптимизации.
лабораторная работа [354,7 K], добавлен 21.07.2012Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Понятие искусственного интеллекта и интеллектуальной системы. Этапы развития интеллектуальных систем. Модели представления знаний, процедурный (алгоритмический) и декларативный способы их формализации. Построение концептуальной модели предметной области.
презентация [80,5 K], добавлен 29.10.2013Понятие, основные задачи и функции общей теории систем как науки. Формулирование требований к системе, разработка концептуальной модели системы на примере системы массового обслуживания (СМО). Проектирование имитационной модели, ее реализация и испытание.
курсовая работа [131,3 K], добавлен 27.12.2010Реализация программы, позволяющей принять решение о выборе поставщика товаров, по аналогии с продукционной моделью представления знаний (сопоставления образцов и консиквентов). Математическая постановка задачи, программный алгоритм и этапы его разработки.
курсовая работа [812,8 K], добавлен 13.11.2012
