Делать было нечего. от скуки написал программу, решающую судоку

@alexu_007 · Регистрация: 29.05.2015

Студворк — интернет-сервис помощи студентам

Теперь не знаю, что с этим добром делать.

@_Ivana · 07.07.2016, 15:56

Сообщение от Evg

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

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

ЗЫ я решал сложные судоку на бумажке, и действовал точно так же. Вопрос только в наборе оптимизирующих критериев для выяснения возможных к заполнению цифр - чем их больше, тем меньше перебора, во многих случаях у нас на каждом шаге есть только один вариант заполнения какой-то клетки. Но нет гарантии, что в каких-то случаях их не будет больше. А твоя "программа-якобы решатель" просто имеет некоторый набор таких критериев, который на примере этой финской судоки не гарантировал единственности варианта на каждом шаге. Моя имеет свой набор критериев, но не расстраивается, если вариантов больше одного.

Evg · 07.07.2016, 19:33

Сообщение от _Ivana

А твоя "программа-якобы решатель" просто имеет некоторый набор таких критериев

Моя программа не имеет вообще никаких переборных критериев. Потому что она не перебирает, а решает (аналитически). Перебор лично я решением не считаю

@_Ivana · 07.07.2016, 19:43

Да всем уже давно понятно, что имеет и делает твоя программа и что ты считаешь и не считаешь. Приводи судоку 100*100 или какое там еще поле - попробуем сравнить.

@Sasha_Smirnov · 07.07.2016, 20:39

Сообщение от _Ivana

полностью пустое поле

Попробуйте, пожалуйста, _Ivana, свою программу с пустым полем 10×10 и 33×33 — хочу сравнить хронометраж Excel и Haskell: Расстановка случайных чисел в массиве 9х9, по правилам судоку!

Сообщение от Sasha_Smirnov

33 × 33

Evg · 07.07.2016, 21:01

Сообщение от _Ivana

Приводи судоку 100*100 или какое там еще поле - попробуем сравнить

Сравнить что?

@_Ivana · 07.07.2016, 22:28

Sasha_Smirnov, сейчас, перепишу на произвольный (кратный трем) размер поля - сейчас у меня на стандартном размере и пишутся цифры, переделаю в буквы.

Evg, уже ничего. Не смею более тревожить ваши убеждения.

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

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 + - - - - + - - - - + - - - - + - - - - + 
 | A B C D | E F G H | I J K L | M N O P | 
 | E F G H | M N O P | A B C D | I J K L | 
 | I J K L | A B C D | M N O P | E F G H | 
 | M N O P | I J K L | E F G H | A B C D | 
 + - - - - + - - - - + - - - - + - - - - + 
 | B D A C | H I J E | N K L F | P O M G | 
 | O K L N | P D A F | B M E G | H C I J | 
 | G M P I | N K B O | H C J A | F D L E | 
 | H E J F | C G L M | O P D I | K A B N | 
 + - - - - + - - - - + - - - - + - - - - + 
 | C A H B | F E I G | K D P M | J L N O | 
 | L G D M | K O N A | C I H J | B P E F | 
 | N P I J | D L M B | F E A O | C G H K | 
 | F O E K | J H P C | G L B N | D I A M | 
 + - - - - + - - - - + - - - - + - - - - + 
 | D H F A | L C E K | J G N B | O M P I | 
 | J C M O | G P H I | L A F E | N K D B | 
 | K L N E | B M D J | P O I C | G H F A | 
 | P I B G | O A F N | D H M K | L E J C | 
 + - - - - + - - - - + - - - - + - - - - +

Сообщение от Sasha_Smirnov

хочу сравнить хронометраж Excel и Haskell

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

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

@Sasha_Smirnov · 07.07.2016, 22:44

Там N элементов заполняют N² клеток, не повторяясь ни в одном ряду (кроме, может быть, диагоналей). То есть [суб]фрагментация на подквадраты вообще не производится (я тогда на это забил).

Ну вы скоростник, _Ivana! Только скорость-то так и не померили.

Сообщение от _Ivana

написано довольно давно

Ну и что? Экссель мой вообще прошлого века!

@_Ivana · 07.07.2016, 23:21

Сообщение от Sasha_Smirnov

не повторяясь ни в одном ряду

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

Сообщение от Sasha_Smirnov

Только скорость-то так и не померили.

Не вижу смысла, по нескольким причинам:
1) мы заполняем поля по разным правилам - я по правилам судоку
2) я ищу все заполнения, а не первое попавшееся (с оговорками)
3) мой кот неоптимален

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

Добавлено через 8 минут
UPD Sasha_Smirnov, а впрочем, хорошо - давайте я напишу именно генерацию поля N*N без повторений во всех строках и во всех столбцах (правильно я понял?), замерим для некоторых N

Сейчас накидаю

Добавлено через 25 минут
Вести с полей - вот вам поле (каламбурчик) 50*50 по вашим правилам:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
CKDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoavI
udpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoavICKDbOALmX
VhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoavICKDbOALmXudpF
NktfyoavICKDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiW
MPBelxrGczRJQHSiWNktfyoavICKDbOALmXudpFVhgEnsqTjUw
lxrGczRJQHSiWNktfyoavICKDbOALmXudpFVhgEnsqTjUwMPBe
EnsqTjUwMPBelxrGczRJQHSiWNktfyoavICKDbOALmXudpFVhg
dpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoavICKDbOALmXu
gEnsqTjUwMPBelxrGczRJQHSiWNktfyoavICKDbOALmXudpFVh
jUwMPBelxrGczRJQHSiWNktfyoavICKDbOALmXudpFVhgEnsqT
ICKDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoav
PBelxrGczRJQHSiWNktfyoavICKDbOALmXudpFVhgEnsqTjUwM
KDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoavIC
QHSiWNktfyoavICKDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJ
avICKDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyo
yoavICKDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktf
vICKDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoa
hgEnsqTjUwMPBelxrGczRJQHSiWNktfyoavICKDbOALmXudpFV
JQHSiWNktfyoavICKDbOALmXudpFVhgEnsqTjUwMPBelxrGczR
DbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoavICK
iWNktfyoavICKDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQHS
SiWNktfyoavICKDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQH
fyoavICKDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNkt
oavICKDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfy
BelxrGczRJQHSiWNktfyoavICKDbOALmXudpFVhgEnsqTjUwMP
XudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoavICKDbOALm
OALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoavICKDb
WNktfyoavICKDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSi
czRJQHSiWNktfyoavICKDbOALmXudpFVhgEnsqTjUwMPBelxrG
ktfyoavICKDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWN
mXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoavICKDbOAL
elxrGczRJQHSiWNktfyoavICKDbOALmXudpFVhgEnsqTjUwMPB
zRJQHSiWNktfyoavICKDbOALmXudpFVhgEnsqTjUwMPBelxrGc
UwMPBelxrGczRJQHSiWNktfyoavICKDbOALmXudpFVhgEnsqTj
TjUwMPBelxrGczRJQHSiWNktfyoavICKDbOALmXudpFVhgEnsq
GczRJQHSiWNktfyoavICKDbOALmXudpFVhgEnsqTjUwMPBelxr
bOALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoavICKD
nsqTjUwMPBelxrGczRJQHSiWNktfyoavICKDbOALmXudpFVhgE
xrGczRJQHSiWNktfyoavICKDbOALmXudpFVhgEnsqTjUwMPBel
sqTjUwMPBelxrGczRJQHSiWNktfyoavICKDbOALmXudpFVhgEn
LmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoavICKDbOA
wMPBelxrGczRJQHSiWNktfyoavICKDbOALmXudpFVhgEnsqTjU
qTjUwMPBelxrGczRJQHSiWNktfyoavICKDbOALmXudpFVhgEns
pFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoavICKDbOALmXud
RJQHSiWNktfyoavICKDbOALmXudpFVhgEnsqTjUwMPBelxrGcz
ALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoavICKDbO
rGczRJQHSiWNktfyoavICKDbOALmXudpFVhgEnsqTjUwMPBelx
tfyoavICKDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQHSiWNk
FVhgEnsqTjUwMPBelxrGczRJQHSiWNktfyoavICKDbOALmXudp
HSiWNktfyoavICKDbOALmXudpFVhgEnsqTjUwMPBelxrGczRJQ

А вот вам время: 0.02 secs (причем, это в интерпретаторе, без компиляции, с учетом вывода). Ну как, будем ~~Тузика с грелкой~~ Хаскель с Экселем сравнивать?

@Sasha_Smirnov · 07.07.2016, 23:58

Так уж сравнили. Спасибо!

Сообщение от Sasha_Smirnov

(код антипедагогичен)

Да и нет уже у меня этой моей поделки.

@_Ivana · 08.07.2016, 00:12

Сообщение от Sasha_Smirnov

Так уж сравнили. Спасибо!

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

zer0mail · 17.07.2016, 22:25

Сообщение от alexu_007

Во первых, финские учёные составляли и вряд-ли они так лажанулись.

Не лажанулись - я проверял. А вот известное судоку Шортц 301, которое встречается в учебниках, имеет несколько решений.

Добавлено через 16 минут

Сообщение от Evg

Перебор лично я решением не считаю

Перебор - это аналитическое решение "от противного". Предположим, что в этой ячейке стоит x. Тогда здесь будет y, здесь z... и приходим к противоречию. Значит, в этой ячейке x стоять не может.
Получается, что для "честного аналитического" решения противоречие возникает на 3-5 шаге (и остается одна непротиворечивая цифра), а для "неаналитического перебора" на 10м или 20м или 30м.

Новые блоги и статьи Все статьи Все блоги /
Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .
мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .	[EasyBuilder Pro] Памятка по разработке для панелей Weintek ФедосеевПавел 26.08.2026 Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .

@alexu_007 737 / 704 / 110 Регистрация: 29.05.2015 Сообщений: 4,348

	Делать было нечего. от скуки написал программу, решающую судоку 09.06.2016, 22:23. Показов 4387. Ответов 30 Метки нет (Все метки) Теперь не знаю, что с этим добром делать. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	07.07.2016, 19:43
	Да всем уже давно понятно, что имеет и делает твоя программа и что ты считаешь и не считаешь. Приводи судоку 100*100 или какое там еще поле - попробуем сравнить. 0