[jwhiteknight]

I have to write the program 8 queens. where the out put looks like
Q******
**Q****
****Q**
******Q
*Q*****

I have to print out all 92 solutions.
I am not even sure if I am on the right track.

I get this error message when I go to compile.
error: method displayBoard in class EightQu eens cannot be applied to given types;
displayBoard();
^
required: int[]
found: no arguments
reason: actual and formal argument lists differ in length

public class EightQueens
{
private final int size = 8;
int [] board = new int [size];


    public  void main (String args []) // main method
    {
    int  y =0;
    board[0] = 1;
    while (y >=0)
    {
board[y]++;
    }
while ((board[y]< 8) && (solveQueens(y)));
    if (board[y] < 8)
    {
    if( y < 7)
    {
    board[++y]=1;
    }
    else
    {
        displayBoard();
    }
    }
    }//  end main

    private  boolean solveQueens(int y)
    {
int x = board[y];

for (int i = 1;i < y; i++)
{
int t = board[y-1];
if (t==x || t==x - i || t ==x +1)
{
    return true;
private void displayBoard (int[] board)
{
    int A =board.length; // sets the lenght for the loops
    for ( int i =0; i < A; i++)
    {
        for (int j=0; j < A; j++)
        {
            if (board[A] == j)
                System.out.print("Q ");
            else
                System.out.print("* ");
         }
        System.out.println();
    }
System.out.println();
    }
}

ps.
is there an easy way to copy and past my code from linux vim to this site. with out duplicating the code that is in the vim?

[ianian112]

sorry if you find this rude, but have you ever programmed in Java before?

Your method expects an array, but you call it without one on line 24.

[NathanMullenax]

The error is pretty straightforward. displayBoard needs an argument--an array of integers.

As far as the algorithm is concerned, you could use backtracking, but you should be aware of how much space and time that would take up. You can reduce the amount of space needed by coming up with a better board representation and keeping track of symmetry.

There are actually only 12 'fundamental' solutions; if you find these twelve, you can generate all of the others by rotating, reflecting, and transposing that set of twelve.

You could actually encode the whole board in 3 bytes if you observe that it only takes three bits to describe the position of a queen within a single row.

Hope this helps.

This post has been edited by NathanMullenax: 20 January 2013 - 06:25 PM

[NathanMullenax]

Pseudo-spoiler. Here's how I did it in C++. It could certainly be improved, but it works and it is pretty fast.

Spoiler

#include <iostream>
#include <vector>
#include <set>
#include <stdlib.h>

// solve 8 queens problem w/ backtracking
typedef struct 
{
    unsigned char rows[8];
} partial_p;

typedef union
{
    partial_p p;
    unsigned long long cmp;
} partial;

static inline bool
getbit( partial const & p, int bit )
{
    return ((p.cmp >> bit)&1)==1;
}

static inline bool
getbit( partial const & p, int x, int y )
{
    return getbit(p,x+(y<<3));
}

void
print_solution( partial const & p )
{
    std::cout << "\n";
    for(int y=0; y<8; ++y)
    {
        for(int x=0; x<8; ++x)
        {
            std::cout << (getbit(p,x,y)?"1":"-");
        }
        std::cout << "\n";
    }
}

inline bool 
operator< ( partial const & a, partial const & b )
{
    return a.cmp < b.cmp;
}

std::set<partial> solutions;

static inline void
setbit( partial &p, int bit )
{   
    unsigned long long mask = 1;
    mask <<= bit;
    p.cmp |= mask;
}

static inline partial
flipv( partial const & p )
{
    partial q;
    for(int i=0; i<8; ++i)
    {
        q.p.rows[i] = p.p.rows[7-i];
    }
    return q;
}

static inline partial
fliph( partial const & p )
{
    partial q;
    q.cmp = 0;
    for(int i=0; i<8; ++i)
    {
        // http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
        q.p.rows[i] = (p.p.rows[i] * 0x0202020202ULL & 0x010884422010ULL) % 1023;
    }
    return q;
}

static inline partial
transpose( partial const & p )
{
    partial q;
    q.cmp = 0;
    for(int y=0; y<8; ++y)
    {
        for(int x=0; x<8; ++x)
        {
            if(getbit(p,x+(y<<3)) )
                setbit(q,(x<<3)+y);
        }
    }
    return q;
}

static inline bool
valid_cols_n_rows( partial const & p )
{
    bool valid(true);
    unsigned char taken(0);
    unsigned char c;
    for(int i=0; valid && i<8; ++i)
    {
        c = p.p.rows[i];
        valid = valid && ((taken & c)==0);
        valid = valid && ((c & (c-1))==0);  // 0 or 2^k
        taken |= p.p.rows[i];
    }
    return valid;
}

static inline bool
validdiags( partial const & p )
{
    static int sums[30];

    for(int i=0; i<30; ++i)
    {
        sums[i]=0;
    }
    
    for(int y=0; y<8; ++y)
    {
        for(int x=0; x<8; ++x)
        {
            // this pixel falls in two different diagonals
            if( getbit(p,x,y) )
            {
                // negative diagonals
                sums[x+y]++;     // x+y goes 0..14
                sums[x-y+22]++;  
                if(sums[x+y]>1||sums[x-y+22]>1)
                    return false;
            }
        }
    }
   
    return true;
}

bool
valid( partial const & p )
{
    //return validrows(p) && validcols(p) && validdiags(p);
    
    return valid_cols_n_rows(p) && validdiags(p);
}

void 
compute_partials( std::vector<partial> & ps, partial const & p )
{
    for(int i=0; i<64; ++i)
    {
        if( !getbit(p,i) )
        {
            partial pp = p;
            setbit(pp,i);
            if( valid(pp) )
            {
                ps.push_back(pp);
            }
        }
    }
}

bool unique( partial const & p )
{
    partial q;
    if( solutions.count(p)>0 )
        return false;
    q = flipv(p);
    if( solutions.count(q)>0 )
        return false;
    q = fliph(q);
    if( solutions.count(q)>0 )
        return false;
    q = flipv(q);
    if( solutions.count(q)>0 )
        return false;
    q = transpose(q);
    if( solutions.count(q)>0 )
        return false;
    q = flipv(q);
    if( solutions.count(q)>0 )
        return false;
    q = fliph(q);
    if( solutions.count(q)>0 )
        return false;
    q = flipv(q);
    if( solutions.count(q)>0 )
        return false;
    return true;
}

int
main()
{
    partial p;
    p.cmp = 0;
    solutions.insert(p);
    
    std::cout << "--------------------------------------------------------------\n";
    std::cout << "This program solves the 8-queens problem on an 8x8 grid.      \n";
    std::cout << "The point of this problem is to find positions for 8 queens.  \n";
    std::cout << "on a chessboard such that none of them can attack one another.\n";
    std::cout << "--------------------------------------------------------------\n\n";
    
    std::cout << "Press enter to begin...\n";
    std::cin.ignore();
    
    for(int i=0; i<8; ++i)
    {
        std::cout << "- Partial solutions so far: " << solutions.size() << "\n";
        std::vector<partial> next;
        for(std::set<partial>::iterator it=solutions.begin(); 
            it!=solutions.end(); ++it )
        {
            compute_partials( next, *it );
        }
        solutions.clear();
        for(int j=0; j<next.size(); ++j)
        {
            if( unique( next[j] ) )
                solutions.insert( next[j] );
            
        }
    }
    
    std::cout << "\n" << solutions.size() << " fundamental solutions found: \n\n";
    std::cout.flush();
    
    std::set<partial>::iterator it;
    int solno=1;
    for(it=solutions.begin(); it!=solutions.end(); it++)
    {
        std::cout << "Solution #" << solno++ << "\n";
        print_solution(*it);
        if( solno <= solutions.size() )
        {
            std::cout << "\nPress enter to see the next solution.\n";
            std::cin.get();
        }
        
    }
   
}

[jwhiteknight]

ianian112, on 20 January 2013 - 06:23 PM, said:

sorry if you find this rude, but have you ever programmed in Java before?

Your method expects an array, but you call it without one on line 24.

no i don't find it very rude.. I am very new to java I am just starting my second java class. I would rather be learning MCSA... but I am trying my best

[macosxnerd101]

Make sure to properly indent and space your code as well to make it easier to read. It will help us better get a handle on your logic, and it will help you better read your code.

[jwhiteknight]

fix the code, so i don't get any errors, when I go and compile the code, but when I go to run the program I don't get any out put I think I am stuck in some sore of loop and it is not getting to the printboard method.

public class EightQueens
{
    public static  void main (String args []) // main method
    {
        int size = 8;
        int [] board = new int [size];
    int  y =0;
    board[0] = 1;
    while (y >=0)
    {
board[y]++;
    }
while ((board[y]< 8) && (solveQueens( y, board)))// int [])));
    if (board[y] < 8)
    {
    if( y < 7)
    {
    board[++y]=1;
    }
    else
    {
        displayBoard( board);
    }
   // else
   // {
     //   y--;

   // }
    }
    }//  end main

    private static boolean solveQueens(int y,int[] board)
    {
int x = board[y];
//system.out.printf (" in method solvequeens %d",x);

for (int i = 1;i < x; i++)
{
int t = board[y-1];
if (t==x || t==x - i || t ==x +1)
{
    return true;
}
    }