Версия для печати темы

Автор: lapp 4.05.2006 9:46

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

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

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

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

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

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

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


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

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

Автор: Bokul 4.05.2006 10:28

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

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


И еще:

	  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 4.05.2006 10:54

Цитата(Bokul @ 4.05.2006 6:28)

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

Автор: Bokul 4.05.2006 10:56

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

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

Автор: lapp 4.05.2006 11:28

Цитата(Bokul @ 4.05.2006 6:56)

Автор: GoodWind 4.05.2006 14:17

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

Автор: lapp 4.05.2006 16:31

Цитата(GoodWind @ 4.05.2006 10:17)

Автор: lapp 5.05.2006 16:39

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

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

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

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

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

Автор: Bokul 25.07.2006 11:11

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

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

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

Автор: lapp 25.07.2006 11:53

Цитата(Bokul @ 25.07.2006 8:11)

Автор: Bokul 26.07.2006 5:31

Автор: DFooz 31.08.2006 19:21

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

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

Автор: Dreamer 29.01.2007 20:11

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


Прикрепленные файлы
 Sudoku.zip ( 35.21 килобайт ) Кол-во скачиваний: 852

Автор: Michael_Rybak 29.01.2007 21:33

Автор: Dreamer 30.01.2007 16:27

Цитата(Michael_Rybak @ 29.01.2007 16:33)

Автор: Michael_Rybak 30.01.2007 18:38

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

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

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

Автор: klem4 30.01.2007 18:44

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

Автор: Michael_Rybak 30.01.2007 23:27

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

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

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

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

Автор: Dreamer 31.01.2007 17:04

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

Автор: Michael_Rybak 31.01.2007 22:02

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

Автор: Dreamer 5.02.2007 19:23

Цитата(Michael_Rybak @ 31.01.2007 17:02)

Автор: Michael_Rybak 6.02.2007 4:01

Цитата(Dreamer @ 5.02.2007 14:23)

Автор: Dreamer 6.02.2007 17:14

Цитата(Michael_Rybak @ 5.02.2007 23:01)

Молодец

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

Автор: NightmareZ 15.02.2007 21:47

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

!

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

Эскизы прикрепленных изображений

Автор: Dreamer 3.03.2007 3:48

Цитата(Michael_Rybak @ 30.01.2007 13:38)

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

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

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

Автор: X.XaM_MaX.X 9.03.2007 1:32

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

Автор: Lapp 9.03.2007 14:43

Цитата(X.XaM_MaX.X @ 8.03.2007 21:32)

Автор: X.XaM_MaX.X 9.03.2007 22:19

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

Автор: Lapp 10.03.2007 6:57

Цитата(X.XaM_MaX.X @ 9.03.2007 18:19)

Автор: X.XaM_MaX.X 20.04.2007 1:33

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

Автор: X.XaM_MaX.X 23.04.2007 2:33

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

Автор: nevolia 3.05.2007 1:07

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

Автор: guaro 19.05.2007 17:07

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

Автор: Game-lord 26.05.2007 21:56

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

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

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

Автор: wingman 8.01.2008 23:54

Цитата(Game-lord @ 26.05.2007 17:56)

Автор: Lir 20.03.2008 22:18

Цитата(wingman @ 8.01.2008 19:54)

Автор: Djoker 13.04.2008 20:26

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

Автор: melon 3.06.2011 19:11

всем привет, у меня курсовая на тему СУДОКУ, к сожалению я в программировании не очень, поэтому стопорюсь на самом элементарном, я построил таблицу а теперь не могу сделать так, чтобы она заполнялась с помощью открываемого файла формата "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.

Автор: Lapp 4.06.2011 14:54

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

Автор: Lapp 4.06.2011 18:37

Короче, melon, рисовать таблицу вручную - врагу не посоветую. Вот тебе прога, которая делает то, что ты просил (читает файл, выводит доску на экран) в текстовой моде. Она использует модуль TxGraph, который есть в FAQ, http://forum.pascal.net.ru/index.php?showtopic=28423 .

program sudoku;
uses
   CRT,TxGraph;

const
   N= 9;
   x0= 3;
   y0= 3;
   dx= 4;
   dy= 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
    for i:=1 to 9 do
      Read(f,Pole[j,i]);
    ReadLn(f);
    if j mod 3=0 then ReadLn(f)
  end;
  close(f);
end;


procedure Tablica;
var
  i,j,k: integer;
begin
  for i:=0 to n do begin
    if i mod 3=0 then k:=2 else k:=1;
    TxHorLine(x0,x0+n*dx,y0+i*dy,k);
    TxVerLine(y0,y0+n*dy,y0+i*dx,k);
  end;
  for i:=1 to n do
    for j:=1 to n do
      if Pole[i,j]>0 then begin
        GoToXY(x0+(i-1)*dx+dx div 2,y0+(j-1)*dy+dy div 2);
        Write(Pole[i,j])
      end
end;

     {osnovnaia programa}
begin
  ClrScr;
  Vvod ('sudoku.dat');
  Tablica;
  Readln;
end.

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

Автор: melon 4.06.2011 22:07

Цитата(Lapp @ 4.06.2011 13:54)

Автор: Lapp 5.06.2011 6:37

Цитата(melon @ 4.06.2011 19:07)