Classic Eight Queens Puzzle in Java

using arrays w/console text output

Page 1 of 1

6 Replies - 13043 Views - Last Post: 26 March 2010 - 05:03 PM Rate Topic: -----

#1 Charlie IronGleet  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 225
  • Joined: 29-January 09

Classic Eight Queens Puzzle in Java

Posted 27 February 2009 - 11:32 AM

Hello,

I am working on a program assignment in Java that is supposed to output one possible solution to the eight queens chess puzzle. ( the goal is to place eight queens on a chessboard such that no two queens can attack each other -- no two queens on the same row, same, column or same diagonal). I have googled this and seen many solutions using topics we've not covered in class -- i.e. recursion, backtracking, etc. So I'm trying to find a solution with just the materials covered in the first few weeks of intro to java -- meaning basically just using arrays and printing the output to the console in a form like this: ***Q***** ...

Thus far I've been able to develop a conceptual algorithm and am having a whale of a time translating it into code. It goes like this:

-- Start with a queen in the top left corner.
-- place a queen in the second column and move till it finds a spot where it can't be hit by the queen in the first column
-- Continue this process with the remaining columns and if there is no place for a queen in the current column go back to the preceding column and move the queen in that column.
-- if the current column is the last column and a safe place exists for the last queen then a solution has been found.
-- display the solution

So to start with I'll need a two-D 8x8 array. I'll fill it with zeros to begin with to indicate empty spaces. A queen will be indicated by a 1. I'll place a queen in the upper left hand corner. And I'll create a method that will place a queen in the second column, first spot, and move till it can't be hit. This is about as far as I've been able to see my way.

I know you guys can't code this for me but any help you are able to provide would be greatly appreciated. I'm truly stumped here.

Thanks much,
IronGleet


public class EightQueens {
			  public static void main(String args[]) {
					int[][] board = new int[8][8]
					for(int row=0; row<8; row++) {
						for(col = 0; col<8; col++) {
							 board[row][col] = 0;
						 }
					 }
					board[0][1] = 1;
					moveQueen();
					
			  }
			public static void moveQueen(int[][] board) {
				   board[1][0] = 1;
				   Here is where I lose all confidence :>

			}
}

This post has been edited by Charlie IronGleet: 27 February 2009 - 11:33 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Classic Eight Queens Puzzle in Java

#2 Charlie IronGleet  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 225
  • Joined: 29-January 09

Re: Classic Eight Queens Puzzle in Java

Posted 27 February 2009 - 11:53 AM

View PostCharlie IronGleet, on 27 Feb, 2009 - 10:32 AM, said:

Hello,

I am working on a program assignment in Java that is supposed to output one possible solution to the eight queens chess puzzle. ( the goal is to place eight queens on a chessboard such that no two queens can attack each other -- no two queens on the same row, same, column or same diagonal). I have googled this and seen many solutions using topics we've not covered in class -- i.e. recursion, backtracking, etc. So I'm trying to find a solution with just the materials covered in the first few weeks of intro to java -- meaning basically just using arrays and printing the output to the console in a form like this: ***Q***** ...

Thus far I've been able to develop a conceptual algorithm and am having a whale of a time translating it into code. It goes like this:

-- Start with a queen in the top left corner.
-- place a queen in the second column and move till it finds a spot where it can't be hit by the queen in the first column
-- Continue this process with the remaining columns and if there is no place for a queen in the current column go back to the preceding column and move the queen in that column.
-- if the current column is the last column and a safe place exists for the last queen then a solution has been found.
-- display the solution

So to start with I'll need a two-D 8x8 array. I'll fill it with zeros to begin with to indicate empty spaces. A queen will be indicated by a 1. I'll place a queen in the upper left hand corner. And I'll create a method that will place a queen in the second column, first spot, and move till it can't be hit. This is about as far as I've been able to see my way.

I know you guys can't code this for me but any help you are able to provide would be greatly appreciated. I'm truly stumped here.

Thanks much,
IronGleet


public class EightQueens {
			  public static void main(String args[]) {
					int[][] board = new int[8][8]
					for(int row=0; row<8; row++) {
						for(col = 0; col<8; col++) {
							 board[row][col] = 0;
						 }
					 }
					board[0][1] = 1;
					moveQueen();
					
			  }
			public static void moveQueen(int[][] board) {
				   board[1][0] = 1;
				   Here is where I lose all confidence :>

			}
}


To be more specific about where I need help -- how do I check to see whether two queens are on a diagonal from one another?
Was This Post Helpful? 0
  • +
  • -

#3 vasdueva  Icon User is offline

  • D.I.C Head

Reputation: 15
  • View blog
  • Posts: 141
  • Joined: 03-April 07

Re: Classic Eight Queens Puzzle in Java

Posted 27 February 2009 - 12:09 PM

Decrement both row and column until one or the other == 0. This will move your 'marker' towards the upper left corner of the board.
If you find a queen between your latest queen and there solution is bad.

Next increment row but decrement column. This will move your position towards the bottom left. If a queen is found between your current queen and the edge of the board, you have a bad solution.
Was This Post Helpful? 0
  • +
  • -

#4 Charlie IronGleet  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 225
  • Joined: 29-January 09

Re: Classic Eight Queens Puzzle in Java

Posted 27 February 2009 - 12:40 PM

View Postvasdueva, on 27 Feb, 2009 - 11:09 AM, said:

Decrement both row and column until one or the other == 0. This will move your 'marker' towards the upper left corner of the board.
If you find a queen between your latest queen and there solution is bad.

Next increment row but decrement column. This will move your position towards the bottom left. If a queen is found between your current queen and the edge of the board, you have a bad solution.


Thanks -- here is what I have so far using that:

public class EightQueens {
	public static void main(String args[]) {
		//create an 8x8 array for the chess board
		int[][] board = new int[8][8];
		//fill the board with zeros, empty squares
		for(int row=0; row<8; row++) {
			for(int col=0; col<8; col++) {
				board[row][col] = 0;
			}

		}
		board[0][0] = 1;

		for(int row = board.length; row<0; row--) {
			for(int col = board[row].length; col < 0; col--){
				if(board[row][col] == 0) {
					board[row][col] = 1;
				}
			}

		}
	}
}


This doesn't look like it would do it -- how do you implement the first part of that algorithm in code, this part:Decrement both row and column until one or the other == 0. This will move your 'marker' towards the upper left corner of the board.
If you find a queen between your latest queen and there solution is bad.

Thanks!
IronGleet
Was This Post Helpful? 0
  • +
  • -

#5 vasdueva  Icon User is offline

  • D.I.C Head

Reputation: 15
  • View blog
  • Posts: 141
  • Joined: 03-April 07

Re: Classic Eight Queens Puzzle in Java

Posted 27 February 2009 - 01:54 PM

int queenRow;
int queenColumn;
while(row != 0 & column != 0 & !queenIsOnDiag) {
	 queenRow--;
	 queenColumn--;
	 if(board[queenRow][queenColumn] ==1) //has queen
	 {
			 queenIsOnDiag = true;
	  }
}



That should do the trick. It'll loop either until the position hits the edge of the board or until it finds a queen. Once the loop terminates check the boolean and you'll know if the queen has been place in an improper position.
Was This Post Helpful? 1
  • +
  • -

#6 Charlie IronGleet  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 225
  • Joined: 29-January 09

Re: Classic Eight Queens Puzzle in Java

Posted 28 February 2009 - 11:41 AM

View Postvasdueva, on 27 Feb, 2009 - 12:54 PM, said:

int queenRow;
int queenColumn;
while(row != 0 & column != 0 & !queenIsOnDiag) {
	 queenRow--;
	 queenColumn--;
	 if(board[queenRow][queenColumn] ==1) //has queen
	 {
			 queenIsOnDiag = true;
	  }
}



That should do the trick. It'll loop either until the position hits the edge of the board or until it finds a queen. Once the loop terminates check the boolean and you'll know if the queen has been place in an improper position.


I'm still really confused as to how this code here you gave me will tell me if a queen is on a diagonal from another queen. Also what do you think I should do: have a loop that places a queen starting in the second row in the first position then check to see if its an ok spot and if not move to the next position then check, etc? But how would I handle it if the position is not ok?

Could you explain to me how it is that this code detects a queen on a diagonal from any other queens?

Thanks,
IronGleet
Was This Post Helpful? 0
  • +
  • -

#7 Guest_Luis*


Reputation:

Re: Classic Eight Queens Puzzle in Java

Posted 26 March 2010 - 05:03 PM

To find out if a queen is the same diagonal you have to see if the difference between the file and the column is the same number, then you know that they are in the same diagonal:

If [Q1(file-column] == [Q2 (file-column)]
OR
[Q1(file-column] == [Q2 (file-column)]

Then 'QUeens in the same Diagonal'
Was This Post Helpful? 0

Page 1 of 1