My AC recursion for n=8 gives about 8250733 calls. What is the minimum recursive calls value?

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

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!!

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)

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?

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

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

моя прога
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

HELP

in the problem statement 1<=n<=8. therefore the maximum of the data tests is 8. why there are test 10, test 9.

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.