[問題] knight漫遊 用遞迴解

[calqlus (東方一隻鹿)]

        ( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
             ( 未必需要依照此格式，文章條理清楚即可 )

遇到的問題： (題意請描述清楚)
不知道想要問什麼了
堆疊解還OK
遞迴就很難弄-.-
而且偏偏一堆書都扯什麼遞迴不值得用啦 用其他方法解安定
SO只好來這貼CODE了

希望得到的正確結果：
輸出會跑出5*5棋盤
從(1,1)這個起點開始
然後1234567...標到24一次走完 不用回到原點

程式跑出來的錯誤結果：
堆疊的話 是利用回朔法 就可以返回去重走
但遞迴也真的沒啥經驗(只有階乘和河內塔)
大概講一下我那程式怎麼用遞迴

1.我嘗試用遞迴 返回去
2.最後一次的遞迴 = 已經是確定常數的回傳值
3.大概是跑無限遞迴吧 最終是記憶體XXX錯誤  用pause測圖時是還可以畫
4.問題的癥結點 到跑第20個位子後 騎士已經無法可走 要逆回的時候
  其實一開始想是 不要逆回了 找個方法讓這個遞迴暴掉 讓上一個遞迴可以去跑

  但不知道該怎麼做-.- 如果真的有這個方法就先講這部分吧....

5.這是一個問題啦 遞迴是不是 只要執行到回傳固定的值
  之前的一堆遞迴就暴掉了 是嗎?


開發平台： (例: VC++ or gcc/g++ or Dev-C++, Windows or Linux)
devc++
有問題的code： (請善用置底文標色功能)
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
#define SUCCESS 1
#define FAILURE 0
#define EMPTY -1

int board[MAXSIZE+1][MAXSIZE+1];
int n;                          //working board size
int offset_x[] = {2,1,-1,-2,-2,-1,1,2};
int offset_y[] = {1,2,2,1,-1,-2,-2,-1};
int count=0;

void initial(int);
void display();
int move(int,int,int,int);
void show();

int main()
{

   n=5;
   initial(n);
   show();

   system("pause");
}

 void initial(int n)
 {
      int i,j;
      /*棋盤初始化*/
      for(i=1;i<=n;i++)
       for(j=1;j<=n;j++)
          board[i][j]=EMPTY;

      printf("====在%d*%d的西洋棋盤上====\n",n,n);
 }

 void show()
 {
      if(move(1,1,-1,-1) == FAILURE) //起點從(1,1)開始
              printf("NO SOLUTION\n");
      else
         display();
 }

#define YES 1
#define NO 0
#define BOARD(x,y) (1<=x) && (x<=n) && (1<=y) && (y<=n)
#define CHECK(x,y) board[x][y] == EMPTY

int move(int x, int y,int visited,int ignore)
{
    int new_x,new_y,i=0,j,found=NO;
    //已設 board[1][1]=0;

     while(count < n*n-1){
              found = NO;
              while (i < 8){ //八個方向都試

                    if(i==visited && ignore==YES) i++;

                    ignore = NO;
                    new_x = x + offset_x[i];
                    new_y = y + offset_y[i];

                    if(BOARD(new_x,new_y) && CHECK(new_x,new_y)){
                       board[new_x][new_y]=++count;
                       found = YES;
                       ignore = NO;
                       visited = i;
                       move(new_x,new_y,visited,ignore);
                       break;
                    }
                    else
                         i++;
              }

              /*八個方向都不能走*/
              if(!found) //  cout<<(!found) 輸出是0
                if(count > 0){
                        board[x][y] = EMPTY ;
                        new_x = x - offset_x[visited];
                        new_y = y - offset_y[visited];
                        count--;
                        ignore=YES;

                        return move(new_x,new_y,visited,ignore);
                        }
                else
                     return FAILURE;
    }
    return SUCCESS;
}

補充說明：
display()函式沒問題我就不寫了
精華區的看過了 那是用堆疊
先吃個飯

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.171.74.174
推 LPH66:你再仔細想想看你所謂的"遞迴爆掉"是什麼意思
→ LPH66:(我是指 4. 裡說的那個)
→ LPH66:想成讓這一次遞迴「告訴」上一層說我這裡死掉了這種感覺
→ LPH66:這樣你就會寫了
推 F23ko:請問.....什麼叫做堆疊解？
推 F23ko:其實，只要讓遞回的方法返回true或 flase就好了
推 lvlightvivi:應該是用stack來解的意思吧
推 loveme00835:遞迴也是堆疊啊 0.0
ture false不是相當於1 0嗎
不過先試試看好了..

另外堆疊解是指用top什麼的去指一個資料結構

推 F23ko:請問題目長什麼樣子？ 有點想玩玩看.....
→ F23ko:http://www.math.sinica.edu.tw/math_media/d284/28407.pdf
→ F23ko:是這個嗎?
Y 目前這題目是類似的
※ 編輯: calqlus         來自: 118.171.74.174       (08/11 20:04)

意外的成功了= =
我取消ignore的引入值
把八個方向找不到的那個函式  回傳值 改 false
就瞬殺了.....
感謝PTT良解
※ 編輯: calqlus         來自: 118.171.74.174       (08/11 20:09)
剛剛又發現一件不幸的事
他移動的位子 11->12 出錯了..
不過改一下應該就好了
※ 編輯: calqlus         來自: 118.171.74.174       (08/11 20:11)
if(i==vi) i++那段下一行
補if(i>=8) break;
GG
※ 編輯: calqlus         來自: 118.171.74.174       (08/11 20:13)
→ bleed1979:如果您不採用回傳判斷，而是reference或global variable
→ bleed1979:可以不必count--。
→ bleed1979:具體程式碼 http://nopa.csie.org/5e068  跑8就要1x秒。
推 yauhh:遞迴解的好處是比較不用動腦想一組一致的控制規則,而是
→ yauhh:用一點簡單的規則,放出去,讓程式自己試,試錯了就中斷那支.
推 Yshuan:這我寫過XD 還記得課本演算法不是最佳解 只是近似 要偷吃!