Судоку, новое повальное увлечение Опции

[Lapp]

Кто знаком с игрой Судоку?
Она появилась не очень давно, несколько лет назад. Я не знаю, насколько она сейчас распространена в России, поэтому рассказываю подробно (извините, если это излишне). По смыслу и по виду напоминает кроссворд, но в отличие от него она не буквенная, а цифровая. Хотя, цифры там используются только как значки - никаких операций над ними (сложения и т.п.) не проводится. Говорят (и я охотно этому верю), что она прежде всего завоевала популярность в Японии, потому что бедные японцы, ввиду особенностей своей письменности, лишены возможности разгадывать кроссворды - хотя появилась она на Западе. Если сейчас зайти в любой книжный, то прямо у дверей увишь специальный стенд, на котором стоит десятка два-три как тонких так и очень толстых книг с этими головоломками..

Игра довольно тупая, но видя такой бешеный успех за короткое время, я заинтересовался ей. А тут ее стали еще публиковать в университетской газете - не попробовать я просто не мог . Как ни странно, это оказалось затягивающим, и на протяжении пары недель я свою ежедневную чашку кофе (см. фото в моем профайле ) стал посвящать этому занятию. Конечно, наскучило довольно быстро, но за это время я успел набросать небольшую прогу (сначала на Паскале, а потом на Дельфи), которая решала эти задачи. Вот я и выкладываю тут свой первоначальный паскалевский вариант..

Теперь о правилах. Поле представляет собой квадрат 9х9 клеток (поделенный еще и на подквадраты 3х3), в некоторых из которых уже стоят циферки, а в остальные их нужно вписать. В результате в каждой клетке должно стоять по цифре от 1 до 9 (ноль не участвует!), причем так, чтобы в любом столбце и в любой строчке присутствовали все девять цифр. Более того, в каждом подквадрате тоже должны быть все цифры, каждой по одной.

Правила очень простые. Существуют несколько методик решения, стратегий и тактик, которые разжевываются в книжках, но суть от этого не меняется. Ниже я привожу фото из университетской газеты (Bruin Daily, Apr 18, 2006), чтобы те, кто не видел, поимели представление.

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

Я предлагаю народу попробовать и, может быть, предложить свои алгоритмы. Код не вычищен, прошу извинить за огрехи. Но он работает (проверено на FPC и TP). Программа требует наличие файла sudoku.dat - он текстовый, это просто построковая запись квадрата, я прилагаю образец ниже.

 sudoku_1.pas ( 2.13 килобайт ) Кол-во скачиваний: 2787


Вот образец содержимого файла sudoku.dat. Важно: файл позиционный, то есть цифры сдигать нельзя. Более того, в строчке должны обязательно присутствовать все девять знаков (цифры и пробелы) - закрасьте приведенный пример блоком, чтобы увидеть пробелы, присутствующие там. Цифра обозначется цифрой, пустое место - пробелом или любым знаком (не цифрой или нулем). Лишних пробелов тоже быть не должно!

  8   2  
 51 3    
4  9 63  
53  7    
   8  96 
 7   9   
 6 5  1  
  3   4  
 1  8  2 

ВОт и все
Кому понравилось - откликайтесь.

[Bokul]

Вы как будто мои мысли читаете , я тоже щас пробую написать что-то подобное ,но с другим алгоритмом.

Вопрос:
А если наоборот - написать программу которая "делает" Судоку.
Решение вроде простое: заполнить массив случайными цифрами в случайных местах,
но появляется загвоздка - как обеспечить чтобы игра всегда имела решения?


И еще:

	  if Total=8 then begin
		c:=1;
		while c in List do Inc( c )
		Board[i,j]:=c;
		Ok:=true;
		ShowBoard(i,j)
	  end

[Lapp]

Вы как будто мои мысли читаете ,
.....
while c in List do Inc©;{здесь наверное вместо "собаки" должна стоять "с"}

И ты тоже мои читаешь - я оставил этот вопрос на второй пост
....
Там не "собака", там "копирайт" . Так переделвается (с) (здесь не должно переделаться, так как тут стоит русская "с")

[Bokul]

По поводу тестирования: проверял на таком файле

     8   
  85   1 
71   6   
  1      
6   4   5
 54  71  
4  18   7
 6    5  
   6     

програмка сразу вылетает, хотя решение существует

Код

546 718 392
298 534 716
713 296 458

971 365 824
632 841 975
854 927 163

425 189 637
369 472 581
187 653 249

P.S Задача и решения взято с одноименной программы
если надо могу выложить программу(чуть больше двух мегов)

Сообщение отредактировано: volvo - 3.11.2006 0:18

[Lapp]

програмка сразу вылетает, хотя решение существует
.....
если надо могу выложить программу(чуть больше двух мегов)

Она не вылетает, она сообщает, что не может решить! Это тот самый случай (множественный выбор), который я описал выше, и который требует применения другого алгоритма! Так что нужно добавить алгоритм. Другие алгоритмы есть. Вот, например, один из них.

Хотим поставить определенную цифру - например, 1. Идем по подквадратам. Если в нем уже есть 1 - переходим к следующему. Если нет - смотрим, какие строки его секут и есть ли в них 1. Затем то же со столбцами. Если в результате остается только одно одно свободное место, где в этом подквадрате может стоять 1, то ставим ее туда.

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

Я же сказал - это самый первый вариант, самый простой алгоритм. Для затравки .

.....
Программу можешь выложить, но заранее скажу - я брать не буду. Я видел много в Инете, но весь интерес именно в том, чтоб сделать самому, на своих мыслях.

Добавлю еще, что делать их, конечно, интереснее, чем играть. Кстати, сейчас модно цифры расставлять в виде орнамента. Да и форму поля можно варьировать.
P.S.
в том примере, что ты выложил, есть пропущенные пробелы. Для выкладывания используй тег Code=pas, а не просто Code. Code пропускает некоторые пробелы в начале строки.

[GoodWind]

может лучше использовать разделитель между числами?
было бы удобнее составлять...

[Lapp]

было бы удобнее составлять...

Дело в том, что игра состоит не в том, чтобы составлять такие задачи. Более того, мне представляется, что "вручную" ее составить невозможно (или очень трудно). Когда я делал эту прогу, я делал так: беру газету с опубликованной задачей и построчно набиваю все в файл. А потом наслаждаюсь, как программа отгадывает за меня . Конечно, ничего интересного в этом нет, я это рассматриваю как промежуточный этап на пути к программе, которая сможет сама составлять задачи, причем по заданному орнаменту, а может быть, и на разных полях. Сейчас у меня наполовину готов интерфейс в Дельфи, там можно вписывать цифири в клетки. Но это все еще пока не то...

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

Код

---1---5-
-----93--
1---26--7
---9---15
6-2--3---
----6--9-
75----1--
4----5--8
2-83---4-

[Lapp]

Я немного подправил алгоритм: добавил перебор при множественном выборе. Таким образом, программа должна теперь находить все возможные решения. По всей видимости, она это и делает, хотя проверить это я не возьмусь . Скажем, в том примере, который привел ты, Bokul, решений 58884 ! Неудивительно, что первый вариант программы отказался ее решать..
Те задачи, которые я брал из местной газеты, полностью детерминированы - они имеют одно решение. Но если (случайно ) стереть в них одну циферку, то количество решений увеличивается, и неслабо.

Выкладываю новый код.
Я убрал из него (закомментировал) вывод по шагам, теперь выдаются только решения - по нажатии любой клавиши, кроме Esc и пробела. Esc выводит из программы, а пробел включает/отключает режим выдачи решений без остановки (это я сделал, когда рука устала держать клавишу при проверке примера Bokul'а ).

Метод перебора возможных комбинаций включает в себя рекурсию. В ТР, думаю, может происходить переполнение стека.. Я пробовал только в FPC.

Вот пока и все. Следите за новыми выпусками нашей программы!! ))))

 sudoku_2.pas ( 3.04 килобайт ) Кол-во скачиваний: 1960

[Bokul]

Жалко что тема затухла не найдя решения генерации судуку.
Я на одном форуме нашел скрипт только на C++, сам я его не знаю, ну только основы, хотя вроде в скрипте нету ничего специфичного, но если у кого-то есть желания и время заниматься "переводом" на досуге ... то вот сам скрипт:

 sudoku_1.cpp ( 5.99 килобайт ) Кол-во скачиваний: 1779

я тоже буду пробивать, но ничего не обещаю.

[Lapp]

Жалко что тема затухла не найдя решения генерации судуку.

Тема заглохла, да, но прогу ту я продолжил . Сделал некую утилиту для создания задач.
Вот скажи - что такое "генерация"? Это что - случайным образом (по мере возможности)? Если так, то не очень интересно..
Сейчас существует много сборников задач - по сотне, тысяче задач.. Можно купить любой, положить в сортир, и разгадывать раз в день.. Но прелесть не в том.
В каждом из этих сборников есть своя изюминка - задачи выглядят привлекательно внешне. Например, изначально цифры расставлены в форме орнамента какого-нить... В некоторых изменено стандартное поле (9х9)

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

[Bokul]

Вот скажи - что такое "генерация"? Это что - случайным образом (по мере возможности)? Если так, то не очень интересно..

Почему же, мне так интересно. Я так и не понял как обеспечить возможность решения при минимальном заполнении полей изначально.

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

Будем ждать.

Можешь сначала выложить исходник, а потом и объяснение к ниму. Или решения чересчур специфичное?

[DFooz]

http://rapidshare.de/files/29767339/ProSud.rar вот книжка про программирование судоку. Вроде на английском языке.

Переведённая аннотация

Отличная книга для тех, кто программирует головоломки. Полностью разобрано программирование японской головоломки судоку. Имеется исходный код, так что программу легко скомпилировать и запустить. Написана на языке Visual Basic 2005, но может быть переведена на любой другой язык программирования, так как алгоритмы хорошо расписаны.

Сообщение отредактировано: DFooz - 31.08.2006 19:22

[Dreamer]

Всем привет! Моё хобби - программирование в среде паскаль! Как здорово, что здесь собрадись мои единомышленники, если вы не против, я к вам присоединюсь! В данный момент я учусь Херсонском физико-техническом лицее и веду разработку компьютерный игры-головоломки Судоку! Моя мечта - поучавствовать в конкурсе по программированию, представить данную разработку на нём! Нетерпится показать её вам! Скачать её можно сдесь (исходный текст + модуль для рисования окошек и создания менюшик, его исходним я к сожалению не владею, но использую его для оформления програмки). Скачать это всё в архиве можно здесь... Обсуждение програмке так же ведётся на форуме Херсонской локальной компьютерной сети... Вот вам на всякий случай адресок... Делитесь впечатлениями, пожеланиями и комментариями! Искренне буду благодарен!

[Michael_Rybak]

Моя мечта - поучавствовать в конкурсе по программированию, представить данную разработку на нём!

(Не смотрел прогу, просто говорю) На МАН можешь пойти с ней. Знаешь про МАН?

[Dreamer]

(Не смотрел прогу, просто говорю) На МАН можешь пойти с ней. Знаешь про МАН?

Знаю, я как раз туда и иду скоро! Хотя... толку та... Никаких шансов с Паскалем...

[Michael_Rybak]

С Паскалем (ну Дельфи, но все-таки) у меня было абсолютно первое место на городе. Так что все зависит от контента а не языка ;)

Посмотрел твою прогу. Прикольно Когда будешь защищаться, обязательно скажи, что в ближайших планах у тебя - дописать решалку.

Удачи. Сходишь - отпишись

[klem4]

А что за МАН такой ?

[Michael_Rybak]

Малая Академия Наук (ср. НАН = Национальная Академия Наук).

Украинский конкурс по школьным предметам, в т.ч. информатика. Что-то типа курсовой надо написать, проект какой-нибудь интересный, защитить его, +профильную олимпиаду написать. Т.е. баллы состоят из контент+защита+олимпиада.

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

У меня был проект "сборник головоломок с решениями", даже где-то диск лежит, вроде. Около 35 головоломок по всяким тематикам, с кучей прикольных алгоритмов (в том числе, кстати, судоку с решалкой и генерилкой красивых (симметричных) задач; тогда она еще не была так популярна).

[Dreamer]

Решалка кстати дома лежит... недоднланная... алгоритм ясен как пень... но чёт решает тока в основном простые уровни ((( Может ещё доделаю... Благодарен за внимание! Если кто-какие лаги видит - пишите! Попытаюсь устранить!

[Michael_Rybak]

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