N QUEENS problems

Question

I try to solve the problem of N queens solution and manage to create an algorithm that gives me all possibilities and prints it (I try to understand everything but as backtracking is a little new to me, it is hard).

My program looks at every possibility and prints the position of the queens one by colones, it looks like it works well, even if I don't understand my stopping condition.

My problem is that I need to print the position in a certain a order (start from first queen position 0 - N), but it prints in a random way.

I could store it in an array and sort it, but it will take too much time, so i would like to know if people can look at my code and point out possible problems and give some tips or feedback.

#include <unistd.h>
 #include <stdio.h>
#define N 10

  void  print(int tab[N][N])
 {
   int i;
   int a;
   char c;

    i = -1;
    while (++i < N)
    {
    a = -1;
    while (++a < N)
        if (tab[a][i])
        {
            c = '0' + a;
            write(1, &c, 1);
        }
     }
     write(1, "\n", 1);
 }


   int  check(int tab[N][N] , int x, int y)
   {
      int i;
      int j;

      i = 0;
      while (i < x)
       if (tab[i++][y])
          return (0);
      i = x;
      j = y;
      while (j >= 0 && i >= 0)
       if (tab[i--][j--])
          return (0);
      i = x;
      j = y;
      while (i >= 0 && j < N)
        if (tab[i--][j++])
          return (0);
     return (1);
    }


    int     backtrack(int tab[N][N],int x ,int y, int *nbr)
    {
       if (x >= N)
       {
          print(tab);
          *nbr += 1;
       }
       while (++y < N)
         if (check(tab, x, y))
         {
              tab[x][y] = 1;
              if (backtrack(tab, x + 1, -1, nbr))
                  return (1);
              tab[x][y] = 0;
         }
       return (0);
    }


    int     ft_ten_queens_puzzle(void)
    {
       int tab[N][N];
       int nbr;
       int b;

       nbr = -1;
       while(++nbr < N)
       {
          b = -1;
          while (++b < N)
           tab[nbr][b] = 0;
       }
       nbr = 0;
       backtrack(tab,0,-1, &nbr);
       return (nbr);
    }

    int main()
    { 
             printf("%d\n",ft_ten_queens_puzzle());
     }

Answer 1

Your output is coming out random due to a couple of bugs in your print function :

a) If you are printing out a grid, then EVERY cell must be output, but you are not printing cells where tab[a][i] is 0

b) You need a newline at the end of EVERY line, but your write statement is in the wrong place

So the function should be like :

void  print(int tab[N][N])
{
   char c;

   for (int i=0; i < N; i++)
   {
      for (int a=0; a < N; a++)
      {
         if (tab[a][i])
         {
            c = '0' + a;
         }
         else 
         {
             c = ' ';
         }
         write(1, &c, 1);
     }
     write(1, "\n", 1);
   }
}

A couple of tips/feedback :

• Use full easy-to-understand variable names.

• Don't use that awkward "int x = -1; while (++x < N) {" format - the standard for (int x=0; x < N; x++) { format is better

• Indent your code correctly. for example, in print, you had the write for the newline out side of it's intended loop, which was easily missed due to indentation issues

• Yes, the language allows you to skip the "{","}" for single-statement loops and if statements. I would STRONGLY recommend to never skip them, but always put them on all loops and ifs; It is so much easier to both prevent, and also to track down bugs (especially when indentation is not consistent)

Just my thoughts, I hope they help :)