Talk:Number Theory

From Algorithmist
Jump to: navigation, search

That formula for checking the N-Queens problem is necessary but not sufficient. It effectively calculates the sum numbers such that each number is from a unique row and column. Therefore, a simple counter example is placing the queens along the diagonal. 65.110.240.184 22:11, 17 April 2008 (UTC)

Even more, it isn't sufficient for row and column noncollision either. Por example, on a 4x4 board the numbers could be 1, 5, 12, 16; sum is 34, or (4*(16+1))/2, but the first and fourth columns collide. 189.145.24.116 07:36, 2 August 2009 (UTC)


Backtracking provides an easy way to find that we can place queens or not. What we actually need is that queens shouldnt be at the same row, columns, or at diagonal position. So if A(i, j) represnts the ith row, and jth column. We can use a 1d array to solve our problem. let us assume, the kth queen is always placed in kth row, so we need a one-D array to see which column does it belongs too. Now following checks are required- 1). Column shouldn't be same, so for that if(x[i]==j) checks that condition. j is the column, where we trying to place kth queen(jt column), we check this for all i's from 1 to n. so if any of (k-1) queens are placed there then it will return false, that means search for other position, where this kth queen can be placed.

2). Diagonally queens should not cut each other. Now just visualize a 2-D array(matrix), mark rows from 1 to n, and columns for 1 to n. You will find that the difference of the terms, diagonally opposite to each other is constant. Note : check the absolute difference for both the main diagonal, and the other one. So now if these 2 conditions satisfied, we can place queens there.

== Hello friends its my first post in algorithmist site, My TC handle is fight, spoj handle fight, meet at acmTju, u can contact me at mans.austin@gmail.com. Hope my post is helpful. ==


This is my Code :

  1. include<iostream>
  2. include<vector>
  3. include<math.h>

using namespace std;

typedef vector <int> VI;

VI x;

int c = 0;

bool place(int k, int i) {

       for(int j=1;j<=k-1;j++)
               if(x[j]==i ||  abs(x[j] - i)==abs(j - k))
                       return false;
       return true;

}

void NQueen(int k, int n) {

       for(int i=1;i<=n;i++) {
               if(place(k, i)) {
                       x[k] = i;
                       if(k==n) {
                               for(int r=1;r<=n;r++)
                                       cout << x[r] << endl;
                               cout << endl;
                               c++;
                       }
                       NQueen(k+1, n);
               }
       }

} int main() {

       int n, k, i;
       cout << "enter how many queens : ";
       cin >> n;
       x.resize(n+1);
       x[0] = -1;
       NQueen(1, n);
       cout << "count : " << c << endl;

}