Для тех кто не знает, суть игры такая:
Есть поле 9x9 в котором находятся цифры от 1..9.
Цель игры получить полностью заполненую таблицу, чтобы:
1) В каждой строке не было повторяющихся цифр
2) В каждом столбце не было повторяющихся цифр
3) Поле разбивается на квадраты 3x3 и в каждом из 9 квадратов, наконец,  не было повторяющихся цифр. Поясню про квадраты:


Номера квадратов в центре. 3) означает чтобы в 1..9 квадрате небыло повторяющихся цифр.
В начале игры дается частично заполненная таблица необходимо ее заполнить.

Кто может четко расписать алгоритм решения этой игры?

Ты его уже описал в пунктах 1-3

> алгоритм решения этой игры?


Ничего я не писал, это правила игры, это не алгоритм решения...

2 BaryVetaL ©  
Видел решение задачи о девяти ферзях ?

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

Да пожалуй это самое простое... Я уже в этом убедился. Попытался решить эту задачу методом перебора, причем перебор оптимизированный, то есть, если поле частично заполнено, ну например, в первой строке если есть уже цифры 1,2,5,6,7,8, то в пустые клетки этой строки подставляются только 3,4,9. Этот перебор ничего не дает. Слишком много комбинаций.
По скромным подсчетам: пусть из 81 клетки заполнено 36, тогда остается пустых 45 если в среднем взять что вариантов оптимизированого перебора на каждую клетку  3, то всего нужно перебрать 3^45=2954312706550833698643 вариантов! Это очень много... А если еще вариантов на каждую клетку больше? Нет в принципе решение найти можно... За часа 4 :)
Получаем задачу которая не решается перебором. Так, что Sphinx ты ошибаешься...

Дело в том что в правильно составленом судоку решение единственно и на каждем шаге есть клетка в которую можно однозначно не годая поставить цифру по этому просто нада перебирать все клетки в поисках определённой и ставить туда цифру а затем искать новую такую клетку. Алгоритм простой как 3 копейки. гораздо более интересен алгоритм гениразии судоку.

Все очень просто, решалку я такую для себя написал, после чего потерял к Судоку всякий интерес =)
У меня получилось два этапа проверки:
1) для каждой пустой клетки находим те числа, которые не встречаются на соответствующих столбце, ряде и квадрате. Если такое число одно, то ставим его и повторяем заново.
Если на первом шаге не нашлось подстановок, то выполняем шаг 2:
2) для каждой пустой клетки берем все наборы чисел, которые можно подставить в пустые клетки в соотв. ряде, столбце и квадрате. Если в исследуемую пустую клетку можно поставить число, которое нельзя поставить в другие пустые клетки - то ставим его и повторяем все с шага 1.

Если после 2го шага ничего не нашлось - значит есть неоднозначность или уже вся сетка заполнена :)

Играйте лучше в Sudeki :)

Много интересного на
http://en.wikipedia.org/wiki/Sudoku
только на английском.

Мое решение на язьіке Ruby. Алгоритм действительно очень простой. Ето моя первая программа на Ruby.

class Sudoku

 def initialize
   @len=9    
   @elem = [0,1,2,3,4,5,6,7,8,9]
   @sum = 45    
   @table=Array.new(@len)
   @table[0]=[7,0,0,5,3,0,8,0,9]
   @table[1]=[0,6,0,0,8,9,0,4,0]
   @table[2]=[0,9,8,0,2,4,0,3,0]
   @table[3]=[6,0,3,8,4,1,9,0,5]
   @table[4]=[0,1,9,0,5,0,4,6,0]
   @table[5]=[5,0,2,9,6,3,7,0,1]
   @table[6]=[0,8,0,3,1,0,6,9,0]
   @table[7]=[0,5,0,0,9,2,0,7,0]
   @table[8]=[9,0,6,0,0,8,1,0,2]
 end
 

 def each
   @table.each do |i|
     i.each do |n|
       yield n
     end  
     puts
   end
 end

 def each_index
   @table.each_index do |i|
     @table[i].each_index do |j|
       yield i,j
     end  
   end
 end

 def pencil_marks(i, j)        
   row = row(i)
   col = column(j)
   cube = cube(i/3, j/3)
   el = [0,1,2,3,4,5,6,7,8,9] - (cube + row + col).uniq!
   #puts "#{@table[i][j]} -> #{el}"    
   @table[i][j,1] = el if el.size == 1
 end

 def solved?
   @table.each do |row|
     rows = row.inject(0) {|sum, element| sum+element}
     if  rows != @sum then return false end
   end    
   return true
 end

 attr_reader:sum,:table,:len

 def row(i)
   @table[i]
 end
 
 def column(j)
   [@table[0][j],@table[1][j],@table[2][j],@table[3][j],@table[4][j],@table[5][j],@ table[6][j],@table[7][j],@table[8][j],]    
 end
 
 def cube(i,j)
   i*=3
   j*=3
   [@table[i][j],@table[i][j+1],@table[i][j+2],@table[i+1][j],@table[i+1][j+1],@table[i+1][j+2],@table[i+2][j],@table[i+2][j+1],@table[i+2][j+2]]
 end
end

puts "Sudoku"
sudoku = Sudoku.new
sudoku.each {|n| print "#{n}, "}
puts "Computing..."

loop do
 break if sudoku.solved?
 sudoku.each_index do |i,j|  
   if sudoku.table[i][j] == 0 then    
     sudoku.pencil_marks(i, j)  
   end
 end
end

puts "Done"
sudoku.each {|n| print "#{n}, "}

народ и все же есть у ого в делфи алгоритм?

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

о, слушай Renegat, может даш посмотреть этот код, очень нужно

Нет. Сам алгос дать не могу. Только в виде объяснений:

1) Запускаем цикл по всем незанятым клеткам:
 а) Получаем все занятые клетки, находящиеся с данной в одном столбце.
 б) Исключаем их из множества 1..9
 в) Далее смотрим в строке, затем в одном из блоков 3х3. Получаем и исключаем.
 г) Если в множестве осталось одно число - пишем его в клетку. Если два и более - пропускаем. Если ни одного - расклад не имеет решения.

Расклады средней сложности решаются примерно за 4 прохода такой штуковины. Самые сложные из решаемых этим способом - за 9-10.

> затем в одном из блоков 3х3.

*где есть данная клетка, конечно же

делать было нечего - набросал на новогодних праздниках

unit Unit1;

interface

uses
 Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
 Dialogs, StdCtrls, Grids;

type
 TForm1 = class(TForm)
   StringGrid1: TStringGrid;
   Button1: TButton;
   Button2: TButton;
   Button3: TButton;
   Button4: TButton;
   procedure Button1Click(Sender: TObject);
   procedure Button2Click(Sender: TObject);
   procedure FormCreate(Sender: TObject);
   procedure Button3Click(Sender: TObject);
   procedure Button4Click(Sender: TObject);
 private
   { Private declarations }
 public
   { Public declarations }
 end;

var
 Form1: TForm1;
 M:array of array[0..8,0..8] of string;
 mk:integer;
 
implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var
i,j:integer;
begin
for i:=0 to stringgrid1.ColCount-1 do
 for j:=0 to stringgrid1.RowCount-1 do
 begin
   stringgrid1.Cells[i,j]:='123456789';
 end;

end;

procedure TForm1.Button2Click(Sender: TObject);
var
i,j,k:integer;

procedure exVertHorizSqr(a,b:integer; c:char);
var
ii,jj:integer;
fr: TReplaceFlags;
begin
fr:=fr + [rfReplaceAll];
//horiz
for ii:=0 to stringgrid1.ColCount-1 do stringgrid1.Cells[ii,b]:=stringreplace(stringgrid1.Cells[ii,b],c,'',fr);
//vert
for ii:=0 to stringgrid1.RowCount-1 do stringgrid1.Cells[a,ii]:=stringreplace(stringgrid1.Cells[a,ii],c,'',fr);
if (b<3) then begin
 if a<3 then
  for ii:=0 to 2 do
   for jj:=0 to 2 do stringgrid1.Cells[jj,ii]:=stringreplace(stringgrid1.Cells[jj,ii],c,'',fr);
 if ((a>2)and(a<6)) then
  for ii:=0 to 2 do
   for jj:=3 to 5 do stringgrid1.Cells[jj,ii]:=stringreplace(stringgrid1.Cells[jj,ii],c,'',fr);
 if (a>5) then
  for ii:=0 to 2 do
   for jj:=6 to 8 do stringgrid1.Cells[jj,ii]:=stringreplace(stringgrid1.Cells[jj,ii],c,'',fr);
              end;
if ((b>2)and(b<6)) then begin
 if a<3 then
  for ii:=3 to 5 do
   for jj:=0 to 2 do stringgrid1.Cells[jj,ii]:=stringreplace(stringgrid1.Cells[jj,ii],c,'',fr);
 if ((a>2)and(a<6)) then
  for ii:=3 to 5 do
   for jj:=3 to 5 do stringgrid1.Cells[jj,ii]:=stringreplace(stringgrid1.Cells[jj,ii],c,'',fr);
 if (a>5) then
  for ii:=3 to 5 do
   for jj:=6 to 8 do stringgrid1.Cells[jj,ii]:=stringreplace(stringgrid1.Cells[jj,ii],c,'',fr);
              end;
if (b>5) then begin
 if a<3 then
  for ii:=6 to 8 do
   for jj:=0 to 2 do stringgrid1.Cells[jj,ii]:=stringreplace(stringgrid1.Cells[jj,ii],c,'',fr);
 if ((a>2)and(a<6)) then
  for ii:=6 to 8 do
   for jj:=3 to 5 do stringgrid1.Cells[jj,ii]:=stringreplace(stringgrid1.Cells[jj,ii],c,'',fr);
 if (a>5) then
  for ii:=6 to 8 do
   for jj:=6 to 8 do stringgrid1.Cells[jj,ii]:=stringreplace(stringgrid1.Cells[jj,ii],c,'',fr);
              end;

 stringgrid1.Cells[a,b]:=c;
end;

function ExpVHS(a,b:integer;c:char):boolean;
var
ii,jj,bol2:integer;
bol:boolean;
begin
if length(stringgrid1.Cells[a,b])<2 then begin result:=false; exit; end;
bol:=false;
// horiz
for ii:=0 to a-1 do if pos(c,stringgrid1.Cells[ii,b])<>0 then bol:=bol or true;
for ii:=a+1 to stringgrid1.ColCount-1 do if pos(c,stringgrid1.Cells[ii,b])<>0 then bol:=bol or true;
if not(bol) then begin result:=not(bol); exit; end;
//vert
bol:=false;
for ii:=0 to b-1 do if pos(c,stringgrid1.Cells[a,ii])<>0 then bol:=bol or true;
for ii:=b+1 to stringgrid1.RowCount-1 do if pos(c,stringgrid1.Cells[a,ii])<>0 then bol:=bol or true;
if not(bol) then begin result:=not(bol); exit; end;

//sqr
bol2:=0;
if (b<3)
then begin
 if a<3 then
  for ii:=0 to 2 do
   for jj:=0 to 2 do
                 if pos(c,stringgrid1.Cells[jj,ii])<>0 then inc(bol2);
 if ((a>2)and(a<6)) then
  for ii:=0 to 2 do
   for jj:=3 to 5 do
              if pos(c,stringgrid1.Cells[jj,ii])<>0 then inc(bol2);
 if (a>5) then
  for ii:=0 to 2 do
   for jj:=6 to 8 do
              if pos(c,stringgrid1.Cells[jj,ii])<>0 then inc(bol2);
end;  //b<3
if ((b>2)and(b<6))
then begin
 if a<3 then
  for ii:=3 to 5 do
   for jj:=0 to 2 do
              if pos(c,stringgrid1.Cells[jj,ii])<>0 then inc(bol2);
 if ((a>2)and(a<6)) then
  for ii:=3 to 5 do
   for jj:=3 to 5 do
              if pos(c,stringgrid1.Cells[jj,ii])<>0 then inc(bol2);
 if (a>5) then
  for ii:=3 to 5 do
   for jj:=6 to 8 do
              if pos(c,stringgrid1.Cells[jj,ii])<>0 then inc(bol2);
end; //((b>2)and(b<6))
if (b>5)
then begin
 if a<3 then
  for ii:=6 to 8 do
   for jj:=0 to 2 do
              if pos(c,stringgrid1.Cells[jj,ii])<>0 then inc(bol2);
 if ((a>2)and(a<6)) then
  for ii:=6 to 8 do
   for jj:=3 to 5 do
              if pos(c,stringgrid1.Cells[jj,ii])<>0 then inc(bol2);
 if (a>5) then
  for ii:=6 to 8 do
   for jj:=6 to 8 do
              if pos(c,stringgrid1.Cells[jj,ii])<>0 then inc(bol2);
end;  //b>5
if bol2>1 then result:=false
          else result:=true;
end;

begin
//in memory
mk:=mk+1;
setlength(M,mk+1);
for i:=0 to stringgrid1.ColCount-1 do
 for j:=0 to stringgrid1.RowCount-1 do M[mk][i,j]:=stringgrid1.Cells[i,j];

for i:=0 to stringgrid1.ColCount-1 do
 for j:=0 to stringgrid1.RowCount-1 do
   if length(stringgrid1.Cells[i,j])=1 then exVertHorizSqr(i,j,stringgrid1.Cells[i,j][1]);

for i:=0 to stringgrid1.ColCount-1 do
 for j:=0 to stringgrid1.RowCount-1 do
   for k:=1 to length(stringgrid1.Cells[i,j]) do
             if ExpVHS(i,j,stringgrid1.Cells[i,j][k])
              then begin
                stringgrid1.Cells[i,j]:=stringgrid1.Cells[i,j][k];
                break;
                   end;

end;

procedure TForm1.FormCreate(Sender: TObject);
var
i,j:integer;
begin
for i:=0 to stringgrid1.ColCount-1 do
 for j:=0 to stringgrid1.RowCount-1 do
 begin
   stringgrid1.Cells[i,j]:='123456789';
 end;
mk:=0;
end;

procedure TForm1.Button3Click(Sender: TObject);
var
i,j:integer;
begin
mk:=mk-1;
setlength(M,mk+1);
for i:=0 to stringgrid1.ColCount-1 do
 for j:=0 to stringgrid1.RowCount-1 do stringgrid1.Cells[i,j]:=M[mk][i,j];
end;

procedure TForm1.Button4Click(Sender: TObject);
begin
  close;
end;

end.

Удалено модератором

Удалено модератором

а так красивше малость будет