# Thread: How to solve the Eight Queens puzzle without recursion?

1. Member
Join Date
Mar 2010
Posts
23
Rep Power
0

## How to solve the Eight Queens puzzle without recursion?

I made one class to hold all the moves, so I can easily backtrack with pop(). The push() adds a move to the stack.

Queens: package JEG_SKAL_BLI_PRO; i - Anonymous - gax7trbT - Pastebin.com
Moves: package JEG_SKAL_BLI_PRO; i - Anonymous - A6FpZQ09 - Pastebin.com

I thought I got the logic correct. But when I run the program, it has only placed 7 queens. Does anyone see what is going wrong here? :)

2. Senior Member
Join Date
Mar 2010
Posts
952
Rep Power
7
Please post your code here if you want help. I, for one, don't want to follow your links.

-Gary-

3. Member
Join Date
Mar 2010
Posts
23
Rep Power
0
Sure :)

Queens:

PHP Code:
```package JEG_SKAL_BLI_PRO;

import java.util.Scanner;

public class Queens {
public static void main(String[] a) {
Scanner in = new Scanner(System.in);

int[][] grid = new int[8][8];
boolean success;

Moves moves = new Moves();

for(int i=0;i < 8;i++) {

success = false; // initially no queen is placed

for(int j=0;j < 8;j++) {

/* THIS IS FOR DEBUGGING */
/*  place(i,j,grid,4);
p(grid);
String s = in.nextLine();
place(i,j,grid,0);   */

if(isLegal(i,j,grid)) {
place(i,j,grid);
success = true; // A queen is placed
Integer[] move = {i ,j};  // autoboxing
moves.push(move); // push the move onto the stack
break;
}

// check if a queen was placed. Or if not enough queens have been placed
if( (! success && j == 7) || (i == 7 && j == 7 && moves.length() < 8)) {
// System.out.println("failure");
Integer[] lastMove = moves.pop();
int lastY = lastMove[0];
int lastX = lastMove[1];
grid[lastY][lastX] = 0; // remove the last placed queen
j = lastX + 1;
i = lastY;
// System.out.println("backtracking!");
}
}
}
p(grid);

// moves.printMoves();
}

public static boolean isLegal(int y, int x, int[][] grid) {
if (isThreatenedVertically(y, x, grid)) return false;
if (isThreatenedHorizontally(y, x, grid)) return false;
if (isThreatenedDiagonally(y, x, grid)) return false;
return true;
}

public static boolean isThreatenedVertically(int y, int x, int[][] grid) {
// check above
for(int i=0;i < y;i++) {
if(grid[i][x] == 1) return true;
}
// check below
for(int i=y+1;i < grid.length;i++) {
// if(grid[i][x] == 1) return true;
}
return false;
}

public static boolean isThreatenedHorizontally(int y, int x, int[][] grid) {
// check left
for(int i=0;i < x;i++) {
if(grid[y][i] == 1) return true;
}
// check right
for(int i=x+1;i < grid.length;i++) {
if(grid[y][i] == 1) return true;
}
return false;
}

public static boolean isThreatenedDiagonally(int y, int x, int[][] grid) {
// check above and left
int dx = x - 1;
int dy = y - 1;
while(dx >= 0 && dy >= 0) {
if(grid[dy--][dx--] == 1) return true;
}
// check below and right
dx = x + 1;
dy = y + 1;
while(dx < grid.length && dy < grid.length) {
if(grid[dy++][dx++] == 1) return true;
}
// check above and right
dx = x + 1;
dy = y - 1;
while(dx < grid.length && dy >= 0) {
if(grid[dy--][dx++] == 1) return true;
}
// check below and left
dx = x - 1;
dy = y + 1;
while(dx >= 0 && dy < grid.length) {
if(grid[dy++][dx--] == 1) return true;
}
return false;
}

public static void p(int[][] grid) {
for(int i=0;i < grid.length;i++) {
for(int j=0;j < grid[0].length;j++) {
System.out.print(grid[i][j]);
}
System.out.println();
}
}

public static void place(int y, int x, int[][] grid) {
grid[y][x] = 1;
}

// for debugging
public static void place(int y, int x, int[][] grid, int i) {
grid[y][x] = i;
}
}```
And Moves:

PHP Code:
```package JEG_SKAL_BLI_PRO;

import java.util.ArrayList;

public class Moves {
private ArrayList<Integer[]> list = new ArrayList<Integer[]>();

public Moves() {

}

public Integer[] pop() {
if(list.size() < 1) return new Integer[]{0, 0}; // empty stack

Integer[] lastMove = list.get(list.size()-1);
list.remove(list.size()-1);

return lastMove;
}

public void push(Integer[] move) {
}

public void printMoves() {
for(int i=0;i < list.size();i++) {
int y = list.get(i)[0];
int x = list.get(i)[1];

System.out.println((i+1)+": Queen placed at: "+y+","+x);
}
}

public int length() {
return list.size();
}

}```
I am using php tags because with code tags so much whitespace is generated.

#### Posting Permissions

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