ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Судоку. Какие бывают зависимости?
24 сообщений из 24, страница 1 из 1
Судоку. Какие бывают зависимости?
    #39603198
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Неделю уже разглядываю эту ситуацию и ничего в голову не приходит.

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

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

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

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

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

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

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

PPS m7m, мне надо с объяснением, т.е. надо правило, на основании которого решение принято.
...
Рейтинг: 0 / 0
16.02.2018, 17:11
| Ответить | Цитировать | Написать  
Судоку. Какие бывают зависимости?
    #39603226
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
https://play.google.com/store/apps/details?id=com.brainium.sudoku.free
Рекомендую попробовать, она умеет давать подсказки с объяснением.
...
Рейтинг: 0 / 0
16.02.2018, 17:13
| Ответить | Цитировать | Написать  
Судоку. Какие бывают зависимости?
    #39603228
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
miksoftВерхний левый квадрат - 9 может быть только в верхней строке, т.к. в средней строке она находится в верхнем правом квадрате.
Точно 9 в А2, только из-за правого квадрата, где 9 посредине.
...
Рейтинг: 0 / 0
16.02.2018, 17:15
| Ответить | Цитировать | Написать  
Судоку. Какие бывают зависимости?
    #39603229
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Dima TmiksoftВерхний левый квадрат - 9 может быть только в верхней строке, т.к. в средней строке она находится в верхнем правом квадрате.
Точно 9 в А2, только из-за правого квадрата, где 9 посредине.ага, а из этого вытекает 8 на A5 и I6
...
Рейтинг: 0 / 0
16.02.2018, 17:17
| Ответить | Цитировать | Написать  
Судоку. Какие бывают зависимости?
    #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, 17:22
| Ответить | Цитировать | Написать  
Судоку. Какие бывают зависимости?
    #39603274
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Dima TКто-нибудь знает какой следующий ход сделать в данном примере?
Девятку в клетку А2.

Я в своё время писал программу, которая использует несколько более развитых зависимостей, но и она иногда натыкается на судоку, которые не в силах решить строгой логикой. В данном случае дважды используется совершенно очевидная зависимость: если в одном пуле (строке, столбце, квадрате) есть две ячейки с кандидатами (А, Б), то в других ячейках таких кандидатов быть уже не может. Согласно этой зависимости, пара (8, 9) в ячейках B7 и B8 убирает девятку из ячеек B2 и B3, а получившаяся пара (1, 7) убирает семёрку из А2.
...
Рейтинг: 0 / 0
16.02.2018, 18:21
| Ответить | Цитировать | Написать  
Судоку. Какие бывают зависимости?
    #39603276
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Соколинский БорисDima T,
В данном случае в 6-м столбце в двух ячейках 1,2. Ясно, что в остальных ячейках столбца что-то другое.
Тут Вы не правы. Это правило работает только если в ячейках именно 1,2. В данном же случае может быть так: в ячейке E6 единица, в ячейке F6 семёрка, а двойка в ячейке I6 (где по Вашему утверждению её не может быть).
...
Рейтинг: 0 / 0
16.02.2018, 18:24
| Ответить | Цитировать | Написать  
Судоку. Какие бывают зависимости?
    #39603278
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
softwarer,
В с6 и e6 - {1, 2} => во всех остальных ячейках 6-го столбца их нет => F6=7
...
Рейтинг: 0 / 0
16.02.2018, 18:32
| Ответить | Цитировать | Написать  
Судоку. Какие бывают зависимости?
    #39603279
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Соколинский Борисsoftwarer,
В с6 и e6 - {1, 2} => во всех остальных ячейках 6-го столбца их нет => F6=7
Да, точно. Сплю. Пора домой.
...
Рейтинг: 0 / 0
16.02.2018, 18:33
| Ответить | Цитировать | Написать  
Судоку. Какие бывают зависимости?
    #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, 18:40
| Ответить | Цитировать | Написать  
Судоку. Какие бывают зависимости?
    #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:01
| Ответить | Цитировать | Написать  
Судоку. Какие бывают зависимости?
    #39603301
m7m
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
m7m
Участник
Dima TPPS m7m, мне надо с объяснением, т.е. надо правило, на основании которого решение принято.
А вот здесь 21197635 и объяснение
...
Рейтинг: 0 / 0
16.02.2018, 19:19
| Ответить | Цитировать | Написать  
Судоку. Какие бывают зависимости?
    #39603309
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Пазл порешался. Все сошлось после 9 в А2 по совету miksoft 21197710

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

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

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

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


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