求解数独Fortran程序.doc

求解数独Fortran程序!*!程序说明：!主程序采用回溯法，先按顺序将每个未知数的位置坐标存入x、y数组中，!共有step个未知数。每个位置从1开始试验，若满足条件则t=t+1，试验!下一个未知数；若19均不能满足条件，则回溯到上一个未知数t=t-1，!将试验值+1，再进行循环。当循环到最后一个未知数时，若满足条件则输!出解；若回溯到第一个未知数时，填入19均不能满足条件，则数独无解。!子程序用来判断试验值是否满足条件。!m,n=未知数在校宫格中的位置，step=未知数个数，t=试验值在未知数中!的次序,A=存放数独值的数组，x,y=存放未知数坐标的数组!*program sudokuimplicit noneinteger i,j,m,n,k,step,tinteger A(1:9,1:9),x(81),y(81)logical flagt=0open(8,file=soku.txt)do i=1,9 !读入数独初值，未知数赋0 do j=1,9 read(8,(i2) A(i,j) if(A(i,j)=0)then t=t+1 step=t !计算未知数个数 x(t)=i y(t)=j endif enddoenddoclose(8)print (2x,9i2),(A(i,j),j=1,9),i=1,9)t=1print*,stepdo while(t=step) i=x(t) j=y(t) if(A(i,j)=9)then !若回溯到的上一个未知数值为9，则继续往前回溯 t=t-2 A(i,j)=0 goto 200 endif do k=A(i,j)+1,9 A(i,j)=k call judge(i,j,k,flag,A) !判断是否满足条件,若满足，退出循环，试验下一个未知数 if(flag.eqv.true.)then exit endif if(k=9.and.(flag.eqv.false.)then !若19均不能满足条件，回溯上一个未知数 t=t-2 A(i,j)=0 endif enddo 200 t=t+1 if(t=step+1)then print*,本数独解为： exit endif if(t=0.and.(flag.eqv.false.)then print*,本数独无解,再检查一下题目吧！ exit endifenddoprint (2x,9i2),(A(i,j),j=1,9),i=1,9)10 format(1x,3I3)End子程序：subroutine judge(vi,vj,k,flag,A)implicit noneinteger i,j,vi,vj,k,m,nlogical flaginteger A(1:9,1:9)flag=.true.m=mod(vi,3)+3*int(1-mod(vi,3)/3.)n=mod(vj,3)+3*int(1-mod(vj,3)/3.)do i=1,9 !判断行条件 if(A(i,vj)=k.and.i/=vi)then flag=.false. endifenddo do j=1,9 !判断列条件 if(A(vi,j)=k.and.j/=vj)then flag=.false. endifenddodo i=vi-m+1,vi-m+3 !判断小宫格条件 do j=vj-n+1,vj-n+3 if(i/=vi.or.j/=vj).and.A(i,j)=k)then flag=.false. end if enddoenddoend 输入数据格式示例：00000080040020805108390000704050008200500 0400800000 000000000000000100000000000 000每行一个数据，共82行。输出示例： 1 2 6 3 5 7 8 4 9 4 7 9 2 6 8 3 5 1 5 8 3 9 1 4 2 6 7 3 4 1 5 7 6 9 8 2 2