㈠ 用c語言寫一個簡易數獨的思路。要代碼
#include<stdio.h>
intnum[9][9],xy[9][9];
intcheck(intx,inty){
inti,m,n;
for(i=0;i<9;i++)
if((xy[x][y]==xy[i][y]&&i!=x)||(xy[x][y]==xy[x][i]&&i!=y))
return0;
for(i=0,m=x/3*3,n=y/3*3;i<9;i++)
if(xy[x][y]==xy[m+i/3][n+i%3]&&m+i/3!=x&&n+i%3!=y)
return0;
return1;
}
voidsearch(intx,inty){
if(x==9)
for(x=0;x<9;x++){
for(y=0;y<9;y++)
printf("%d",xy[x][y]);
printf(" ");
}
elseif(num[x][y])
search(x+(y+1)/9,(y+1)%9);
else
for(xy[x][y]=1;xy[x][y]<=9;xy[x][y]++)
if(check(x,y))
search(x+(y+1)/9,(y+1)%9);
return;
}
intmain(){
inti,j;
for(i=0;i<9;i++)
for(j=0;j<9;j++){
scanf("%d",&num[i][j]);
xy[i][j]=num[i][j];
}
search(0,0);
return0;
}
輸入為9行9列整數，已知的整數填寫對應的數字，尚待計算的未知數字填寫0。
該代碼的思路很簡單，就是從第一行第一列開始依次填入數字，檢查是否是在同一行、同一列、同一宮有沒有填入重復數字，如果沒有就繼續填入下一個數字，如果有就返回。
雖然效率稍低，但原理簡單、表述直白、易於理解，更有效率的代碼是使用十字鏈表完成，如有興趣可繼續深入
㈡ 如何用PASCAL編寫數獨程序 SUDOKU
空位用空格補齊（每用下劃線）
可以文件輸入（用編譯好的程序打開文件），亦可鍵盤輸入。
用打過CRT補丁的Turbo Pascal編譯，或使用Free Pascal(這個不保證正常)
樣例沒有超時，但對於特殊數據可能超時（我還沒有數據，自己寫得太簡單，但是，特殊數據基本不會不超過0.01s）
程序如下：
program sdjsq;{數獨解算器}
{-------------調用庫------------------------------------------------USES}
uses CRT,Dos;{使用CRT Dos庫}
{-------------數據類型定義------------------------------------------TYPE}
type
sz=0..9;{數字，byte類型的子界佔一byte}
sy=1..9;{same as sz}
sd=array [sy,sy] of sz;{數獨，佔8×8×1byte=81byte}
ss=set of sy;{數字的集合}
dot=
record
s:ss;
n,x,y:byte;
end;
{-------------變數定義-----------------------------------------------VAR}
var
a:sd;
x,y:byte;
list:record
num:byte;
dat:array [1..81] of dot;
end;
{=============列印邊框============================================PRINTK}
procere printk;
var
i, k : byte;
flag : boolean;
begin
gotoxy(1,1);textcolor(15);textbackground(0);
write(#218);for k:=1 to 8 do write(#196#194);writeln(#196#191);
for i := 1 to 9 do begin
write(#179);for k:=1 to 9 do begin
textbackground(1-ord(((i-1) div 3+(k-1) div 3) mod 2=0));
write(#32);textbackground(0);write(#179);
end;
writeln;
if i<>9 then begin
write(#195);for k:=1 to 8 do write(#196#197);writeln(#196#180);
end;
end;
write(#192);for k:=1 to 8 do write(#196#193);writeln(#196#217);
gotoxy(1,1);
end;
{=============可以填的數==============================================KY}
procere ky(a:sd;x,y:byte;var s:ss);
var
i,j:byte;
begin
s:=[1,2,3,4,5,6,7,8,9];
for i:=1 to 9 do if i<>x then s:=s-[a[i,y]];
for i:=1 to 9 do if i<>y then s:=s-[a[x,i]];
for i:=1 to 3 do for j:=1 to 3 do
if ((x-1)div 3*3+i<>x) and ((y-1)div 3*3+j<>y)
then s:=s-[a[(x-1)div 3*3+i,(y-1)div 3*3+j]];
s:=s-[0];
end;
{=============列印數據=============================================PRINT}
procere print(xn,yn,color:byte);
begin
gotoxy(2*xn,2*yn);
textcolor(color);
textbackground(5+ord(not ((x=xn)and(y=yn)))*(-4-ord(((xn-1) div 3+(yn-1) div 3) mod 2=0)));
if a[xn,yn]<>0 then write(a[xn,yn]) else write(#32);
gotoxy(1,1);
end;
{=============用鍵盤讀入數據===========================INPUT BY KEYBOARD}
procere inputbkb(var a:sd);
label 1;
var
xi,yi:byte;
c:char;
s:ss;i:byte;
begin
printk;
fillchar(a,sizeof(a),0);x:=1;y:=1;print(1,1,0);
textcolor(15);textbackground(0);
s:=[1..9];gotoxy(1,20);for i:=1 to 9 do write(i:2);
repeat
c:=readkey;
xi:=x;yi:=y;
case c of
(*#13{Enter}, #27{Esc}*)
#27:halt;
(*#72{Up}, #75{Left}, #77{Right}, #80{Down}*)
#0:begin
c:=readkey;
case c of
#75:if x<>1 then x:=x-1 else write('');
#72:if y<>1 then y:=y-1 else write('');
#80:if y<>9 then y:=y+1 else write('');
#77:if x<>9 then x:=x+1 else write('');
#83:a[x,y]:=0;
end;
end;
#48..#58:if (ord(c)-48 in s) or (c=#48)
then a[x,y]:=ord(c)-48 else write('');
end;
print(xi,yi,12);print(x,y,12);
ky(a,x,y,s);
gotoxy(1,20);
textcolor(15);textbackground(0);delline;
for i:=1 to 9 do if i in s then write(i:2);
until c=#13;
x:=0;y:=0;print(xi,yi,12);
end;
procere noans;
begin
gotoxy(1,20);
textbackground(0);delline;textcolor(143);
write('No answer!');
readkey;
halt;
end;
{=============用文件讀入數據===============================INPUT BY FILE}
procere inputbf(var a:sd;const path:string);
function Exist(Path:string):boolean;
var
S: PathStr;
begin
S := FSearch(Path, GetEnv(''));
Exist := S <> '';
end;
var
x,y:byte;
c:char;
f:text;
begin
if not exist(path) then begin
inputbkb(a);
end else begin
assign(f,path);reset(f);printk;
for y:=1 to 9 do begin
for x:=1 to 9 do begin
read(f,c);
if not (c in [#48..#58,#32]) then begin
inputbkb(a);exit;
end;
if c=#32 then a[x,y]:=0 else a[x,y]:=ord(c)-48;print(x,y,12);
end;
readln(f);
end;
end;
end;
{=============填入固定數據============================================TC}
procere tc;
var
x,y,i,t,n,f:byte;
s:ss;
function tct:byte;
var
i,j,k,l:byte;
s1,s2,s3:ss;
n1,n2,n3:array [1..9] of byte;
begin
tct:=0;
for i:=1 to 9 do begin
fillchar(n1,sizeof(n1),0);fillchar(n3,sizeof(n3),0);fillchar(n2,sizeof(n2),0);
for j:=1 to 9 do begin
ky(a,i,j,s);if a[i,j]<>0 then begin s:=[a[i,j]]; n1[a[i,j]]:=10; end;
for k:=1 to 9 do if k in s then if n1[k]=0 then n1[k]:=j else n1[k]:=10;
ky(a,j,i,s);if a[j,i]<>0 then begin s:=[a[j,i]]; n2[a[j,i]]:=10; end;
for k:=1 to 9 do if k in s then if n2[k]=0 then n2[k]:=j else n2[k]:=10;
ky(a,((i-1) mod 3)*3+((j-1) mod 3+1),((i-1) div 3)*3+((j-1) div 3+1),s);
if a[((i-1) mod 3)*3+((j-1) mod 3+1),((i-1) div 3)*3+((j-1) div 3+1)]<>0 then begin
s:=[a[((i-1) mod 3)*3+((j-1) mod 3+1),((i-1) div 3)*3+((j-1) div 3+1)]];
n3[a[((i-1) mod 3)*3+((j-1) mod 3+1),((i-1) div 3)*3+((j-1) div 3+1)]]:=10;
end;
for k:=1 to 9 do if k in s then if n3[k]=0 then n3[k]:=j else n3[k]:=10;
end;
for k:=1 to 9 do begin
j:=n1[k];
if j in [1..9] then begin
a[i,j]:=k;print(i,j,6);tct:=1;exit;
end;
end;
for k:=1 to 9 do begin
j:=n2[k];
if j in [1..9] then begin
a[j,i]:=k;print(j,i,6);tct:=1;exit;
end;
end;
for k:=1 to 9 do begin
j:=n3[k];
if j in [1..9] then begin
a[((i-1) mod 3)*3+((j-1) mod 3+1),((i-1) div 3)*3+((j-1) div 3+1)]:=k;
print(((i-1) mod 3)*3+((j-1) mod 3+1),((i-1) div 3)*3+((j-1) div 3+1),6);
tct:=1;exit;
end;
end;
end;
end;
procere check;
var
i,j,k:byte;
s,s1,s2,s3:ss;
begin
for i:=1 to 9 do begin
s1:=[];s2:=[];s3:=[];
for j:=1 to 9 do begin
if a[i,j]=0 then begin ky(a,i,j,s);s1:=s1+s; end else s1:=s1+[a[i,j]];
if a[j,i]=0 then begin ky(a,j,i,s);s2:=s2+s; end else s2:=s2+[a[j,i]];
if a[((i-1) mod 3)*3+((j-1) mod 3+1),((i-1) div 3)*3+((j-1) div 3+1)]=0 then begin
ky(a,((i-1) mod 3)*3+((j-1) mod 3+1),((i-1) div 3)*3+((j-1) div 3+1),s);s3:=s3+s;
end else s3:=s3+[a[((i-1) mod 3)*3+((j-1) mod 3+1),((i-1) div 3)*3+((j-1) div 3+1)]];
end;
for j:=1 to 9 do begin
if not (j in s1) then noans;
if not (j in s2) then noans;
if not (j in s3) then noans;
end;
end;
end;
begin
repeat
f:=0;
for x:=1 to 9 do
for y:=1 to 9 do
if a[x,y]=0 then begin
ky(a,x,y,s);t:=0;
if s=[] then
noans;
for i:=1 to 9 do if i in s then begin
t:=t+1;n:=i;
end;
if t=1 then begin a[x,y]:=n;print(x,y,14);f:=f+1; end;
end;
f:=f+tct;check;
until f=0;
end;
{=============遞歸求解===============================================TRY}
function answer:boolean;
var
ans:boolean;
procere try(num:byte);
var
i,j,n,x,y:byte;
s:ss;
begin
if keypressed then case readkey of #27:halt;#0:if readkey=#107 then halt; end;
if num<=list.num then begin
x:=list.dat[num].x;y:=list.dat[num].y;
ky(a,x,y,s);if s=[] then exit;
n:=random(8)+1;
for j:=n to n+8 do begin
i:=j mod 9+1;
if i in s then begin
a[x,y]:=i;print(x,y,10);
try(num+1);
a[x,y]:=0;print(x,y,0)
end
end
end else begin
gotoxy(1,20);textcolor(15);textbackground(0);delline;write('Complete!');answer:=true;ans:=true;
case readkey of #27:halt;#0:if readkey=#107 then halt; end;
textcolor(15);textbackground(0);gotoxy(1,20);delline;writeln('Trying...');
end;
end;
begin
answer:=false;ans:=false;
try(1)
end;
procere crtinit;
var
OrigMode: Word;
begin
OrigMode:=LastMode; { Remember original video mode }
TextMode(Lo(LastMode)+Font8x8); { use 43 or 50 lines on EGA/VGA }
end;
procere px;
var
l:array [1..9] of record
num:byte;
dat:array [1..81] of dot;
end;
i,j,k:byte;
d:dot;
begin
for i:=1 to 9 do l[i].num:=0;
for i:=1 to 9 do for j:=1 to 9 do if a[i,j]=0 then begin
d.x:=i;d.y:=j;ky(a,i,j,d.s);d.n:=0;for k:=1 to 9 do if k in d.s then inc(d.n);
inc(l[d.n].num);l[d.n].dat[l[d.n].num]:=d;
end;
list.num:=0;
for i:=1 to 9 do for j:=1 to l[i].num do begin
inc(list.num);list.dat[list.num]:=l[i].dat[j];
end;
end;
begin
randomize;
crtinit;
textbackground(0);clrscr;
if ParamCount=0 then inputbkb(a) else inputbf(a,ParamStr(1));
textcolor(15);textbackground(0);gotoxy(1,20);delline;writeln('Thinking...');tc;
textcolor(15);textbackground(0);gotoxy(1,20);delline;writeln('Checking...');px;
textcolor(15);textbackground(0);gotoxy(1,20);delline;writeln('Trying...');gotoxy(1,1);
if not answer then noans;
textcolor(15);textbackground(0);gotoxy(1,20);delline;writeln('That''s all!');readkey;
end.
㈢ 求用C語言編寫一個解數獨的程序，急
用0代表要填的數
#include <stdio.h>
#include <stdlib.h>
#define SIZE 9
#define get_low_bit(x) ((~x&(x-1))+1)
struct{
int left;
char num;
char try;
}board[SIZE][SIZE];
int bit2num(int bit)
{
switch(bit){
case 1:case 2:
return bit;
case 4:
return 3;
case 8:
return 4;
case 16:
return 5;
case 32:
return 6;
case 64:
return 7;
case 128:
return 8;
case 256:
return 9;
}
}
void printf_res()
{
int i, j, k;
for(i=0; i<SIZE; i++)
{
if(i%3==0)
{
for(j=0; j<SIZE*2+4; j++)
putchar('-');
putchar('\n');
}
for(j=0; j<SIZE; j++)
{
if(j%3==0)
putchar('|');
if(board[i][j].num > 0)
printf("\033[0;31m%2d\033[0m", board[i][j].num);
else
printf("%2d", board[i][j].try);
}
printf("|\n");
}
for(i=0; i<SIZE*2+4; i++)
putchar('-');
putchar('\n');
}
void sub(int i, int j, int bit)
{
int k, m;
for(k=0; k<SIZE; k++)
{
board[k][j].left &= ~bit;
board[i][k].left &= ~bit;
}
for(k=i/3*3; k<(i/3+1)*3; k++)
for(m=j/3*3; m<(j/3+1)*3; m++)
board[k][m].left &= ~bit;
}
void init()
{
int i, j;
for(i=0; i<SIZE; i++)
for(j=0; j<SIZE; j++)
if(board[i][j].num > 0)
sub(i, j, 1<<(board[i][j].num-1));
else if(board[i][j].try > 0)
sub(i, j, 1<<(board[i][j].try-1));
}
void add(int i, int j, int bit)
{
int k, m;
for(k=0; k<SIZE; k++)
{
board[k][j].left |= bit;
board[i][k].left |= bit;
}
for(k=i/3*3; k<(i/3+1)*3; k++)
for(m=j/3*3; m<(j/3+1)*3; m++)
board[k][m].left |= bit;
}
void solve(int pos)
{
int i=pos/SIZE;
int j=pos%SIZE;
int bit, left;
if(pos == SIZE*SIZE)
{
printf_res();
exit(0);
}
if(board[i][j].num > 0)
solve(pos+1);
else
for(left=board[i][j].left; left; left&=(left-1))
{
bit = get_low_bit(left);
sub(i, j, bit);
board[i][j].try = bit2num(bit);
solve(pos+1);
add(i, j, bit);
board[i][j].try=0;
init();
}
}
int main()
{
int i, j, c;
for(i=0; i<SIZE; i++)
for(j=0; j<SIZE; j++)
{
while((c=getchar())<'0' || c>'9')
;
board[i][j].num = c-'0';
board[i][j].try = 0;
board[i][j].left = 0x0001FF;
}
init();
solve(0);
return 0;
}
㈣ 數獨怎麼做
單向掃看法:在第一個例子中,我們注意看一下第2宮。
我們知道,每個宮內必須包含數字9,第1宮以及第3宮中都包含數字9,並且第1宮的9位於第3行。
第3宮的9位於第2行，這也就意味著第2宮的9不能在第2行和第3行，所有第2宮的9隻能放置在第2宮第1行的空格內。
2.雙向掃看法:同樣的技巧也可以擴展到相互垂直的行與列中。讓我們想一下第3宮中1應該放在哪裡。在這個例子中,第1行以及第2行已經有1了,那麼第3宮中只有底部的倆個空格可以填1。不過，方格g4已經有1了，所有第g列不能再有1。
所以i3是該宮唯一符合條件填上數字1的地方。
3.尋找候選法:通常地,一個方格只能有一個數字的可能性,因為剩下的其他8個數字都已經被相關的行列宮所排除了。我們看一下下面例子中b4這個方格。b4所在的宮中已經存在了數字3，4，7，8，1和6位於同一行，5和9位於同一列，排除上述所有數字，b4隻能填上2。
4數字排除法：排除法是一個相對繁雜的尋找數字的方法。我們可以從c8中的1間接推出e7和e9必須包含數字1，不管這個1在哪個方格，我們可以確認的是，第e列的數字1肯定在第8宮內，所以第2宮內中間這一列就不可能存在數字1。因此，第2宮的數字一必須填在d2處。
㈤ 編一個數獨程序（只需要生成過程），PASCAL 好的追50分。
program sudoku;
const
s:array[1..81]of integer= (1,1,1,2,2,2,3,3,3,
1,1,1,2,2,2,3,3,3,
1,1,1,2,2,2,3,3,3,
4,4,4,5,5,5,6,6,6,
4,4,4,5,5,5,6,6,6,
4,4,4,5,5,5,6,6,6,
7,7,7,8,8,8,9,9,9,
7,7,7,8,8,8,9,9,9,
7,7,7,8,8,8,9,9,9);
var
u,d,l,r,c,g:array[0..236520]of longint;
size:array[0..324]of integer;
l1,l2,l3:array[1..729]of integer;
f:array[1..9,1..9]of integer;
procere cover(p:longint);
var p1,p2:longint;
begin
l[r[p]]:=l[p];r[l[p]]:=r[p];
p1:=u[p];
while p1<>p do
begin
p2:=l[p1];
while p2<>p1 do
begin
d[u[p2]]:=d[p2];u[d[p2]]:=u[p2];
dec(size[c[p2]]);
p2:=l[p2];
end;
p1:=u[p1];
end;
end;
procere recover(p:longint);
var p1,p2:longint;
begin
l[r[p]]:=p;r[l[p]]:=p;
p1:=d[p];
while p1<>p do
begin
p2:=r[p1];
while p2<>p1 do
begin
d[u[p2]]:=p2;u[d[p2]]:=p2;
inc(size[c[p2]]);
p2:=r[p2];
end;
p1:=d[p1];
end;
end;
procere prework;
var sum,i,j,k:longint;
begin
sum:=0;
for i:=1 to 9 do
for j:=1 to 9 do
for k:=1 to 9 do
begin
inc(sum);
l1[sum]:=i;l2[sum]:=j;l3[sum]:=k;
g[(sum-1)*324+81+(i-1)*9+k]:=1;//行
g[(sum-1)*324+162+(j-1)*9+k]:=1;//列
g[(sum-1)*324+(s[(i-1)*9+j]-1)*9+k]:=1;//九宮
g[(sum-1)*324+243+(i-1)*9+j]:=1;//格子
end;
for i:=1 to 236520 do
begin
l[i]:=i-1;r[i]:=i+1;
u[i]:=i-324;d[i]:=i+324;
end;//common
for i:=1 to 324 do
begin
u[i]:=i+236196;
d[i+236196]:=i;
end;//special
for i:=0 to 729 do
begin
l[i*324+1]:=(i+1)*324;
r[(i+1)*324]:=i*324+1;
end;//special
l[0]:=324;
r[0]:=1;
l[1]:=0;
r[324]:=0;//door
for i:=325 to 236520 do
begin
if g[i-324]=0 then
begin
r[l[i]]:=r[i];
l[r[i]]:=l[i];
u[d[i]]:=u[i];
d[u[i]]:=d[i];
end else inc(size[(i-1)mod 324+1]);
c[i]:=(i-1)mod 324+1;
end;
end;
procere init;
var sum,i,j:longint;
begin
assign(input,'輸入文件名');reset(input);
sum:=0;
for i:=1 to 9 do
for j:=1 to 9 do
begin
inc(sum,324);
read(f[i,j]);
if f[i,j]<>0 then
begin
cover(c[sum+(s[(i-1)*9+j]-1)*9+f[i,j]]);//宮覆蓋
cover(c[sum+81+(i-1)*9+f[i,j]]);//行
cover(c[sum+162+(j-1)*9+f[i,j]]);//列
cover(c[sum+243+(i-1)*9+j]);//格子
end;
end;
close(input);
end;
procere print;
var i,j:integer;
begin
for i:=1 to 9 do
begin
for j:=1 to 9 do
write(f[i,j],' ');
writeln;
end;
//close（output);halt;
writeln;writeln;writeln;
end;
procere main;
procere Algorithm_X;
var min1,min2:integer;
p,p1,id,p2,p3:longint;
begin
min2:=maxint;min1:=maxint;id:=0;p:=r[0];
if p=0 then print;
while p<>0 do
begin
if min1>size[p] then
min1:=size[p];
if (min2>size[p])and(p<243) then begin
min2:=size[p];id:=p;
end;
p:=r[p];
end;
if min1=0 then exit;// can't cover,
p:=id;
cover(p);//cover
p1:=d[p];
while p1<>p do
begin
p2:=l[p1];
while p2<>p1 do
begin
cover(c[p2]);
p2:=l[p2];
end;
p3:=(p2-324) div 324+1;
if p2 mod 324=0 then dec(p3);
f[l1[p3],l2[p3]]:=l3[p3];//fill in
Algorithm_X;
p2:=r[p1];
while p2<>p1 do
begin
recover(c[p2]);
p2:=r[p2];
end;
p1:=d[p1];
end;
recover(p);
end;
begin
assign(output,'輸出文件名');rewrite(output);
Algorithm_X;
close(output);
end;
begin
prework;
init;
main;
end.
這個不是過程哦，是一個完整的程序呃.......處理過程是讀入一個數獨，輸出所有的解，如果您只需要一個解，請把print過程裡面的 //close(output);halt; 的//刪掉就可以得到一個解了
㈥ 數獨 演算法 C語言 代碼
一、步驟：
1.對每一個空格，根據規則推斷它可能填入的數字，並存儲它的所有可能值；
2.根據可能值的個數，確定填寫的順序。比如說，有些空格只有一種可能，那必然是正確的結果，首先填入。
3.將所有隻有一種可能的空格填寫完畢以後，回到步驟1，重新確定剩下空格的可能值；
4.當沒有隻有一種可能的空格時（即每個空格都有兩種以上可能），按照可能值個數從小到大的順序，使用深度（廣度）優先搜索，完成剩下空格。
二、常式：
#include<windows.h>
#include<stdio.h>
#include<time.h>
charsd[81];
boolisok=false;
//顯示數獨
voidshow()
{
if(isok)puts("求解完成");
elseputs("初始化完成");
for(inti=0;i<81;i++)
{
putchar(sd[i]+'0');
if((i+1)%9==0)putchar(' ');
}
putchar(' ');
}
//讀取數獨
boolInit()
{
FILE*fp=fopen("in.txt","rb");
if(fp==NULL)returnfalse;
fread(sd,81,1,fp);
fclose(fp);
for(inti=0;i<81;i++)
{
if(sd[i]>='1'&&sd[i]<='9')sd[i]-='0';
elsesd[i]=0;
}
show();
returntrue;
}
//遞歸解決數獨
voidforce(intk)
{
if(isok)return;
if(!sd[k])
{
for(intm=1;m<=9;m++)
{
boolmm=true;
for(intn=0;n<9;n++)
{
if((m==sd[k/27*27+(k%9/3)*3+n+n/3*6])||(m==sd[9*n+k%9])||(m==sd[k/9*9+n]))
{
mm=false;
break;
}
}
if(mm)
{
sd[k]=m;
if(k==80)
{
isok=true;
show();
return;
}
force(k+1);
}
}
sd[k]=0;
}
else
{
if(k==80)
{
isok=true;
show();
return;
}
force(k+1);
}
}
intmain()
{
system("CLS");
if(Init())
{
doublestart=clock();
force(0);
printf("耗時%.0fms",clock()-start);
}
elseputs("初始化錯誤");
getchar();
}