算法分析與設(shè)計(jì)大作業(yè)

問題描述

在本次算法分析的課堂演示中，我做的是一個(gè)關(guān)于“裁切悖

論——消失的正方形的PPT”，但是由于代碼的問題，現(xiàn)在借鑒

了同學(xué)的實(shí)驗(yàn)，寫了一個(gè)關(guān)于數(shù)獨(dú)算法的小題目。

如下圖所示，有一個(gè)9*9的正方形，而正方形又分成了九個(gè)

小正方形，現(xiàn)在已經(jīng)在圖示的正方形中給出了一些方格中的數(shù)字,

要求將正方形中所有小方格的數(shù)字填充完，并且每個(gè)小正方形以

及每行、每列，只能出現(xiàn)一次卜9這九個(gè)數(shù)字。

687

9576

48

32

469

4123

5317

892

1763

解決方案

我們先假設(shè)填入的數(shù)字為0~8共9個(gè)數(shù)字。

將整個(gè)圖分成9個(gè)3*3的方塊，從左到右，從上到下，依次編號(hào)

0-8。

填每個(gè)格子的時(shí)候,我們可以選擇.0~8。

對(duì)于選擇的數(shù)字，有3種限制，我們通過這三種限制來對(duì)回溯過

程進(jìn)行剪枝。

L行不重復(fù)r[9][9]

2?列不重復(fù)c[9][9]

3?塊不重復(fù)b[9][9]

對(duì)使用3個(gè)9x9的數(shù)組來描述這三種限制。

對(duì)于行n來說，所有之前填過的數(shù)字nums,都有r[n][nums]二

lo

同理，對(duì)與列和塊來說，之前每個(gè)填過的數(shù)字都相應(yīng)標(biāo)記為1。

當(dāng)嘗試向一個(gè)格子[row]9。1]（塊序號(hào)為bi）填充數(shù)據(jù)i（0〈=iv=8,

的時(shí)候，如果對(duì)應(yīng)中。w][i]=l或c[col][i]=1或b[bi][i]=l,

說明無法滿足條件，是非法的。）

這時(shí)再嘗試i=i+L

當(dāng)向坐標(biāo)為[row][col]填入一個(gè)滿足條件的數(shù)字i的時(shí)候，我們

更新限制數(shù)組如下

r[row][i]=1;

c[col][i]=1;

b[bi][i]=1;

然后坐標(biāo)移到下一個(gè)，這里選用的順序是右移動(dòng)。

對(duì)于一個(gè)格子CX的后續(xù)CY,如果我們遍歷。?9完成，那么

返回。

嘗試CX的其他可能性。

當(dāng)填入的格子是[8][8]時(shí)，整個(gè)問題處理完畢。

對(duì)于給定的輸入，直接將初始狀態(tài)的矩陣設(shè)置成相應(yīng)的值，同時(shí),

根據(jù)給定的值，設(shè)置初始的r,c,b的限制條件。

當(dāng)讀到的格子內(nèi)已經(jīng)有給定值的時(shí)候，無需做其他嘗試，直接進(jìn)

入處理下一個(gè)格子。

實(shí)際填入的是1?9,所以要對(duì)。?8做一點(diǎn)轉(zhuǎn)換。

對(duì)于每次嘗試完一個(gè)可能填入的數(shù)后，需要恢復(fù)現(xiàn)場(chǎng)，包括將該

格子內(nèi)的數(shù)重置為初始值0.同時(shí)，相應(yīng)的限制條件r,c,b都應(yīng)把

剛才填入的值的位置0.

代碼實(shí)現(xiàn)

下面給出這道題目的實(shí)現(xiàn)代碼：

1.打開codeblocks,新建一個(gè)項(xiàng)目；

2.編寫代碼。

代碼如下：

include<stdlib.h>

include<stdio.h>

#defineMMAX9

charM[MMAX][MMAX]={{0}};

intcount=0;

intgetblockid(introw,intcol)

{

returnrow/3*3+col/3;

)

voidgetnext(int*row,int*col,int*nrow,int*ncol){

if(*col==8)

(

*ncol=0;

*nrow=(*row)+1;

)

日se

*nrow=*row;

*ncol=(*col)+1;

)

)

voidoutputmatrix(charmtr[MMAX][MMAX]){

inti,j;

for(i=0;i<MMAX;i++)

(

for(j=0;j<MMAX;j++)

(

printf("%d",mtr[i]OJ);

)

printf("\n");

)

)

voidfill(introw,intcol,charmatrix[MMAX][MMAX],char

rowdOtMMAX],charcold[][MMAX],charblod[][MMAX]){

count++;

if(matrix[row][col]!=0)

if(row==8&&col==8){

outputmatrix(matrix);

return;

)

intnr,nc;

getnext(&row,&col,&nr,&nc);

fill(nr,nc,matrix,rowd,cold,blod);

return;

)

inti=1;

charmtr[MMAX][MMAX];

memcpy(mtr,matrix,MMAX*MMAX*sizeof(char));

for(;i<=9;i++)

(

//duplicatealldata

intblockid=getblockid(row,col);

if(

blod[blockid][i-1]!=(char)1&&

rowd[row][i-1]!=(char)1&&

cold[col][i-1]!=(char)1

)

//fillthecell

//printf("fill[%d][%d]with%d\n",row,col,i);

matrix[row][col]=i;

if(row==8&&col==8){

outputmatrix(matrix);

return;

)

//settherestriction

blod[blockid][i-1]=1;

rowd[row][i-1]=1;

cold[col][i-1]=1;

intnrow.ncol;

getnext(&row,&col,&nrow,&ncol);

fill(nrow,ncol,matrix,rowd,cold,blod);

//restorestatus

blod[blockid][i-1]=0;

rowd[row][i-1]=0;

cold[col][i-1]=0;

matrix[row][col]=0;

)

)

)

voidtrackfixedcell(charfixmtr[MMAX][MMAX],char

r[MMAX][MMAX],charc[MMAX][MMAX],char

b[MMAX][MMAX]){

introw,col;

for(row=0;row<MMAX;row++)

{

for(col=0;col<MMAX;col++)

(

if(fixmtr[row][col]!=0)

(

r[row][(int)fixmtr[row][coI]-1]=1;

c[col][(int)fixmtr[row][col]-1]=1;

b[getblockid(row,col)][(int)fixmtr[row][col]-1]

=1；

)

)

)

)

voidreadfixed(charmtr[MMAX][MMAX],char*input){

inti=0;

for(;i<MMAX*MMAX;i++)

introw=i/MMAX;

intcol=i%MMAX;

if(input[i]!='0')

(

mtr[row][col]=input[i]-48;

)

)

)

/*

*===FUNCTION

*Name:main

*Description:

7

int

main(intargc,char*argv[])

(

char*fixed=

"6000870000009057060400000800300020000040006900004

10023500030170080090200001076300";

charr[MMAX][MMAX]={{0}};

charc[MMAX][MMAX]={{0}};

charb[MMAX][MMAX]={{0}};

readfixed(M,fixed);

trackfixedcell(M,r,c,b);

fill(0,0,M,r,c,b);

printf("count=%d\n",count);

returnEXIT_SUCCESS;

}/*----------endoffunctionmain----------*/

實(shí)現(xiàn)圖

S3l^SC:\U$ersVJ'師叔\Desktop\喳\main.exe—□X

659187432

328945716|

147623985

935762841

214358697

876419523

562834179

783591264

491276358

count=24943

Processreturned0(0x0)executiontime:0.065s

Pressanykeytocontinue.

腰狗拼音輸入法全：

出好

心￡口

在計(jì)算機(jī)軟件專業(yè)中，算法分析與設(shè)計(jì)是一門非常重要的課

程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依

賴它，在軟件還是面向過程的階段，就有程序=算法+