Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Судоку. Какие бывают зависимости? / 24 сообщений из 24, страница 1 из 1
16.02.2018, 16:48
    #39603198
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
Неделю уже разглядываю эту ситуацию и ничего в голову не приходит.

Маленькие цифры это все варианты, которые можно поставить в данную клетку.

Тут нет ни одной свободной клетки, куда можно было бы поставить только одну цифру.

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

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

Кто-нибудь знает какой следующий ход сделать в данном примере?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 16:52
    #39603202
Соколинский Борис
Соколинский Борис
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
Dima T,
Следующий ход - проверять количество ячеек в блоке с одинаковым потенциальным набором. Если таковых столько же, сколько цифр в наборе, исключать - весь набор из остальных ячеек блока.
В данном случае в 6-м столбце в двух ячейках 1,2. Ясно, что в остальных ячейках столбца что-то другое.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 16:52
    #39603204
m7m
m7m
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
Dima T,

8-ка в верхний ряд в 5-й столбец
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 16:56
    #39603206
m7m
m7m
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
m7mDima T,

8-ка в верхний ряд в 5-й столбец
В догонку
В Среднем квадрате 9-ка должна быть обязательно в 3-м ряду
и значит 9-ки в верхнем ряду у этого квадрата быть не может
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 17:03
    #39603209
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
Верхний левый квадрат - 9 может быть только в верхней строке, т.к. в средней строке она находится в верхнем правом квадрате.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 17:11
    #39603218
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
Соколинский БорисDima T,
Следующий ход - проверять количество ячеек в блоке с одинаковым потенциальным набором. Если таковых столько же, сколько цифр в наборе, исключать - весь набор из остальных ячеек блока.
В данном случае в 6-м столбце в двух ячейках 1,2. Ясно, что в остальных ячейках столбца что-то другое.
Мысль не понял. Можно поподробнее. И действие какое я должен сделать?

PS Добавил координаты на картинку.

PPS m7m, мне надо с объяснением, т.е. надо правило, на основании которого решение принято.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 17:13
    #39603226
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
https://play.google.com/store/apps/details?id=com.brainium.sudoku.free
Рекомендую попробовать, она умеет давать подсказки с объяснением.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 17:15
    #39603228
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
miksoftВерхний левый квадрат - 9 может быть только в верхней строке, т.к. в средней строке она находится в верхнем правом квадрате.
Точно 9 в А2, только из-за правого квадрата, где 9 посредине.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 17:17
    #39603229
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
Dima TmiksoftВерхний левый квадрат - 9 может быть только в верхней строке, т.к. в средней строке она находится в верхнем правом квадрате.
Точно 9 в А2, только из-за правого квадрата, где 9 посредине.ага, а из этого вытекает 8 на A5 и I6
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 17:22
    #39603230
Соколинский Борис
Соколинский Борис
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
Dima T,
Действие такое - выделять из блока подмножества ячеек с замкнутым набором.
Примерно так (N - число свободных ячеек)
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
type
  CSet=set of 1..9;
var 
  TotalSet: CSet;

// внешний цикл по всем комбинациям, O(N!)
TotalSet:=[];
for i:=1 to N do begin
  TotalSet:=TotalSet+C[i];  //объединяем множества
  If EnumCount(TotalSet)=N  then begin  //EnumCount - подсчет количества элементов в множестве.
    for J:=i+1 to N do C[i]:=C[i]-TotalSet; //исключаем весь набор из оставшихся элементов
     Break;
  end;   
end;
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 18:21
    #39603274
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
Dima TКто-нибудь знает какой следующий ход сделать в данном примере?
Девятку в клетку А2.

Я в своё время писал программу, которая использует несколько более развитых зависимостей, но и она иногда натыкается на судоку, которые не в силах решить строгой логикой. В данном случае дважды используется совершенно очевидная зависимость: если в одном пуле (строке, столбце, квадрате) есть две ячейки с кандидатами (А, Б), то в других ячейках таких кандидатов быть уже не может. Согласно этой зависимости, пара (8, 9) в ячейках B7 и B8 убирает девятку из ячеек B2 и B3, а получившаяся пара (1, 7) убирает семёрку из А2.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 18:24
    #39603276
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
Соколинский БорисDima T,
В данном случае в 6-м столбце в двух ячейках 1,2. Ясно, что в остальных ячейках столбца что-то другое.
Тут Вы не правы. Это правило работает только если в ячейках именно 1,2. В данном же случае может быть так: в ячейке E6 единица, в ячейке F6 семёрка, а двойка в ячейке I6 (где по Вашему утверждению её не может быть).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 18:32
    #39603278
Соколинский Борис
Соколинский Борис
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
softwarer,
В с6 и e6 - {1, 2} => во всех остальных ячейках 6-го столбца их нет => F6=7
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 18:33
    #39603279
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
Соколинский Борисsoftwarer,
В с6 и e6 - {1, 2} => во всех остальных ячейках 6-го столбца их нет => F6=7
Да, точно. Сплю. Пора домой.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 18:40
    #39603282
вонючий скунс
вонючий скунс
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
softwarerСоколинский БорисDima T,
В данном случае в 6-м столбце в двух ячейках 1,2. Ясно, что в остальных ячейках столбца что-то другое.
Тут Вы не правы. Это правило работает только если в ячейках именно 1,2. В данном же случае может быть так: в ячейке E6 единица, в ячейке F6 семёрка, а двойка в ячейке I6 (где по Вашему утверждению её не может быть).а что тогда будет в C6 и Е6 ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 18:40
    #39603283
вонючий скунс
вонючий скунс
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
а, опоздал )
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 19:01
    #39603297
Gennadiy Usov
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
miksoftDima Tпропущено...

Точно 9 в А2, только из-за правого квадрата, где 9 посредине.ага, а из этого вытекает 8 на A5 и I6
Далее, если А5 и I6 - 8, то G5 -1,G4 - 3, I5 -2. G7 -8, B8 -9
Пора обновить картинку.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 19:19
    #39603301
m7m
m7m
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
Dima TPPS m7m, мне надо с объяснением, т.е. надо правило, на основании которого решение принято.
А вот здесь 21197635 и объяснение
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 19:45
    #39603309
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
Пазл порешался. Все сошлось после 9 в А2 по совету miksoft 21197710

PS Надо было заскриншотить результат, а то пока ходил столько идей понаписали. Извиняюсь.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 21:28
    #39603337
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
Dima T,

задача такого рода есть хороший пример задач на удовлетворения ограничений(constraint satisfaction problem), и в какой то мере ее решение можно охарактеризовать твоей фразой Дмитрийвыбрать куда пойти, а в случае ошибки отмотать игру назад,
может быть пригодится этот пример
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.02.2018, 20:03
    #39603542
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
SashaMercuryее решение можно охарактеризовать твоей фразойDima Tметодом научного тыка выбрать куда пойти, а в случае ошибки отмотать игру назад
Пока, насколько мне известно, нет ни одной позиции, требующей использования МНТ. Как, впрочем, нет и строгого доказательства, что в абсолютно любой позиции хотя бы один из существующих способов или уберёт неподходящую цифру-кандидата, или вставит цифру-решение.

Применительно к показанной в исходном сообщении позиции - там просто-таки дофига различных вариантов движения к решению. Причём использующих простейшие техники.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.02.2018, 01:30
    #39603588
Lentan
Lentan
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
Akina там просто-таки дофига различных вариантов движения к решению. Причём использующих простейшие техники.
а, тупо:

для малых квадрат, 9!=362880 вариантов,
1) - отсечь из 9!, все не "подходящие" в каждом из 9-ти
2) - отсеть из `итого` п.1) для большого квадрата
...
перебор из остатка, если есть
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.02.2018, 01:43
    #39603590
Lentan
Lentan
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
1) - отсечь из 9!, все не "подходящие" в каждом из 9-ти
... и т.д.
купил теще, книженцу, решает...,
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.02.2018, 00:52
    #39603864
Шавлюк Евгений
Шавлюк Евгений
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Судоку. Какие бывают зависимости?
Когда-то сделал решатель судоку на SQL (firebird 2.5)
http://www.sql.ru/forum/925653/reshenie-sudoku-na-sql
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Судоку. Какие бывают зависимости? / 24 сообщений из 24, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]