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

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

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

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

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

Нажмите для просмотра прикрепленного файла

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

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

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

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

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


И еще:

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нажмите для просмотра прикрепленного файла

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

Нажмите для просмотра прикрепленного файла
я тоже буду пробивать, но ничего не обещаю.

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

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

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

Будем ждать.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Есс!!! Доделал! То что нужно, доделал!!! Решает все Судоку, которые имеют решения! Вот она програмка!!! В сеансе игры - жмите Enter - всё будет решено!!!

Молодец

Только если решение не единственно, она виснет ;)

По моему она не виснет, просто не решает! Вопрос... А разве нужно решать НЕПРАВИЛЬНО составленные судоку? Я читал - Правильно составленные Судоку должны иметь ЕДИНСТВЕННОЕ РЕШЕНИЕ!!!

Лажа. Прога пишется за день на коленке. Вотъ мой вариант.

!

А вот это, простите, не Вашего ума дело - что пишется за сколько дней... Файл удален, ибо нарушает Правила форума (видно, от осознания собственной исключительности, мистер NightmareZ решил, что Правила Его не касаются? Он ошибся...) volvo

Итак, доделал немного прогу (добавил цветовую конфигурацию, устранил некоторые ошибки, объединил варианты в единую базу)... Нажмите для просмотра прикрепленного файла На Херсоннском обласном МАНЕ с ней сегодня занял 3е место!!! Бузумно этому рад На этом разработка Судоку мною в среде Турбо Паскаль официально завершена Благодарю за поддержку и внимание!

А я делал алгоритм построение карт..не поверите...месяц ))) Я выводил его методом проб и ошибок и вот наконец получилось!

Что ты подразумеваешь под алгоритмом построения карт?

Короче часть кода которая на ходу создавала "расклады" имеющие решения

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

И самое интересное.. Обычно задачи (публикуемые в газетах или сборниках) характеризуются уровнем сложности (типа от 1 до 5). Есть ли в твоей программе такое понятие? Если нету - то можно ли было бы его ввести, и как?

Сложность у меня подразумевает процент возможного возникновения цифры в конкретных квадратах. Чем сложность выше чем выше шанс что некоторые квадраты вообще будут без цифр, а это усложнит разгадку! Проверено 8) Алгоритм я уже не помню и смотреть лень, но в принципе всё случайным образом только вот сложность можно выбирать и всё 8) Да больше и не надо было тогда. Правда игра так и не увидела свет. Кстати я о ней как-то писал на форуме одном: http://www.gp32x.com/board/index.php?showtopic=35250&st=0 . Я её как-нибудь закончу 8) Щас правдо над карточной игрой с сюжетом работаю потихоньку.

Но как закончу если интересно выложу версию под винду(оригинальная версия под GP2X).

О я вспомнил что скоро будет gbax 2007(это соревнование игр среди девайсов psp, ds, gp2x) так что судоку туда вышлю, но решил его переписать полностью и вот пока я толком не начал(пока делаю процедуру вывода картинок с прозрачностью) я хотел спросить: есть ли какие-нибудь не сильно капитальные модификации судоку? Я о чём-то таком слышал. Просто думаю добавить пару режимов(оригинальный и ещё какой-нибудь).

Помогите срочно мне нада курсовую написать игру Судоку но нада в виде проекта а не .ехе плиз киньте(если есть) если нет то ответьте хоть(очень срочно плиз плиз плиз(зарание спс)

nevolia
да... и я собрался писать курсовик по судоку. Теперь тоже мучаюсь поиском алгоритмов генерации... да и проверки, отчасти...
Может кто нибудь обновить книгу, которую выкладывали на первой странице по программированию головоломок и судоку в частности?!

Хотите расскажу как генерировать карты, которые в любом случае будут иметь решение?? Может я щас допущу ошибку, но я давно программил и это как я помню, и так начнём:
Для начала заполните массив следующим образом:

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

Далее берем первые три столбца и меняем их местами между собой три раза(надеюсь я правильно помню). Потом делаем так же с столбцами 4-6 и 7-9. Потом начинаем делать тоже самое с строками...ну вот и всё.
Я к сожалению не уверен что я всё правильно помню, так что если чего поправьте меня плиз!

По моему даже не имеет значение какие строки и столбики мы меняем местами, и в каком порядке тоже.
Важно то, что числа можно менять только строками или столбиками.

Имеет. Столбцы и строки можно перемещать только внутри групп (1-3, 4-6, 7-9), в которых они стоят, иначе может статься так, что в блоке 3х3 окажется повторяющаяся цифра.

Кстати, карта, предложенная Game-lord нарушает это правило. Для того, чтобы данный алгоритм работал первоначальная матрица должна быть верна. Но нужно сразу сказать сам по себе такой способ генерации дает очень малое разнообразие карт.

Здравствуйте!
Я написал генератор карт судоку, но каким способом нужно убирать определённые цифры в ней, что бы получилась правильная раскладка судоку имеющая одно решение? )

всем привет, у меня курсовая на тему СУДОКУ, к сожалению я в программировании не очень, поэтому стопорюсь на самом элементарном, я построил таблицу а теперь не могу сделать так, чтобы она заполнялась с помощью открываемого файла формата "dat" вот алгоритм. прошу помочь

program sudoku;
uses
   crt;

const
   N=9;
   px=2;
   py=2;

type
 TPole = array [1..N,1..N] of integer;

var
 s,i,m:integer;
 Pole:TPole;

procedure Vvod (Name:String);
var
 f:text;
 s:string;
 i,j:Integer;
begin
 assign (f,Name);
 reset (f);
   for j:=1 to 9 do
    {begin}
     ReadLn(f,s);
     for i:=1 to 9 do
     Pole[1,i]:=Ord(s[i])-Ord('0');
   { end;

 end;
 begin
 assign (f,Name);
 reset (f);
 for i:= 1 to 9 do
 begin
    for j:=1 to 9 do Read;
    Readln(f);
 end;}

 close(f);
end;

procedure Tablica;
begin
ClrScr;

 gotoxy(px,py+1);
 write('I---------------------------------------------------------I');
 gotoxy(px,py+2);
 write('║   │   │   ║   │   │   ║   │   │   ║');
 gotoxy(px,py+3);
 write(I---------------------------------------------------------I');
 gotoxy(px,py+4);
 write('║   │   │   ║   │   │   ║   │   │   ║');
 gotoxy(px,py+5);
 write(I---------------------------------------------------------I');
 gotoxy(px,py+6);
 write('║   │   │   ║   │   │   ║   │   │   ║');
 gotoxy(px,py+7);
 write('I---------------------------------------------------------I');
 gotoxy(px,py+8);
 write('║   │   │   ║   │   │   ║   │   │   ║');
 gotoxy(px,py+9);
 write('I---------------------------------------------------------I');
 gotoxy(px,py+10);
 write('║   │   │   ║   │   │   ║   │   │   ║');
 gotoxy(px,py+11);
 write('I---------------------------------------------------------I');
 gotoxy(px,py+12);
 write('║   │   │   ║   │   │   ║   │   │   ║');
 gotoxy(px,py+13);
 write(I---------------------------------------------------------I');
 gotoxy(px,py+14);
 write('I---------------------------------------------------------I');
 gotoxy(px,py+15);
 write('I---------------------------------------------------------I');
 gotoxy(px,py+16);
 write('║   │   │   ║   │   │   ║   │   │   ║');
 gotoxy(px,py+17);
 write(I---------------------------------------------------------I');
 gotoxy(px,py+18);
 write('I---------------------------------------------------------I');
 gotoxy(px,py+19);
 write('I---------------------------------------------------------I');
 gotoxy(px,py+20);

end;
     {osnovnaia programa}
begin
 Vvod ('d:\sudoku.dat');
 Tablica;

readln;
end.

М

Теги!! Правила Форума, п.5, и правила раздела Задачи, п.2 исправлено Также, желательно следить за кодировкой, когда копируешь.. исправлено

А что ты хочешь-то, melon? Прочитать файл, нарисовать таблицу в псевдографике и заполнить ее начальными данными?

Короче, melon, рисовать таблицу вручную - врагу не посоветую. Вот тебе прога, которая делает то, что ты просил (читает файл, выводит доску на экран) в текстовой моде. Она использует модуль TxGraph, который есть в FAQ, Псевдографика. Рисование линий, рамок и таблиц. .


Результат выглядит примерно вот так:

  ╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
  ║ 1 │   │   ║   │   │   ║   │   │ 9 ║
  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
  ║   │   │ 8 ║   │ 4 │   ║   │   │   ║
  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
  ║   │   │   ║   │   │   ║   │   │   ║
  ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
  ║   │ 5 │   ║   │ 9 │   ║   │ 6 │   ║
  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
  ║ 2 │   │   ║   │   │   ║   │   │   ║
  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
  ║   │   │   ║   │   │   ║   │ 1 │   ║
  ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
  ║   │   │ 2 ║   │ 7 │   ║   │   │ 3 ║
  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
  ║   │   │   ║   │   │ 5 ║   │   │   ║
  ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
  ║ 9 │   │   ║   │   │   ║   │ 4 │   ║
  ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝

(числа взяты наобум, это не есть реальное судоку)

у меня тема курсовой написать игру СУДОКУ в паскале, вот я начал, сделал таблицу в ручную.) создал отдельно в блокноте таблицу с цифрами сохранил ее. в продолжении пытаюсь сделать так чтобы она заполнила моя таблицу! таблица выресовывается без проблем.

Да ну? прааавда?? Ну, я оооччень рад за тебя!!
Только не пойму - а зачем же ты выложил выше то крапи шит, которое даже не компилится?.. а, въехал.. это прикол такой что ли, да? мне сейчас типа нужно кататься по полу и помирать со смеху? ну, ты шутник, дыня! ))..