Обход доски конем

int n;            // сторона доски
int sqr = n * n;  // количество клеток
int dx[9], dy[9]; // массивы, состоящие из координат, куда может попасть конь при       своем ходе, принимая, что он стоит в клетке с координатами 0,0
dx[1] = 2; dx[2] = 1; dx[3] = -1; dx[4] = -2;
dx[5] = -2; dx[6] = -1; dx[7] = 1; dx[8] = 2; 
dy[1] = 1; dy[2] = 2; dy[3] = 2; dy[4] = 1;
dy[5] = -1; dy[6] = -2; dy[7] = -2; dy[8] = -1;
int set (int i, int x, int y)
{
  int j, u, v, q1 = 0;
  for(j = 1; (!q1) && (j <= 8); j++)
  {
    u = x + dx[j]; 
    v = y + dy[j];
    if ( 1 <= u && u <= n && 1 <= v && v <= n && board[u][v] == 0)
    {
      board[u][v] = i;
      if (i < sqr)
      {
        q1 = set (i + 1, u, v);
        if (q1 == 0) board[u][v] = 0; 
      } 
      else q1 = 1;
    }
  }
  return q1;
 }

Ну, поскольку функция рекурсивная, не мешало бы подсчитать максимальную глубину рекурсии при всех n.... И убедиться, что у Вас хватает места на стеке для этого... Вполне возможно, что при n=9 Ваш стек переполняется... Попробуйте настроить размер вручную...

Добавлено: А с чего Вы взяли что она "не работает"? Добавьте выдачу i в set например, увидите - все работает. Просто он на одном из начальных шагов делает ошибку а количество откатов нарастает в геометрической прогрессии. В итоге - практически бесконечное время выполнения. Дело, скажем так, в алгоритме...

я добавил в set выдачу всей board и вижу, что в одном из углов остается поле с "0", а вокруг - сплошь заполненные, т.е. просто надо ждать пока пройдет откат до этой клетки...

Да, насчет глубины рекурсии - это я ляпнул. Максимальная глубина - n^2

Добавлено: Я немного изменил Вашу программу, добавил ограничение на количество итерации и выдачу статистики "сколько раз была сделана попытка поставить число n"... Советую взглянуть на результат.

#include <stdio.h>
#include <stdlib.h>
int n = 12;       // сторона доски
int sqr = n * n;  // количество клеток
// массивы, состоящие из координат, куда может попасть конь при       
//своем ходе, принимая, что он стоит в клетке с координатами 0,0
int dx[9] = {0,  2,  1, -1, -2, -2, -1, 1 ,2}; 
int dy[9] = {0, -1, -2, -2,  1, -1,  2, 2, 1};
char txt[80];
int board[20][20];    
int it = 1000;
int ntry[1000];
int set (int i, int x, int y)
{  
  if (it > 0)
    --it;
  else
    return 1;
  ntry[i-1] += 1;
  for(int k = 1; k <= n; ++k)
  {
    txt[0] = 0;
    for(int j = 1; j <= n; ++j)
      sprintf(txt, "%s%4d", txt, board[k][j]);
    printf("%s\n", txt);
  }
  printf("%d\n\n", i);
  int j, u, v, q1 = 0;
  for(j = 1; (!q1) && (j <= 8); j++)  
  {    
    u = x + dx[j];     
    v = y + dy[j];    
    if (1 <= u && u <= n &&
        1 <= v && v <= n &&
        board[u][v] == 0)
    {      
      board[u][v] = i;
      if (i < sqr)
      {
        q1 = set (i + 1, u, v);
        if (q1 == 0) board[u][v] = 0;
      }       
      else q1 = 1;
    }  
  }
  return q1; 
 }
int main(void)
{
  board[1][1] = 1;
  for(int k = 0; k < 1000; ++k)
    ntry[k] = 0;
  set(2, 1, 1);
 for(int k = 0; k < n * n; ++k)
   printf("%d - %d\n", k, ntry[k]);
 for(int i = 1; i <= n; ++i)
 {
   txt[0] = 0;
   for(int j = 1; j <= n; ++j)
     sprintf(txt, "%s%4d", txt, board[i][j]);
   printf("%s\n", txt);
 }
 return 0;
}

А зачем велосипед изобретать, задача-то решена давно: обход доски конем.

Практика: обход доски шахматным конем.

Это НП полная задача (т.е. перебор всех значений). Поэтому не удивительно, что она долго работает.

Реализация на основе очереди истека или если более точно то поиск в глубину или ширину