Knight traversal of the board
The problem, apparently, is an Olympiad, on recursion. Actually, you need to go through the entire board with a knight so that on each of its cells the knight was only 1 time. The minimum size of the board for which a solution exists is 5. I wrote a program, it works for numbers from 5 to 8. But for numbers greater than 8, it dies. Can someone help us refine it for any natural numbers? Here is the code of the function that performs a run on the board.
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;
}
In main() it is set n, board[1][1] = 1, and is called function set(2,1,1).
4 answers
Well, since the function is recursive, it wouldn't hurt to calculate the maximum recursion depth for all n.... And make sure you have enough space on the stack for that... It is quite possible that at n=9, your stack overflows... Try adjusting the size manually...
Added: And what makes you think that it "doesn't work"? Add the output of i to set, for example, and you will see that everything works. It's just that he makes a mistake at one of the initial steps and the number of rollbacks increases exponentially progressions. The result is an almost infinite execution time. The point, let's say, is in the algorithm...
I added the output of the entire board to set and I see that in one of the corners there is a field with "0", and around it - completely filled, i.e. you just have to wait until the rollback to this cell takes place...
Yes, about the depth of recursion - I blurted it out. Maximum depth - n^2
Added: I slightly changed your program, added a limit on the number of iterations and output statistics "how many times was an attempt made to put the number n"... I advise you to look at the result.
#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;
}
And why invent a bicycle, the problem was solved a long time ago: bypass the board with a knight.
Practice: traversing the board with a chess knight.
This NP is a complete task (i.e. iterating through all the values). Therefore, it is not surprising that it works for a long time.
The implementation is based on the queue expired or, more precisely, the search in depth or width