在smlnj中打開騎士的遊覽（回溯）算法

我必須編寫SML代碼來解決騎士在回溯中的遊覽問題。國際象棋騎士必須跑遍棋盤（尺寸：NxN），並且必須每次訪問正方形一次（最後不必回到第一個方格）。在smlnj中打開騎士的遊覽（回溯）算法

我已經編寫了所有的函數來創建一個空白板，設置或獲取棋盤上的方塊，以獲得可能的騎士下一步棋的列表。但我不知道如何在SML中編寫遞歸函數（我知道如何在C中編寫此算法，但不是在SML中編寫此算法）。

算法下一個8×8棋盤

dl and dr are array : (delta to calculate next moves) 
dl = [-2,-2, -1, 1, 2, 2, 1, -1] 
dr = [-1, 1, 2, 2, 1, -1,-2, -2] 


    bool backtracking(int** board, int k/*current step*/, int line, int row, int* dl, int* dr) 
    { 
    bool success = false; 
    int way = 0; 
    do{ 
     way++; 
     int new_line = line + dl[way]; 
     int new_row = row + dr[way]; 

    if(legal_move(board, new_line, new_row)) 
    { 
     setBoard(board,new_line, new_row,k); //write the current step number k in board 
      if(k<64) 
      { 
        success = backtracking(board, k+1, new_line, new_row, dl, dc); 
        if(!success) 
        { 
          setBoard(board,new_line, new_row,0); 
        } 
      } 
      else 
        success = true; 
    } 
    } 
    while(!(success || way = 8)); 
    return success; 
    }

來源

2011-04-12 Arie

如果您知道如何使用C編寫它，請編寫/粘貼C，然後我們將幫助您將它轉換爲SML。 – 2011-04-12 09:48:48

由於網站的限制，我編輯了我的問題......（我無法在24小時內回答我的問題，評論太大了） – Arie 2011-04-12 11:00:15

好吧，這是正確的地方 - 你不應該發佈作爲答案的問題更新，評論不能包含大的代碼塊。 – 2011-04-12 11:10:46

不要以爲像C！這是一種討厭的思維方式！用C/imperative來計算你的算法是沒有用的。你需要做作業並學會正確思考。

您將如何設計該程序？它必須存儲狀態，並且每個狀態必須記錄騎士已經去過的地方。將你的狀態設計成棋盤的元組（遍歷的bool記錄方塊列表）和棋子（列表（int，int））。因此，函數調用如下所示：

exception Back 
fun iter (state, []) = 
     if boardFull state then state else raise Back 
    | iter (state, next::ns) = 
     iter (next, states next) handle Back => iter (state, ns) 

fun states (board, ps) = 
    <a move is a pair (int, int); write out the list of eight moves; map a next fn down the list, and filter it by legal moves> (2 or 3 lines of code for you to write) 
fun boardFull (board, pos::ps) = <foldl twice to apply the 'and' fn over the whole board> (1 line of code for you to write)

來源

2011-05-08 21:13:19

在smlnj中打開騎士的遊覽（回溯）算法

回答

相關問題