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

@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м.

Новые блоги и статьи Все статьи Все блоги /
Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .

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

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

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