Обкатывал пятый алгоритм для программы решения судоку на Делфи. Четыре уже реализованы, но не все задачи решаются. Решение ТОЛЬКО логикой. Никаких переборов и пробных подстановок. Формулами в Excel реализовал 1, 2 и 5-й алгоритмы. Конечно, надо включить итерации и при вводе цифр из журнала не забывать нажимать F9. Иногда не отрабатывают циклы из-за массивных формул, особенно, если нажимать стрелочки. Активатор итераций не стал делать, может сильно притормозить. Excel решает задачи от 1 до 4 звёздочек сложности и половину 5 звёздочных. Формулы написаны в режиме защёлки. Откат не срабатывает. Можно безвозвратно испортить лист "Образец". Оптимизацией и протягиваемостью формул не утруждался. Версия Excel не ниже 2007.
Обкатывал пятый алгоритм для программы решения судоку на Делфи. Четыре уже реализованы, но не все задачи решаются. Решение ТОЛЬКО логикой. Никаких переборов и пробных подстановок. Формулами в Excel реализовал 1, 2 и 5-й алгоритмы. Конечно, надо включить итерации и при вводе цифр из журнала не забывать нажимать F9. Иногда не отрабатывают циклы из-за массивных формул, особенно, если нажимать стрелочки. Активатор итераций не стал делать, может сильно притормозить. Excel решает задачи от 1 до 4 звёздочек сложности и половину 5 звёздочных. Формулы написаны в режиме защёлки. Откат не срабатывает. Можно безвозвратно испортить лист "Образец". Оптимизацией и протягиваемостью формул не утруждался. Версия Excel не ниже 2007.Светлый
Сейчас читаю книгу "Стюарт Рассел, Питер Норвиг - Искусственный интеллект. Современный подход (2006)" (на пятой главе). В ней (книге) рассматривается в т.ч. решение подобных головоломок. На вскидку, данный случай (головоломку судоку) я бы охарактеризовал как "информированный поиск в конечном пространстве состояний" (опираясь на 4-ю главу данной книги).
скорее, решаются все, вопрос в том, за какое время и сколько памяти для этого потребуется =) Разумеется, при наличии полного алгоритма, "исследующего все" пространство состояний.
Решение ТОЛЬКО логикой. Никаких переборов и пробных подстановок.
чего?) Хотелось бы пояснения.
---
Было дело, писал на vba под эксель. Формулы никогда не интересовали) Признаться, в данный момент даже нет ms office на компе. Вместо него libre =)
---
p.s.: по прочтению 4-ой главы вышеупомянутой книги написал решение "игры 8", оно же подходит и для "пятнашек", впрочем, как и для любой другой квадратной матрицы. Только считать будет долго)
Сейчас читаю книгу "Стюарт Рассел, Питер Норвиг - Искусственный интеллект. Современный подход (2006)" (на пятой главе). В ней (книге) рассматривается в т.ч. решение подобных головоломок. На вскидку, данный случай (головоломку судоку) я бы охарактеризовал как "информированный поиск в конечном пространстве состояний" (опираясь на 4-ю главу данной книги).
скорее, решаются все, вопрос в том, за какое время и сколько памяти для этого потребуется =) Разумеется, при наличии полного алгоритма, "исследующего все" пространство состояний.
Решение ТОЛЬКО логикой. Никаких переборов и пробных подстановок.
чего?) Хотелось бы пояснения.
---
Было дело, писал на vba под эксель. Формулы никогда не интересовали) Признаться, в данный момент даже нет ms office на компе. Вместо него libre =)
---
p.s.: по прочтению 4-ой главы вышеупомянутой книги написал решение "игры 8", оно же подходит и для "пятнашек", впрочем, как и для любой другой квадратной матрицы. Только считать будет долго)
Бывают расстановки в судоку, которые логикой не решаются, если недостаточно информации для принятия решения. Например, из всего поля открыта только одна цифра, нельзя принять однозначное решение, как расстановлены остальные цифры. В данном случае решений может быть несколько либо одно, но которое логикой невозможно найти, тогда можно применять метод подстановок и перебора. Но как плюс, можно найти решение любого судоку (при условий верного его составления).
Бывают расстановки в судоку, которые логикой не решаются, если недостаточно информации для принятия решения. Например, из всего поля открыта только одна цифра, нельзя принять однозначное решение, как расстановлены остальные цифры. В данном случае решений может быть несколько либо одно, но которое логикой невозможно найти, тогда можно применять метод подстановок и перебора. Но как плюс, можно найти решение любого судоку (при условий верного его составления).MCH
Мои алгоритмы осуществляют "информированный поиск", то есть только то, что можно вывести логически. Наступает момент, когда нет логических предпосылок ни для одного действия - установки цифры или вычёркивания цифры из списка. В этот момент можно наугад выбрать одну из двух цифр в какой-то клетке и продолжить этими же алгоритмами. Если возникает противоречие, восстановим состояние и вызвавшую это противоречие цифру вычёркиваем. И т. д. Мой алгоритм не делает переборов вообще, поэтому работает "мгновенно". Я просто пытаюсь найти такие логические завязки, которые максимально раскроют цифры. 1. В клетке вычеркнуты все цифры кроме одной. Устанавливаем. 2. Во всех клетках группы осталась единственная цифра. Устанавливаем. 3. Во всех клетках группы остались 2 цифры, которые встречаются по 2 раза и только в двух клетках. Вычёркивание. 3а. В двух клетках группы две одинаковые цифры. Вычёркивание. 4. Пункт 3 и 3а, только для трёх цифр и клеток. Вычёркивание. 5. Если цифра есть в пересечении групп и её нет в оставшейся части группы, то и в оставшейся части пересекающейся группы её не может быть. Вычёркивание. Пересечения могут быть любыми. В простом случае это три клетки. Для фигурных судоку от двух до восьми. Для 3 и 4 пунктов как-то не придумал формулы.(Да не очень-то и хотелось ). 5 пункт сильно перекрывает 3 и 4.
p.s.: по прочтению 4-ой главы вышеупомянутой книги написал решение "игры 8", оно же подходит и для "пятнашек", впрочем, как и для любой другой квадратной матрицы. Только считать будет долго)
Для получения зачёта мои не самые умные учащиеся составляли программу решения "15". Там было строк 400-500, но всё работало.
Мои алгоритмы осуществляют "информированный поиск", то есть только то, что можно вывести логически. Наступает момент, когда нет логических предпосылок ни для одного действия - установки цифры или вычёркивания цифры из списка. В этот момент можно наугад выбрать одну из двух цифр в какой-то клетке и продолжить этими же алгоритмами. Если возникает противоречие, восстановим состояние и вызвавшую это противоречие цифру вычёркиваем. И т. д. Мой алгоритм не делает переборов вообще, поэтому работает "мгновенно". Я просто пытаюсь найти такие логические завязки, которые максимально раскроют цифры. 1. В клетке вычеркнуты все цифры кроме одной. Устанавливаем. 2. Во всех клетках группы осталась единственная цифра. Устанавливаем. 3. Во всех клетках группы остались 2 цифры, которые встречаются по 2 раза и только в двух клетках. Вычёркивание. 3а. В двух клетках группы две одинаковые цифры. Вычёркивание. 4. Пункт 3 и 3а, только для трёх цифр и клеток. Вычёркивание. 5. Если цифра есть в пересечении групп и её нет в оставшейся части группы, то и в оставшейся части пересекающейся группы её не может быть. Вычёркивание. Пересечения могут быть любыми. В простом случае это три клетки. Для фигурных судоку от двух до восьми. Для 3 и 4 пунктов как-то не придумал формулы.(Да не очень-то и хотелось ). 5 пункт сильно перекрывает 3 и 4.
p.s.: по прочтению 4-ой главы вышеупомянутой книги написал решение "игры 8", оно же подходит и для "пятнашек", впрочем, как и для любой другой квадратной матрицы. Только считать будет долго)
Для получения зачёта мои не самые умные учащиеся составляли программу решения "15". Там было строк 400-500, но всё работало.Светлый
Программировать проще, чем писать стихи.
Сообщение отредактировал Светлый - Четверг, 16.07.2015, 19:31
В свое время тоже делал решалку для Sudoku. Все расчеты сделаны на формулах, макрос перебора - строчек на 10 Данный способ подходит как для классического судоку так и для судоку с суммами
В свое время тоже делал решалку для Sudoku. Все расчеты сделаны на формулах, макрос перебора - строчек на 10 Данный способ подходит как для классического судоку так и для судоку с суммамиMCH
Вход
Регистрация
Напомнить пароль
Автосумма
Часто используемые
ВПР
ЕСЛИ
СУММЕСЛИ
Финансовые
Логические
Текстовые
Даты и времени 
Ссылки и массивы 
Математические
Другие функции
Проверка свойств и значений
Баз данных
Математические
Обработки массивов
Обработки строк
Преобразования типов данных 
Загрузки данных
Работы с файлами
Обработки системных параметров
Обработки цвета
Работы с датами и временем
Преобразования в системы счисления
Финансовые
). 5 пункт сильно перекрывает 3 и 4. 
