回 帖 发 新 帖 刷新版面

主题:用pascal解数独

我用pascal编了一个解数独的程序,结果老是没能成功,哪位大师可以帮在下一把啊,帮我找出错误之处!!!谢谢
program exe_1;
type
x=array[1..9,1..9]of integer;
var
  a:x;
  b:array[1..9,1..9] of boolean;
  i,j,y:integer;
  t:text;
function yes(i,j:integer; a:x):boolean;
  var
    k:integer;
  begin
    yes:=true;
    for k:=1 to 9 do
      if (a[i,j]=a[i,k]) and (k<>j) then
        begin
          yes:=false;
          exit;
        end;
    for k:=1 to 9 do
      if (a[i,j]=a[k,j]) and (k<>i) then
        begin
          yes:=false;
          exit;
        end;
    if (i mod 3=1 ) and (j mod 3=1) then
      if (a[i,j]=a[i+1,j+1]) or (a[i,j]=a[i+1,j+2]) or
         (a[i,j]=a[i+2,j+1]) or (a[i,j]=a[i+2,j+2]) then
        begin
          yes:=false;
          exit;
        end else
     if (i mod 3=1 ) and (j mod 3=2) then
       if (a[i,j]=a[i+1,j-1]) or (a[i,j]=a[i+1,j+1]) or
          (a[i,j]=a[i+2,j-1]) or (a[i,j]=a[i+2,j+1]) then
        begin
          yes:=false;
          exit;
        end else
     if (i mod 3=1 ) and (j mod 3=0) then
       if (a[i,j]=a[i+1,j-1]) or (a[i,j]=a[i+1,j-2]) or
          (a[i,j]=a[i+2,j-1]) or (a[i,j]=a[i+2,j-2]) then
        begin
          yes:=false;
          exit;
        end else
     if (i mod 3=2 ) and (j mod 3=1) then
      if (a[i,j]=a[i-1,j+1]) or (a[i,j]=a[i-1,j+2]) or
         (a[i,j]=a[i+1,j+1]) or (a[i,j]=a[i+1,j+2]) then
        begin
          yes:=false;
          exit;
        end else
    if (i mod 3=2 ) and (j mod 3=2) then
      if (a[i,j]=a[i-1,j-1]) or (a[i,j]=a[i-1,j+1]) or
         (a[i,j]=a[i+1,j-1]) or (a[i,j]=a[i+1,j+1]) then
        begin
          yes:=false;
          exit;
        end else
    if (i mod 3=2 ) and (j mod 3=0) then
      if (a[i,j]=a[i-1,j-1]) or (a[i,j]=a[i-1,j-2]) or
         (a[i,j]=a[i+1,j-1]) or (a[i,j]=a[i+1,j-2]) then
        begin
          yes:=false;
          exit;
        end else
    if (i mod 3=0) and (j mod 3=1) then
      if (a[i,j]=a[i-1,j+1]) or (a[i,j]=a[i-1,j+2]) or
         (a[i,j]=a[i-2,j+1]) or (a[i,j]=a[i-2,j+2]) then
        begin
          yes:=false;
          exit;
        end else
    if (i mod 3=0 ) and (j mod 3=2) then
      if (a[i,j]=a[i-1,j-1]) or (a[i,j]=a[i-1,j+1]) or
         (a[i,j]=a[i-2,j-1]) or (a[i,j]=a[i-2,j+1]) then
        begin
          yes:=false;
          exit;
        end else
    if (i mod 3=0 ) and (j mod 3=0) then
      if (a[i,j]=a[i-1,j-1]) or (a[i,j]=a[i-1,j-2]) or
         (a[i,j]=a[i-2,j-1]) or (a[i,j]=a[i-2,j-2]) then
        begin
          yes:=false;
          exit;
        end;
  end;
procedure try(i,j:integer; a:x);
  var
    k,g:integer;
  begin

    if j>9 then
      begin
        i:=i+1;
        j:=1;
      end;

    if (i>9) then
      begin
        for k:=1 to 9 do
          begin
             for g:=1 to 9 do write(a[k,g]);
             writeln;
          end;
        inc(y);
        writeln;
      end
    else
      begin
        if b[i,j] then
          begin
            for k:=1 to 9 do
              begin
                a[i,j]:=k;
                if yes(i,j,a) then try(i,j+1,a);
              end
          end
        else try(i,j+1,a);
      end;
  end;
begin
  assign(t,'ta.txt');
  reset(t);
  for i:=1 to 9 do
    begin
      for j:=1 to 9 do
        begin
          read(t,a[i,j]);
          if (a[i,j]=0) then b[i,j]:=true;
        end;
      readln(t);
    end;
  close(t);
  y:=0;
  try(1,1,a);
  writeln(y);
end.

回复列表 (共8个回复)

沙发

搜索效率太低

板凳

没看出什么错误来啊,如果速度太慢,就先把固定的填上,然后再搜索。

3 楼

你这个搜索效率太低了 
   
   这个比较快  网上的大师级的数独都能瞬间过~
program sudoku;
const
   st='123456789';
type
   xmlnode=array[1..9] of longint;
   linenode=array[1..9] of boolean;
   squarenode=array[1..3] of linenode;
var
   y:char;
   sum:integer;
   xml:array[1..9] of xmlnode;
   linex,liney:array[1..9] of linenode;
   square:array[1..3] of squarenode;
procedure init;
var i,j,a,b:integer;temp:char;temp1:integer;
begin
   sum:=0;
   fillchar(xml,sizeof(xml),0);
   fillchar(linex,sizeof(linex),true);
   fillchar(liney,sizeof(liney),true);
   fillchar(square,sizeof(square),true);
   for i:=1 to 9 do
      begin
         for j:=1 to 9 do
            begin
               read(temp);
               if temp='.' then xml[i][j]:=0
               else
                  begin
                     temp1:=pos(temp,st);
                     xml[i][j]:=temp1;
                     if linex[i][temp1] then linex[i][temp1]:=false else begin writeln('No solution!'); readln; halt; end;
                     if liney[j][temp1] then liney[j][temp1]:=false else begin writeln('No solution!'); readln; halt; end;
                     if i<=3 then a:=1
                     else
                        if i>=7 then a:=3
                        else a:=2;
                     if j<=3 then b:=1
                     else
                        if j>=7 then b:=3
                        else b:=2;
                     if square[a][b][temp1] then square[a][b][temp1]:=false else begin writeln('No solution!'); readln; halt; end;
                  end;
            end;
         readln;
      end;
end;
   

4 楼


procedure outit;
var i,j:integer;
begin
   for i:=1 to 9 do
      begin
         for j:=1 to 8 do
            write(xml[i,j]);
         writeln(xml[i,9]);
      end;
   writeln;
   inc(sum);
   if (sum>100) and (not ((y='y') or (y='Y'))) then
      begin
         write('此数独解数过多,若希望继续输出请输入Y,或按任何键退出:');
         readln(y);
         if not ((y='y') or (y='Y')) then halt;
      end;
end;
procedure search(v1,v2:integer);
var i,j,temp1,temp2,a,b:integer;
begin
   if v1>9 then begin outit; exit; end;
   if xml[v1][v2]<>0 then
      begin
         temp1:=v1;temp2:=v2+1;
         if v2+1>9 then begin temp1:=v1+1; temp2:=1; end;
         search(temp1,temp2);
      end
   else
      begin
         for i:=1 to 9 do
            begin
               if linex[v1][i] then
               if liney[v2][i] then
                  begin
                     if v1<=3 then a:=1
                     else
                        if v1>=7 then a:=3
                        else a:=2;
                     if v2<=3 then b:=1
                     else
                        if v2>=7 then b:=3
                        else b:=2;
                     if square[a][b][i] then
                        begin
                           xml[v1][v2]:=i;
                           linex[v1][i]:=false;
                           liney[v2][i]:=false;
                           square[a][b][i]:=false;
                           temp1:=v1;temp2:=v2+1;
                           if v2+1>9 then begin temp1:=v1+1; temp2:=1; end;
                           search(temp1,temp2);
                           xml[v1][v2]:=0;
                           linex[v1][i]:=true;
                           liney[v2][i]:=true;
                           square[a][b][i]:=true;
                        end;
                  end;
            end;
      end;
end;
begin
   y:='z';
   writeln('输入待解决的数独');
   writeln('"."->表示未填写的数');
   writeln('例如:');
   writeln('..1......');
   writeln('..2.3...4');
   writeln('...5..6.7');
   writeln('5..14....');
   writeln('.7.....2.');
   writeln('....78..9');
   writeln('8.7..9...');
   writeln('4...6.3..');
   writeln('......5..');
   writeln('请输入:');
   init;
   search(1,1);
   if sum=0 then
   writeln('No solution!');
   writeln('此数独共有',sum,'组解');
   readln;
end.

5 楼

program shudu;
var a:array[1..9,1..9]of integer;
    b,c,d:array[1..9,1..9]of boolean;
    i,j:integer;
    k:char;
procedure try(x,y:integer);
var i,j:integer;
begin
  if ((x=9) and (y=9)) then
  begin
    for i:=1 to 9 do
      if (b[x,i]) then a[x,y]:=i;
    for i:=1 to 9 do
    begin
      for j:=1 to 9 do
        write(a[i,j]);
      writeln;
    end;
    close(input);
    close(output);
    halt;
  end;
  if a[x,y]=0 then
  begin
    for i:=1 to 9 do
      if ((b[x,i]) and (c[y,i]) and (d[((x-1)div 3)*3+(y+2)div 3,i]=true)) then
      begin
        d[((x-1)div 3)*3+(y+2)div 3,i]:=false;
        b[x,i]:=false;
        c[y,i]:=false;
        a[x,y]:=i;
        if y=9 then try(x+1,1)
               else try(x,y+1);
        a[x,y]:=0;
        d[((x-1)div 3)*3+(y+2)div 3,i]:=true;
        b[x,i]:=true;
        c[y,i]:=true;
      end;
  end
               else
  if y=9 then try(x+1,1)
         else try(x,y+1);
end;
{======main======}
begin
  fillchar(a,sizeof(a),0);
  fillchar(b,sizeof(b),true);
  fillchar(c,sizeof(c),true);
  fillchar(d,sizeof(d),true);
  assign(input,'shudu.in');
  reset(input);
  assign(output,'shudu.out');
  rewrite(output);
  for i:=1 to 9 do
  begin
    for j:=1 to 9 do
    begin
      read(k);
      if k<>' ' then
      begin
        a[i,j]:=ord(k)-48;
        b[i,ord(k)-48]:=false;
        c[j,a[i,j]]:=false;
        d[((i-1)div 3)*3+(j+2)div 3,a[i,j]]:=false;
      end;
    end;
    readln;
  end;
  try(1,1);
end.

6 楼

楼上厉害!我只是个初学者(PASCAL)

7 楼

可以用一个9*9的集合存放一个格子里能填什么数,搜索是会快很多,别忘记维护

8 楼

的确。。同意LS。
但是这样会很难编(意即编程复杂度会很高),而且每做出一次决策都会改动大量数组的值。。。
相比之下,还是存储一下横竖和每个九宫格的可行性较好。。

我来回复

您尚未登录,请登录后再回复。点此登录或注册