CODEWITHSUNDEEP
c
randomlock
randomlock

Reputation: 29

Queen puzzle 4x4

I am trying to solve this Queen problem of placing 4 queen in 4x4 matrix . I know it can be solved with backtracking algorithm . However i have not studied that and i am trying to solve it with my current knowledge . So what i am trying is to generate all possible combination of Queen in 4x4 matrix and print only one which cannot cancel each other .

1) For generating all combination , i am using rand function .

However there is obviously fault in my above coding . There are some outputs with only three '1' instead of four '1' . I am not able to eliminate this problem .

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

main()
{
    srand(time(NULL));
    int ar[30][30], i , j , a , b , c = -1, d = -1, k = 0;  

    while (1)
    {
        for (i = 0 ; i < 4 ; i++)
        {
            for (j = 0 ; j < 4 ; j++)
            {
                ar[i][j] = 0;
            }
        }

        for (i = 0 ; i < 2 ; i++)
        {
            for (j = 0 ; j < 2 ; j++)
            {
                a = rand() % 3 ;
                b = rand() % 3 ;
                if (a != c || b != d)
                {
                    ar[a][b] =  1 ; // here 1 = Queen 
                    c = a ;
                    d = b;
                }
            }
        }
    }  
}

2) Also is there any way i can reduce the time complexity using only these method ?

Upvotes: 0

Views: 453

Answers (3)

Paul Ogilvie
Paul Ogilvie

Reputation: 25286

The following is the brute force, backtracking code for the 8 queens problem, asked some time ago. Just change 8 to 4:

int checkBoard(int board[8][8]);
int putQueens(int board[8][8], int nQueens);
void printBoard(int board[8][8]);

int eightQueens(void)
{
    int board[8][8];
    memset(board, 0, sizeof(int)*64);
    if (putQueens(board, 0)) {
        printBoard(board);
        return (1);
    }
    return(0);
}


int putQueens(int board[8][8], int nQueens)
{
    int i, j;
    for (i=0; i<8; i++) {
        for (j=0; j<8; j++) {
            if (board[i][j]==0) {
                board[i][j]= 1;
                if (checkBoard(board)) {
                    if (nQueens==7) return(1);
                    if (putQueens(board, nQueens+1)) return(1);
                }
                board[i][j]= 0;
            }
        }
    }
    return(0);
}
int checkBoard(int board[8][8])
{
    int i, j;
    for (i=0; i<8; i++) {
        for (j=0; j<8; j++) {
            if (board[i][j]) {
                int ii, jj;
                for (ii=i+1; ii<8; ii++) {
                    if (board[ii][j]) return(0);
                }
                for (jj=j+1; jj<8; jj++) {
                    if (board[i][jj]) return(0);
                }
                for (ii=i+1, jj=j+1; ii<8 && jj<8; ii++, jj++) {
                    if (board[ii][jj]) return(0);
                }
                for (ii=i-1, jj=j-1; ii>0 && jj>0; ii--, jj--) {
                    if (board[ii][jj]) return(0);
                }
                for (ii=i-1, jj=j+1; ii>0 && jj<8; ii--, jj++) {
                    if (board[ii][jj]) return(0);
                }
                for (ii=i+1, jj=j-1; ii<8 && jj>0; ii++, jj--) {
                    if (board[ii][jj]) return(0);
                }
            }
        }
    }
    return (1);
}
void printBoard(int board[8][8])
{
    int i,j;
    printf("  ");
    for (j=0; j<8; j++) printf(" %1d",j+1); printf("\n");

    for (i=0; i<8; i++) {
        printf("%1d ",i+1);
        for (j=0; j<8; j++)
            printf(" %1c", board[i][j]==0? '-':'*');
        printf("\n");
    }
}

Upvotes: 0

M Oehm
M Oehm

Reputation: 29126

(1) You check only that a queen isn't placed on the same square as the last queen you placed. Remove the variables c and d and check whether ar[a][b] is still zero.

(2) Your scatter approach will produce many set-ups that are misses. Especially, because you don't enforce that ther cannot be any queens on the same rank and file. (In addition, rand() % 3 produces random values from 0 to 2, inclusively. You will never get a non-threatening configuration that way.)

If you want to use your random (bogosort) approach, you could use a one-dimensional array where the index is the rank and the number is the file where a queen is. Then you start with:

int queen[4] = {0, 1, 2, 3};

and shuffle the array. For 4 queens, that will yield 4! = 24 possibile configurations. You could try to iterate through them systematically.

Upvotes: 1

pmg
pmg

Reputation: 108978

Instead of using temporary variables to check whether the array is filled, use the array itself!

    for (i = 0 ; i < 2 ; i++)
    {
        for (j = 0 ; j < 2 ; j++)
        {
            a = rand() % 3 ;
            b = rand() % 3 ;
            if (ar[a][b] == 0)
            {
                ar[a][b] =  1 ; // here 1 = Queen 
            }
        }
    }

Your problem is that the inner loop will execute 4 times and you can only control 1 repeat with variables c and d.

Let's say a is 1 and b is 1: you make c = 1 and d = 1.

then a is 2 and b is 1 ... making c = 2 and d = 1.

then if a is 1 and b is 1 again, you cannot check for duplicate.

Upvotes: 1

Related Questions