C++

Forum

 
Classic N Queensm problem

zeroblank (67)
i had this code written out long time ago and up til now i cant figure out what is wrong with it .. i even tried debugging and im still clueless.

the problem is as follow:

1- when i undo my choice in the else statement i still get the values in the array although i assigned it to zero
2- State = 0 only has one value of i which is zero although there is a loop ..

could u tell me please why my code is ignoring my commands ? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
#include<iostream>


using std::cout;
using std::endl;



bool valid(int * queen, int current_index)
{
	for (int j = 0; j < current_index; j++)
	{
		int slope = (queen[current_index] - queen[j]) / (current_index - j);
		if ((queen[current_index] == queen[j]) || (slope == 1))
		{
			return false;
		}
	}
	return true;
}

void print(int* queen, int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << queen[i] << " ";
	}
	cout << endl;
}

bool Queen(int * queen, int state, int n)
{
	if (state == n)
	{
		return true;
	}
	else
	{
		for (int i = 0; i < n; i++)
		{
			queen[state] = i;
			if (valid(queen, state))
			{
				if (Queen(queen, ++state, n)) return true;
				else
				{
					queen[state] = 0;
				}
			}
		}
	}
	return false;
}

int main()
{
	int queen[4] = { 0 };
	Queen(queen, 0, 4);
	system("pause");
}
jonnin (11410)
print out the result of all your is valid checks.

I ran it and got 0 2 3 3 from print()
Last edited on
zeroblank (67)
yeah which is weird giving that this is not a valid result and i stated that if it's Queen(queen , ++state , n) is false queen[state] = 0; which is not applied in here and this is not the only problem i complained i encountered in this problem also the first state 0 only have an i of 0 it doesnt go further ignoring the for loop
zeroblank (67)
anyone ??
lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
#include<iostream>


using std::cout;
using std::endl;



bool valid(int * queen, int current_index)
{
        for (int j = 0; j < current_index; j++)
        {
                int slope = (queen[current_index] - queen[j]) / (current_index - j);
                if ((queen[current_index] == queen[j]) || (slope == 1) || slope == -1 )    // extra slope = -1 check
                {
                        return false;
                }
        }
        return true;
}

void print(int* queen, int n)
{
        for (int i = 0; i < n; i++)
        {
                cout << queen[i] << " ";
        }
        cout << endl;
}

bool Queen(int * queen, int state, int n)
{
        if (state == n)
        {
                return true;
        }
        else
        {
                for (int i = 0; i < n; i++)
                {
                        queen[state] = i;
                        if (valid(queen, state))
                        {
                                if (Queen(queen, state+1, n)) return true;    // DON'T update state itself
                        }
                        else                                                  // moved else to different if
                        {
                                queen[state] = 0;
                        }
                }
        }
        return false;
}

int main()
{
        int queen[4] = { 0 };
        Queen(queen, 0, 4);
        print(queen, 4);
}

zeroblank (67)
Last Chance is my only and last hope <3 thanks a tone <3 <3 ..
Topic archived. No new replies allowed.