Thread: Could someone help me with this n queens-based problem?

  1. #1
    Registered User
    Join Date
    Oct 2014
    Posts
    225

    Could someone help me with this n queens-based problem?

    I have a problem where eight queens are to be placed on an 8x8 chessboard in such a way that no queens will be able to attack each other (i.e., lie along same row, column or diagonal). The program will prompt the user to enter, for each column, the row that contains a queen. For the given configuration, the program should print "Safe" if no queen can attack any other queen (none are sharing the same row, column or diagonal), or print "Unsafe" if an attack is possible. I'm not entirely sure how to do this however, and I'd like some help. I am working from this base code:
    Code:
    
    
    Code:
      #include <iostream>
    using namespace std;
    int main() {
       int board[8];
       cout << "Enter the rows containing queens, in order by column: ";
       for(int i = 0; i < 8; ++i) {
           cin >> board[i];
       }
       cout << endl;
       for(int i = 0; i < 8; ++i) {
           for(int a = 0; a < 8; ++a) {
               if(board[a] != i) {
                   cout << ".";
              //     cout << ".";
               } else {
                 //     cout << ".";
                   cout << "Q";
               }
           }
           cout << endl;
       }
    }

  2. #2
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Allocate a 2d array, every element initialized to 0.

    Each queen is the value 1.

    Sum elements in each row, store
    Sum elements in each column, store
    Sum elements in each diagonal direction, going both ways, store

    If any sum is larger than 1, you know it's not safe.

    This is how I would do it, at least.

  3. #3
    Registered User
    Join Date
    May 2010
    Posts
    4,539
    Let me first point out that this is also posted here.

    Then I will remark that at least you copied some code from somewhere that is at least formatted correctly.

    Next I'm going to wish you luck, since just the other day you couldn't even print a simple histogram this topic is likely to be very interesting.


    Jim

  4. #4
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Quote Originally Posted by jimblumberg View Post
    Let me first point out that this is also posted here.

    Then I will remark that at least you copied some code from somewhere that is at least formatted correctly.

    Next I'm going to wish you luck, since just the other day you couldn't even print a simple histogram this topic is likely to be very interesting.


    Jim
    I lol'd.

  5. #5
    Registered User
    Join Date
    Oct 2014
    Posts
    225
    Quote Originally Posted by MutantJohn View Post
    Allocate a 2d array, every element initialized to 0.

    Each queen is the value 1.

    Sum elements in each row, store
    Sum elements in each column, store
    Sum elements in each diagonal direction, going both ways, store

    If any sum is larger than 1, you know it's not safe.

    This is how I would do it, at least.
    I would like to do this, but I still don't quite get it. Where is every element stored in my current program?

  6. #6
    Registered User
    Join Date
    May 2009
    Posts
    3,867
    Quote Originally Posted by Kelton2 View Post
    I would like to do this, but I still don't quite get it. Where is every element stored in my current program?
    Lookup the arrays in your book; "your" program is using an 1d array the suggestion was using an 2d array.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  7. #7
    Registered User Alpo's Avatar
    Join Date
    Apr 2014
    Posts
    877
    Quote Originally Posted by Kelton2 View Post
    I would like to do this, but I still don't quite get it. Where is every element stored in my current program?
    You basically start out with something like this:

    Code:
        bool board[8][8] = {{false}}; // init to zero
    A small 5*5 board with "queen" at position (board[2][1]):

    [0] [0] [0] [0] [0]
    [0] [0] [0] [0] [0]
    [0] [1] [0] [0] [0]
    [0] [0] [0] [0] [0]
    [0] [0] [0] [0] [0]

    Now, in the loop that gathers users input, for every new entry, iterate through the 8 directions a queen can move, starting with the x and y value that the user has passed in for the new queen position:

    = (no change to user value)
    -- (iterate down from user value)
    ++(iterate up from user value)

    Direction:[y][x]
    ------------------------
    // left:[=][--]
    // left-up:[--][--]
    // up:[--][=]
    // right-up: [--][++]
    // right: [=][++]
    // right-down: [++][++]
    // down: [++][=]
    // left-down: [++][--]


    At every step of these iterations, we check to see "is this boolean value at board[y][x] true?", and if it is, then the queen the user has passed in is under attack, and that move is invalid.
    WndProc = (2[b] || !(2[b])) ? SufferNobly : TakeArms;

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with n queens
    By programmerc in forum C Programming
    Replies: 1
    Last Post: 02-03-2013, 01:38 PM
  2. 8 queens problem in C
    By reds in forum C Programming
    Replies: 1
    Last Post: 04-25-2011, 11:35 PM
  3. Eight Queens Problem...Tried Everything.
    By Kiros_Xannon in forum C++ Programming
    Replies: 6
    Last Post: 09-27-2009, 02:46 PM
  4. 8 Queens problem
    By Dashing Boy in forum C++ Programming
    Replies: 14
    Last Post: 10-15-2007, 12:12 PM