smlnj의 열린 기사단 (백 트랙킹) 알고리즘

Question

나는 역 추적에서 나이트의 여행 문제를 해결하기 위해 SML 코드를 작성해야합니다. 체스 판은 체스 판 (크기 : NxN) 전체를 달려야하며 각 사각형을 정확히 한 번 방문해야합니다 (끝에 첫 번째 사각형으로 돌아올 필요 없음).

나는 빈 보드를 만들고, 보드에 사각형을 얻고, 다음 기사의 가능한 기사 목록을 얻는 모든 기능을 이미 작성했습니다. 하지만 SML에서 재귀 함수를 작성하는 방법에 대해서는 잘 모르겠다. (나는이 알고리즘을 C로 작성하는 법을 알고 있지만 SML에서는 작성하지 않았다.)

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; 
    } 

Answer 1

는 C처럼 생각하지 마십시오의 8 × 8 체스 판에 대한 C에서

알고리즘! 그것은 생각의 고약한 방법입니다! C/명령형으로 알고리즘을 작성하는 것은 결코 도움이되지 않습니다. 숙제를하고 제대로 생각하는 법을 배워야합니다.

어떻게 프로그램을 디자인 하시겠습니까? 그것은 국가를 저장해야하며, 각 국가는 기사가 어디로 갔는지 기록해야합니다. 보드의 튜플 (가로 지르는 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)