My AC recursion for n=8 gives about 8250733 calls. What is the minimum recursive calls value? My recursion gives only 64 for n=8. I sort moves by count of free cells that can be reached from them. I solved this problem using backtracking with optimization( you start from some position and then you go to the position that has the fewest future possible moves...//from other post). But it's WA 3. Then I checked the answers of my program myself and all was correct.Then I wrote a simple checker for this problem. And it said all right. Then I tried to save the answers(firstly my answers then answers from forum) as the constants in the program. And the answer was WA 3 again. Help me, please!!! P.S. Sorry for my English. Edited by author 12.09.2005 23:16 Edited by author 12.09.2005 23:21 But your solution is wrong! Thank you for answer. I found the mistake in my code and now I got AC! At me the same problem!!! I do not know in what a mistake. Help, please. I really stuck with this, I don't know how to make my algorithm faster here is my code: #include <stdio.h> char board[10][10]; char letter[66],num[66]; int n,s=0,ncuad; int pos_f[8]={-1,-2,-2,-1, 1, 2, 2, 1}; int pos_c[8]={-2, 1,-1, 2, 2, 1,-1,-2}; init_board(){ int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) board[i][j]='0'; } search(int i,int f,int c){ int j=0; if(s==1) return 0; if(board[f][c]=='0'){ board[f][c]='1'; switch(f){ case 1: letter[i]='a';break; case 2: letter[i]='b';break; case 3: letter[i]='c';break; case 4: letter[i]='d';break; case 5: letter[i]='e';break; case 6: letter[i]='f';break; case 7: letter[i]='g';break; case 8: letter[i]='h';break; } num[i]=c; if(i==ncuad) s=1; while(j<8 && s==0){ if((f+pos_f[j])>0 && (f+pos_f[j])<=n) if((c+pos_c[j])>0 && (c+pos_c[j])<=n) search(i+1,f+pos_f[j],c+pos_c[j]); j++; } board[f][c]='0'; } } int main(){ int i,j; scanf("%d",&n); ncuad=n*n; init_board(); for(i=1;i<=n;i++) for(j=1;j<=n;j++) search(1,i,j); if(s){ for(i=1;i<=ncuad;i++) printf("%c%d ",letter[i],num[i]); return 0; } else printf("IMPOSSIBLE\n"); return 0; } if someone can help me I would appreciate a lot!! else begin writeln('a1'); writeln('b3'); writeln('a5'); writeln('b7'); writeln('d8'); writeln('c6'); writeln('b4'); writeln('a2'); writeln('c3'); writeln('b1'); writeln('a3'); writeln('b5'); writeln('a7'); writeln('c8'); writeln('b6'); writeln('a4'); writeln('c5'); writeln('a6'); writeln('b8'); writeln('d7'); writeln('f8'); writeln('e6'); writeln('d4'); writeln('c2'); writeln('e3'); writeln('d1'); writeln('b2'); writeln('c4'); writeln('d6'); writeln('e8'); writeln('g7'); writeln('f5'); writeln('e7'); writeln('g8'); writeln('f6'); writeln('h7'); writeln('g5'); writeln('e4'); writeln('d2'); writeln('f1'); writeln('h2'); writeln('f3'); writeln('e1'); writeln('g2'); writeln('h4'); writeln('g6'); writeln('h8'); writeln('f7'); writeln('h6'); writeln('g4'); writeln('e5'); writeln('d3'); writeln('c1'); writeln('e2'); writeln('g1'); writeln('h3'); writeln('f2'); writeln('h1'); writeln('g3'); writeln('h5'); writeln('f4'); writeln('d5'); writeln('c7'); writeln('a8'); end; thanks! but can I ask you two questions...? first, how many time takes in your computer if you run my code to get the solution for n=8? because my computer is veryy slow and get stuck and number two is it any way to solve it the problem without precalc?? (sorry for my bad english) and thanks again!!! :D:D:D:D:) byee! and good luck! I didn't use precalc. I calculated answer for N using answer for N-1 if it was not 'No Solution' I took first N moves from it. Use the priority array for the chessboard : void init() { int a,b,c; int chessboard[8][8]={0}; int direction[8][2]= { {2,1},{-2,1},{2,-1},{-2,-1}, {1,2},{-1,2},{1,-2},{-1,-2}, }; for(a=0;a<n;a++) { for(b=0;b<n;b++) { int count=0; for(c=0;c<n;c++) { int x1 = a+direction[c][0]; int y1 = b+direction[c][1]; if(x1>=0&&x1<n&&y1>=0&&y1<n) count++; } chessboard[a][b] = count; } } } For example, n = 8 : 2 3 4 4 4 4 3 2 3 4 6 6 6 6 4 3 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 3 4 6 6 6 6 4 3 2 3 4 4 4 4 3 2 go to the cell with minimum priority first ! Good luck ! Edited by author 17.02.2009 12:04 Edited by author 17.02.2009 12:04 How can here be >=10 tests if 1<=n<=8? You can have an array deg[i][j] = count of adjacent unvisited cells for cell (i;j). While doing DFS sort edges by non-decreasing deg[i+move. first] [j+move. second]. It calls an heuristic after some scientist whose name begins at W. Backtracking works on this problem) I wrote code, using it, and i thought it'll got TL. But when I tried, it get AC) (Sorry for my poor english) The running time of a simple backtracking search will depend on the move search order you use. For example, this order: moves = [ a, e, f, b, c, g, h, d ] where a = (1,-2) b = (1,2) c = (-1,2) d = (-1,-2) e = (2,1) f = (2,-1) g = (-2,1) h = (-2,-1) works great for n = 7, but not 6 or 8. If you use a simple depth first search, your run time will depend on the order in which you examine the possible moves. For example, always examining the moves in this order yields a TLE: (1,2), (1,-2), (-1,2), (-1,-2), (2,1), (2,-1), (-2,1), (-2,-1). To get the fastest solutions you'll want to adapt the search order at each node in the search tree, but you can get an AC with a static search order. Recursive algorithm seems to slow for n=8. Actually, it depends on the order of moves, but the order fast for n=8 was slow for 6 or 7, the fast one for 7 was slow for 8 and so on... Anyway, I used pregenerated output to solve this. Is there a way to optimize the algorithm? there is a greedy solution but non-demonstrable: you start from some position and then you go to the position that has the fewest future possible moves... here are the solutions that I've computed with this: for n = 5, 6, 7 and 8; N = 5: "a1","b3","a5","c4","e5","d3","e1","c2","a3","b1","d2","e4","c5","a4","b2","d1","e3","d5","b4","a2","c1","e2","c3","b5","d4" N = 6: "a1","b3","a5","c6","e5","f3","e1","c2","a3","b1","d2","f1","e3","f5","d4","b5","d6","c4","b6","a4","b2","d1","f2","e4","f6","d5","c3","a2","b4","a6","c5","e6","f4","d3","c1","e2" N = 7: "a1","b3","a5","b7","d6","f7","g5","e6","g7","f5","e7","g6","f4","g2","e1","c2","a3","b1","d2","f1","g3","e2","g1","f3","d4","b5","a7","c6","b4","a2","c1","d3","b2","a4","b6","c4","e5","d7","c5","a6","c7","d5","c3","d1","e3","g4","f2","e4","f6" N = 8: "a1","b3","a5","b7","d8","f7","h8","g6","f8","h7","g5","h3","g1","e2","c1","a2","b4","a6","b8","c6","a7","c8","e7","g8","h6","g4","h2","f1","d2","b1","a3","c2","e1","f3","h4","g2","e3","d1","b2","a4","c3","b5","d4","f5","d6","c4","e5","d3","f2","h1","g3","e4","c5","d7","b6","a8","c7","d5","f4","e6","g7","e8","f6","h5" i used back and got AC in 0.46 .... I got AC in 0.031s . But I not just submit the answer. I just use DFS. Edited by author 26.06.2004 10:16 I do it in 0.015 sec I don`t use CONSTANT solv I am also use DFS and AC in 0.718s. Why my program slowly from you? What is your fu*king dfs solutions? how did u manage that it is impossible! My answer accepted in 0.734 sec I also used DFS Edited by author 01.04.2014 18:17 I wonder: my recursive solution for n=8 works faster than for n=7. you may be not use recursion. you may draw on sheet this and type answer to program... http://delphiforfun.org/Programs/knights_tour.htm A technique known as Warnsdorf's heuristic allows us to make much better choices for next move than random selection. The heuristic, discovered by H. C. von Warnsdorf in 1823 tells us to select as our next move the one which has the fewest choices for moving on from there. This heuristic works so well that , although I have implemented backtracking to remove bad choices, I have yet to see a move retracted while making a tour Warnsdorf's idea works in linear time! Amazing power of human mind.. :) I had use Warnsdorff heuristic, but I take wrang answer.. Maybe you can find my bug? #include <iostream> using namespace std; struct minimum { int minp; int i; int j; minimum():minp(9999),i(0),j(0){} }; int d[9][9]; bool isnuje_hid(int i, int j,int n) { if(i <= n && i >= 1 && j <= n && j >= 1) return true; else return false; } int reytung(int i,int j,int n) { int k = 0; if(!d[i][j]) { if(isnuje_hid(i+2,j+1,n))k++; if(isnuje_hid(i+1,j+2,n))k++; if(isnuje_hid(i+2,j-1,n))k++; if(isnuje_hid(i+1,j-2,n))k++; if(isnuje_hid(i-2,j+1,n))k++; if(isnuje_hid(i-2,j-1,n))k++; if(isnuje_hid(i-1,j+2,n))k++; if(isnuje_hid(i-1,j-2,n))k++; } else return -1; return k; } void zrobyty_hid(int & i, int & j,int n) { minimum a; if(isnuje_hid(i+2,j+1,n)) if(reytung(i+2,j+1,n) < a.minp && reytung(i+2,j+1,n) > 0) { a.minp = reytung(i+2,j+1,n); a.i = i + 2; a.j = j + 1; } if(isnuje_hid(i+1,j+2,n)) if(reytung(i+1,j+2,n) < a.minp && reytung(i+1,j+2,n) > 0) { a.minp = reytung(i+1,j+2,n); a.i = i + 1; a.j = j + 2; } if(isnuje_hid(i+2,j-1,n)) if(reytung(i+2,j-1,n) < a.minp && reytung(i+2,j-1,n) > 0) { a.minp = reytung(i+2,j-1,n); a.i = i + 2; a.j = j - 1; } if(isnuje_hid(i+1,j-2,n)) if(reytung(i+1,j-2,n) < a.minp && reytung(i+1,j-2,n) > 0 ) { a.minp = reytung(i+1,j-2,n); a.i = i + 1; a.j = j - 2; } if(isnuje_hid(i-2,j+1,n)) if(reytung(i-2,j+1,n) < a.minp && reytung(i-2,j+1,n) > 0) { a.minp = reytung(i-2,j+1,n); a.i = i - 2; a.j = j + 1; } if(isnuje_hid(i-2,j-1,n)) if(reytung(i-2,j-1,n) < a.minp && reytung(i-2,j-1,n) > 0) { a.minp = reytung(i-2,j-1,n); a.i = i - 2; a.j = j - 1; } if(isnuje_hid(i-1,j+2,n)) if(reytung(i-1,j+2,n) < a.minp && reytung(i-1,j+2,n) > 0) { a.minp = reytung(i-1,j+2,n); a.i = i - 1; a.j = j + 2; } if(isnuje_hid(i-1,j-2,n)) if(reytung(i-1,j-2,n) < a.minp && reytung(i-1,j-2,n) > 0) { a.minp = reytung(i-1,j-2,n); a.i = i - 1; a.j = j - 2; } if(i && j) { i = a.i; j = a.j; } d[i][j] = 1; } char convert(int n) { switch(n) { case 1: return 'a'; case 2: return 'b'; case 3: return 'c'; case 4: return 'd'; case 5: return 'e'; case 6: return 'f'; case 7: return 'g'; case 8: return 'h'; } } int main() { int n; cin >> n; if(n < 5 && n > 1){cout << "IMPOSSIBLE"; return 0;} int m = 1,k = 1; d[1][1] = 1;d[0][1] = 1;d[1][0] = 1;d[0][0] = 1; for(int i = 1; i <= n*n; i++) { cout << convert(m) << k << endl; zrobyty_hid(m,k,n); } return 0; } Edited by author 27.02.2007 00:32 Edited by author 27.02.2007 02:42 My algorithm based on Warnsdorff rule got AC. Check your realisation. моя прога Uses SysUtils,Math; {$APPTYPE CONSOLE} var i,f,j,n,c,x,y,x1,y1:integer; a:array [-1..10,-1..10] of byte; b:array[1..8] of char=('a','b','c','d','e','f','g','h'); procedure proc(k,l:integer); var min,i1,j1:integer; begin for i1:=-2 to 2 do for j1:=-2 to 2 do if (abs(i1)+abs(j1)=3) and (a[k+j1,l+i1]=0) then inc(min); if min<c then begin c:=min; x1:=k; y1:=l end;
end; begin {$ifndef online_judge} reset(input,'input.txt'); rewrite(output,'output.txt'); {$endif} fillchar(a,sizeof(a),1); readln(n); for i:=1 to n do for j:=1 to n do a[i,j]:=0; case n of 1:writeln('a1'); 2:writeln('IMPOSSIBLE'); 3:writeln('IMPOSSIBLE'); 4:writeln('IMPOSSIBLE') else begin x:=1; y:=1; f:=0; repeat c:=10; a[x,y]:=1; writeln(b[x],y); for i:=-2 to 2 do for j:=-2 to 2 do if (abs(i)+abs(j)=3) and (a[x+j,y+i]=0) then proc(x+j,y+i); inc(f); x:=x1; y:=y1; until f>=sqr(n); end; end; end. Фишка в том, что прога оптимально(!) обходит псведошахматную доску с заданными размерами ребер n<=8 и находит решение по обходу доски конем, чтобы он только один раз наступал на одно поле(я проверял), но правда, поскольку решение отличается от того что в тестах, приишлось сдать массивом конастант... обидно. Если есть возражения, пишите! I think,when n=1 answer is "IMPOSSIBLE",but really right answer is "a1". [code deleted] Edited by moderator 27.03.2007 09:45 if replace char[8][8] by char [64][64] my program works for n=63 :) 2admis: I realy don't know why i got wa#3 my program work on all my test, please test my program your self. and look at my motto :) Edited by author 26.03.2007 22:10 :) stupid test Thank you Edited by author 26.03.2007 23:00 HELP Maybe in some tests n < 1 or n > 8? how about posting your source code? It may be useful I submit a const table .Why CE? in the problem statement 1<=n<=8. therefore the maximum of the data tests is 8. why there are test 10, test 9. The first two tests are samples. Then follow n = 1, 2, ... 8. Program Acm_Timus_Ru_1298; const dy:array [1..8] of integer=(-2,-2,-1,1,2,2,1,-1); dx:array [1..8] of integer=(-1,1,2,2,1,-1,-2,-2); g:array [1..8] of char=('a','b','c','d','e','f','g','h'); var a:array [-5..15,-5..15] of longint; k,i,j,ip,min,h,x,y,rem:longint; n : longint; p : boolean; Function mo(x,y:integer):boolean; Begin if (x>n) or (x<1) or (y>n) or (y<1) then mo:=false else mo:=a[x,y]=0; End; Function hm(x,y:integer):byte; Var i:integer; Begin k:=0; if not(mo(x,y)) then k:=n*n else for i:=1 to 8 do if mo(x+dx[i],y+dy[i]) then k:=k+1; hm:=k; End; BEGIN readln(n); if (n>=1) and (n<=8) then begin fillchar(a,sizeof(a),0); x:=1;y:=1; for i:=1 to n*n do begin min:=n*n; a[x,y]:=i; for j:=1 to 8 do begin h:=hm(x+dx[j],y+dy[j]); if h<min then begin ip:=j; min:=h; end; end; x:=x+dx[ip]; y:=y+dy[ip]; end; p:=true; for i:=1 to n do for j:=1 to n do if a[i,j]=0 then p:=false; if p=false then begin writeln('IMPOSSIBLE');end else for k:=1 to n*n do for i:=1 to n do for j:=1 to n do if a[i,j]=k then writeln(g[i],j); end else writeln('IMPOSSIBLE'); END. I think the problem is here- x:=x+dx[ip]; y:=y+dy[ip]; may be ip is invalid since it might not be updated. When all the neighbor squares return hm()>=min value, ip will not get updated. It's very intresting! I compiled given source code both on Delphi and FreePascal and checked each program on every possible tests (n from 1 to 8) and I didn't get Access Violation. I am really confused if this code get Access Violation on Timus Judge System. It's very interesting, I wrote a new program in which answers for 5,6,7,8 were constants (which I defined by my program which gets Crash on a server), and I got AC. Admins! Can you give some clarification to this situation? Is it a crash of the program or a Judge? Add ip:=7862341 line after BEGIN, and you'll get crash in both Delphi and FreePascal. I know that ip was not initialized. Delphi gave that warning, but why does the same program run different on my home machine and on timus server. I have no crashes on all possible tests. How do you compile sources exactly? If variable is not initialized it may have arbitrary value, that depends on many factors. It must work different on different machines! |
|