Chess problem...TLE on test #10!! how to make it faster????? 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!! see+++++++++++++ Posted by famas 12 May 2005 22:32 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; Re: see+++++++++++++ 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! Re: see+++++++++++++ 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. I did not known C++ Posted by famas 13 May 2005 17:14 Re: Chess problem...TLE on test #10!! how to make it faster????? 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 Re: TLE on test #10!! How can here be >=10 tests if 1<=n<=8? Re: Chess problem...TLE on test #10!! how to make it faster????? Great tip, thank you! |