sml - open knight's tour (backtracking) algorithm in smlnj -

-

i have write sml code solve knight's tour problem in backtracking. chess knight must run on chessboard (size: nxn) , must visit each square once (no need come in first square @ end).

i write functions create empty board, set or squares in board, list of possible knight next moves. have no idea on how write recursive function in sml (i know how write algorithm in c not in sml).

algorithm in c 8x8 chessboard

dl , dr array : (delta 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 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;     }

don't think c! that's nasty way of thinking! working out algorithm in c/imperative never helpful. need homework , learn think properly.

how design program? has store state, , each state has record knight has gone. design state tuple of board (a list of list of bool recording squares traversed) , moves (a list of (int, int)). so, function calls this:

exception fun iter (state, []) =        if boardfull state state else raise   | iter (state, next::ns) =       iter (next, states next) handle => iter (state, ns)  fun states (board, ps) =     <a move pair (int, int); write out list of 8 moves; map next fn down list, , filter legal moves> (2 or 3 lines of code write) fun boardfull (board, pos::ps) = <foldl twice apply 'and' fn on whole board> (1 line of code write)

Comments

Post a Comment

Popular posts from this blog

php - What is the difference between $_SERVER['PATH_INFO'] and $_SERVER['ORIG_PATH_INFO']? -

-
what’s difference between $_server['path_info'] , $_server['orig_path_info'] ? how use them? when run print_r($_server) , path_info , orig_path_info not present in array. why not? how can enable them? i have read php manual on them, still don’t understand them. the path_info variable present if invoke php script this: http://www.example.com/phpinfo.php/hello_there it's /hello_there part after .php script. if don't invoke url that, there won't $_server["path_info"] environment variable. the porig_ prefix uncommon. path_info standard cgi-environment variable, , should never prefixed. did read that? (there issues around php3/php4 if invoked php interpreter via cgi-bin/ - hardly has such setups today.) for reference: http://www.ietf.org/rfc/rfc3875
Read more

fortran - Function return type mismatch -

-
i'm attempting recode old c++ program in fortran make use of lapack (i'm aware c++ have lapack++, i'm having lot of trouble installing it, gave up). i didn't have problems compilation, when had variables declared real . when started coding section of program required lapack, found parameters passed dsyev need double precision . tried change double precision (including changing hard coded numbers double precision counterparts, i.e. 0.0 -> 0.0d0) when try compile, following error of functions , subroutines i've written: error: return type mismatch of function <function> @ (1) (real(4)/real(8)) i'm not sure coming from, in program has been changed double precision. for example, i've declared following: double precision :: alpha(3),d(3),zeta1,zeta2 double precision :: a1(3),a2(3),d1(3),d2(3) double precision :: pi pi = 3.14159265359d0 alpha = (/0.109818d0, 0.405771d0, 2.22766d0/) d = (/0.444635d0, 0.535328d0, 0.154329d0 /) 10 i=1,3 ...
Read more

queue - mq_receive: message too long -

-
i implementing communication between 2 processes using queue. problem when call function mq_receive, error: message long. i have done following: struct mq_attr attr; long size = attr.mq_msgsize; .... // initializing queue "/gateway" int rc = mq_receive(gateway, buffer, size, &prio); if print size value, size=1, while when print same size program (got same mechanism), not long integer ( -1217186280 )... how can solve error?....so while size = 1, believe it's right "message long" why 1? p.s. have tried put : int rc = mq_receive(gateway, buffer, sizeof(buffer), &prio); but no result. it seems need read docs more carefully. when call mq_receive should pass size of destination buffer. this size must greater mq_msgsize attribute of queue . in addition, seems have error in queue attributes initialisation makes proper mq_receive call impossible. here standard message queue session: fill mq_attr struct ( doc ): struct mq_a...
Read more