Results 1 to 10 of 10
  1. #1
    sonofshirt is offline Member
    Join Date
    Sep 2010
    Posts
    6
    Rep Power
    0

    Default Determining whether a queen can attack another piece

    I'm working on a program to solve the n-queens problem, and am having trouble with determining whether a queen can attack another queen. For the problem, I assume that there is only 1 queen on each row, and they only move within that row to solve the problem. Thus, I can represent the locations of the queens with an array (int[] queens), where the position in the array is the row, and the value of the integer is the column. For example, queens[0] = 0 would mean the queen is in the top left corner of a board, and if there are 5 queens, queens[4] = 4 would indicate it's in the bottom right hand corner. I tried to make a simple problem below that just has a 5x5 board that sets the queens so they cannot attack each other. And I've narrowed down my problem to the "testAttack" method, but it's not working like I want it to. For that method, I assume that queens are not going to be in the same row, so the horizontal check would be redundant, so I'm just trying to implement the column check and the diagonal check.

    Any help to improve the testAttack method would be helpful. thanks!

    For reference, I also posed this same question at the coderanch: Determining whether a queen can attack another piece (Java in General forum at JavaRanch)


    Java Code:
    import java.util.Scanner;
    
    public class Main {
    
        public static void main(String[] args) {
            // To hold the number of queens for the problem
            int numQueens;
            // Scanner class to get the input from user
            Scanner keyboard = new Scanner(System.in);
            // Prompt the user for the number of Queens
            System.out.println("Welcome to the N-Queens Solver.");
            System.out.println();
            QueenBoard test = new QueenBoard(5);
            test.setToGoal();
    
            boolean testGoal = test.isGoalState(test.getQueens());
            test.printBoard();
            System.out.println("Should be false: " + testGoal);
        }
    
    public static class QueenBoard {
        // Going to use 2 dimensional array to represent the board. 1 will represent
        // a Queen, while 0 is a blank space
        private int[][] board;
        // the queen positions will be represented by a single array, since there
        // can only be one queen per row
        private int[] queens;
        // keeps track of what n is
        private int nSize = 0;
    
        // Constructor allows for a board with width/length n
        public QueenBoard (int n){
            board = new int[n][n];
            queens = new int[n];
            nSize = n;
        }
    
        public void setToGoal(){
            queens[0]=4;
            queens[1]=1;
            queens[2]=3;
            queens[3]=0;
            queens[4]=2;
            this.convertQueensToBoard();
        }
    
        public int[] getQueens(){
            return queens;
        }
        
    /* Because we assume there are no queens in the same row, all we much do is
     * check to see if there is a queen in the same column or in a diagonal
     * line. This method checks to see if a queen placement at a given row/column
     * combination is valid
     */
        public boolean testAttack(int row, int column){
            for (int i = 1; i <= row; i++)
                    // checks columns
                if (queens[row - i] == column
                    // check diagonal to upper left
                    || queens[row -1] == column - i
                    // check diagonal to upper right
                    || queens[row -1] == column + i)
                    // if any of these match, there is a conflict
                    return false;
            // only get to this point if there are no conflicts
            return true;
        }
    
            public boolean isGoalState(int[] state){
            boolean goal = false;
            for (int i=0; i < nSize; i++){
                // if a queen can attack another queen, then we know we haven't
                // reached our goal state yet and we can stop the for loop and
                // select a new operator
                if (testAttack(i, state[i]) == true){
                    goal = false;
                    System.out.println("Setting to False");
                }
                else {
                    System.out.println("Setting to True");
                    goal = true;
                }
            }
            return goal;
        }
    
                // Method to print the board
        public void printBoard(){
            System.out.println();
            // loop through the rows of the board
            for (int i = 0; i < board.length; i++){
                // loop through each column for each row of the board
                for (int j = 0; j < board.length; j++){
                    // if the value is blank, print out an X
                    if (board[i][j] == 0)
                        System.out.print(" .");
                    // otherwise (if there's a value) there must be a queen,
                    // so print out a Q
                    else
                        System.out.print(" Q");
                    // at the end of each row, print a new line
                    if (j == board.length-1)
                        System.out.println();
                }
            }
        }
    
        private void convertQueensToBoard(){
            for (int i=0; i<nSize; i++){
                for (int j=0; j<nSize; j++){
                    if (queens[i] == j)
                        board[i][j] = 1;
                    else
                        board[i][j] = 0;
                } // inner for loop
            } // outer for loop
          } // end of method
        } // end of class
    
    }

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,655
    Blog Entries
    7
    Rep Power
    21

    Default

    Think of a regular X-Y grid; each queen is positioned at a certain (x, y); you already made sure every queen is on a different y position (each queen in a different row). You have to make sure each queen is also on:

    1) a different x position (a different column)
    2) a different 'upgoing' diagonal
    3) a different 'downgoing' diagonal.

    1) is easy: simply check if you can find another queen that has a same x position as the queen to be checked.

    2) and 3) aren't difficult either but take a bit of (simple) math: an upgoing diagonal has the mathematical representation y == x+c; if you can find two queens at positions (x, y) and (x', y') such that y == x+c && y' == x'+c they're on the same upgoing diagonal. A same reasoning applies for 3) where the downgoing diagonal is represented by y == c-x.

    kind regards,

    Jos
    Last edited by JosAH; 10-07-2010 at 05:31 PM.

  3. #3
    Ronin is online now Senior Member
    Join Date
    Oct 2010
    Posts
    384
    Rep Power
    5

    Default

    JosAH,

    No disrespect but as a non-maths person, that mathematic notation was a little too much for the likes of me.

    sonofshirt,

    After checking the column as previously suggested, then one solution would be to implement a series of loops. The first will increment the current column position whilst incrementing the current row. This is done until you reach the edge of the board, validating each position as you go. This process is repeated for the other directions as follows:

    column++, row--
    column--, row++
    column--, row--

    Regards.
    Last edited by Ronin; 10-07-2010 at 05:48 PM.

  4. #4
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,987
    Rep Power
    9

  5. #5
    sonofshirt is offline Member
    Join Date
    Sep 2010
    Posts
    6
    Rep Power
    0

    Default

    yes, and that's referenced in the original post. Thanks for being vigilant, though!

  6. #6
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,987
    Rep Power
    9

    Default

    Ah! I just realized it was already referenced in the OP. Whoops, carry on!

  7. #7
    sonofshirt is offline Member
    Join Date
    Sep 2010
    Posts
    6
    Rep Power
    0

    Default

    appreciate the replies. I'm working on reconfiguring the method, and clarifying what it's supposed to return (I think even I was a bit confused, and I wrote the damn things..)

    Thanks for the thoughts, I'll repost here as I take another whack at it...

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,655
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Ronin View Post
    JosAH,

    No disrespect but as a non-maths person, that mathematic notation was a little too much for the likes of me.
    I don't see much math notation, most of it is valid Java code as well; if you don't understand simple things like this, I wonder if you can ever make it in the programming business ...

    kind regards,

    Jos

  9. #9
    Ronin is online now Senior Member
    Join Date
    Oct 2010
    Posts
    384
    Rep Power
    5

    Default

    JosAH

    I find your comments completely unnecessary and my ability as a programmer (nor yours for that matter) should NOT be called into question. My comment was not intended to defame yours in any way but to provide layman's terms for less knowledgable individuals viewing this thread.

    I am aware of my correct lack of contribution to this forum, something which should not be confused with lack of ability. Like you I am here to assist where I can so lets put this aside and play nice.

    Regards.

  10. #10
    sonofshirt is offline Member
    Join Date
    Sep 2010
    Posts
    6
    Rep Power
    0

    Default

    figured this out (code on the other forum). Thanks, everyone!

Similar Threads

  1. small piece of code: cannot set a max
    By senca in forum New To Java
    Replies: 1
    Last Post: 03-06-2010, 08:26 PM
  2. Decode this piece of Code
    By mikeyl62 in forum New To Java
    Replies: 2
    Last Post: 02-27-2010, 08:59 PM
  3. Determining ActionListener
    By siamino in forum New To Java
    Replies: 12
    Last Post: 05-25-2009, 11:04 PM
  4. detecting flooding attack
    By prashant in forum Networking
    Replies: 1
    Last Post: 12-27-2008, 08:44 PM
  5. Replies: 5
    Last Post: 10-25-2008, 08:42 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •