Title: Stack Algorithm N-Queens
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

Stack Algorithm: N-Queens

A Stack is a very simple data structure, but it can be used to implement some powerful programming techniques. Algorithms which logically need a Stack can often be reprogrammed into a Recursive algorithm. There are many times when one or the other of these related approaches can be very powerful.

Problems which lend themselves to a Recursive or Stack algorithm

1. Almost any compiler related thing fits this model. When I have had such problems in my industrial experience I resorted to something called "Recursive Descent"
2. Many puzzles fit can be solved with this approach. For example Sudoko, and finding a path through a Maize
3. Towers of Hanoi
4. N Queens problem

Queens.java


import java.util.ArrayList;
import java.util.Stack;


public class Queens {
    int[] m_board;
    int m_board_size;
    ArrayList<int[]> m_solutions=new ArrayList<int[]>();
    Stepper stepper = null;

    public Queens(int n, Stepper stepper)
    {
        m_board_size =n;
        m_board= new int[n];
        for (int i=0; i < m_board.length; i++)
            m_board[i]=-1;
        this.stepper = stepper;
    }
    public void solve_non_recursive(boolean all)
    {
        Stack<Integer> stack = new Stack<Integer>();
        boolean completed=false;
        int step = 0;
        stack.push(0); // Starting column

        while (!completed && stack.size() > 0)
        {
            int curr_starting_column = stack.peek(); // Get

            for (int curr_column=curr_starting_column; curr_column < m_board_size; curr_column++)
            {
                step = stack.size()-1;
                m_board[step] = curr_column;
                clearUnusedCells(step+1);

                if (check_step(step))
                {
                    if (step == m_board_size-1)
                    {
					
                        if (stepper != null)
                            stepper.step(m_board);
							
                        captureSolution();
                        if (!all)
                        {
                            completed = true;
                            break;
                        }
                        // Good solutions are captured.  If "all" = true then we are done
                        // If "all" is not true, then we move onto the next possibility as if this
                        // were a failed solution.
                    }
                    else
                    {
                            // The following statement is not quite a stack standard, but I need
                            // some easy way to replace whatever is on the top of the stack
                            stack.set(stack.size()-1, curr_column+1);
							
                            stack.push(0); // new starting column

                            break;

                    }
                }// end of if (check_step(step))

                // if we have exhausted the columns in this for loop, then we backtrack
                if (curr_column ==  m_board_size-1)
                    stack.pop();


            }// end of for loop


            if (stack.peek() >= m_board_size)
            {
                    stack.pop();
            }


        } // end of while loop
        System.out.println("Finished Queens");
    }


    public void solve(boolean all)
        {
            solve(0, all);
        }

    private boolean solve(int step, boolean all)
        {
            for (int i=0; i < m_board_size; i++)
            {
              //  cout << "Loop "<< m_curr_step << " " << i << endl;
                m_board[step] = i;
                clearUnusedCells(step+1);

                if (check_step(step))
                {
                    boolean results = false;
                    if (step == m_board_size-1)
                    {
                        if (stepper != null)
                            stepper.step(m_board);

                        captureSolution();
                        results = true;
                        //printSolutions();
                        //cout << "We did it!!"<< endl;
                    }
                    else
                        results = solve(step+1, all);

                    // In case we only want one solution, we need to
                    // provide a way out when a solution has been found.
                    if (results && !all) return true;
                }

            }
            return false;
        }


    private boolean check_step(int step)
    {
        // Because we are sequentially going through rows,
        //   we know the queens are not in the same row

        int col = m_board[step];
        int diag1, diag2;

        // Check to see if this column has been used yet
        diag1 = diag2 = col;
        for (int i=step-1; i >= 0; i--)
        {
            if (m_board[i] == col) return false;
            diag1 += 1;
            diag2 -= 1;
            if (diag1 == m_board[i]) return false;
            if (diag2 == m_board[i]) return false;
        }
        return true;
    }
    public void printSolutions(boolean printSolutions)
        {
            if (printSolutions)
            {
                for (int k=0; k < m_solutions.size(); k++)
                {
                    System.out.printf("%n************* %n Solution Number: %d %n", k );
                    int[] solution = m_solutions.get(k);
                    for (int i=0; i < m_board_size; i++)
                        System.out.printf("%d ",solution[i]);
                }
            }
            System.out.printf( "%n%n Num solutions =%d %n", m_solutions.size() );
        }
        private void captureSolution()
        {
            // Copy this solution before adding to m_solutions

            int[] solution = new int[m_board_size];
            for (int i=0; i < m_board_size; i++)
                solution[i] = m_board[i];

            m_solutions.add(solution);
        }
        private void clearUnusedCells(int start)
        {
            for (int i= start; i < m_board.length; i++)
                m_board[i]=-1;
        }


    public static void main(String[] args) {
        Queens q = new Queens(8, null);
        q.solve(true);
        q.printSolutions(true);
    }

}



Stepper.java Interface


 public interface Stepper {
    public void step(int[] m_board);
}


Drawing Queens on a Chess board

We are going to lift some code from the published answer from our previous Chessboard homework question. There a few modifications to support this effort.

To make it possible to see this algorithm in slow motion, I have created a "stepping" mechanism to let you see the algorithm in progress. This technique makes use of Threads and the wait/notify mechanisms discussed earlier in the semester(Remember the "bucket/producer/consumer" programs.

It's a little tricky, but it gives me a way to visually show this algorithm in slow motion.

whiteQueen.gif ... we need this image stored at the top level of your project

Game.java



import java.awt.Graphics;
import java.awt.Image;

import javax.swing.ImageIcon;

enum ColorType {black, white};
enum PieceType {Pawn, Rook, Knight, Bishop, Queen, King};

class Piece
{
    int xSquare, ySquare;
    PieceType pieceType;  // Not needed yet
    ColorType color;      // Not needed yet

    Piece (PieceType p, ColorType color, int xSquare, int ySquare)
    {
        this.pieceType=p;
        this.color = color;
        this.xSquare = xSquare;
        this.ySquare = ySquare;
    }
    void move(int x, int y)
    {
        xSquare =x;
        ySquare = y;
    }

     void drawInPosition(Graphics g, BoardDimensions b)
     {
         if (xSquare < 0 || ySquare < 0)
             return;
         ChessPiece chessPiece = ChessPiece.chessPieces[color.ordinal()][pieceType.ordinal()];
         int x = b.left+xSquare*b.square_width ;
         int y = b.top+ySquare*b.square_height;
         chessPiece.draw(g,x,y,b.square_width,b.square_height);
     }

}



public class Game {
    Piece[] pieces = new Piece[8];

    public void update (int[] m_position)
    {
        for (int i=0; i < m_position.length; i++)
        {
            pieces[i].move(m_position[i], i);
        }
    }


    Game()
    {
        // Fill in all the pieces and their locations
        int index=0;

        for (int i=0; i < 8; i++) // 8 white queens placed off the board
        {
            pieces[index++] = new Piece(PieceType.Queen, ColorType.white, -1, -1);
        }

    }

    void drawInPosition(Graphics g, BoardDimensions b)
    {
        for (int i=0; i < pieces.length; i++)
        {
            pieces[i].drawInPosition(g, b);
        }
    }

}

class ChessPiece
{
    static PieceType[] pieceType= PieceType.values();
    static ColorType[] colorType = ColorType.values();
    static ChessPiece[][]chessPieces = new ChessPiece[colorType.length][pieceType.length];
    static void readInImages()
    {
        for (int i=0; i < colorType.length; i++)
            for (int j=0; j < pieceType.length; j++)
                chessPieces[i][j] = new ChessPiece(i,j);
    }

    Image pieceImg ;
    int width, height;
    private Image loadImage(String fileName) {
            return new ImageIcon(fileName).getImage();
        }

    ChessPiece(int colorIndex, int pieceIndex)
    {
        String imageName =colorType[colorIndex].toString() +
                pieceType[pieceIndex].toString()+".gif";

        pieceImg = loadImage(imageName);
        width = pieceImg.getWidth(null);
        height = pieceImg.getHeight(null);
    }
    void draw(Graphics g, int x, int y, int wSpace, int hSpace)
    {
        double scale_width= (double)wSpace/width;
        double scale_height = (double)hSpace/height;

        double scale = Math.min(scale_width, scale_height);
        int newHeight = (int)(height*scale);
        int newWidth = (int)(width*scale);
        x = x + wSpace/2 - newWidth/2;
        y = y + hSpace/2 - newHeight/2;
        g.drawImage(pieceImg, x, y, newWidth, newHeight, null);
    }


}

class BoardDimensions
{
    int left=-1,  top=-1,  square_width=-1, square_height=-1;
    void setParms(int left, int top, int square_width, int square_height)
    {
        this.left = left;
        this.top = top;
        this.square_width = square_width;
        this.square_height = square_height;
    }
}



ChessBoard.java


import java.awt.*;
import java.awt.event.*;
import javax.swing.*;


public class ChessBoard extends JFrame implements Stepper, Runnable
{
    Queens queens;
    Game game= new Game();
    BoardDimensions boardDimensions = new BoardDimensions();
    boolean updateScreen = false;
    Dimension oldDimension = new Dimension();
    Image offScreenImage = null;
    Graphics offScreenGraphics = null;

    class Solver extends Thread
    {
        public void run()
        {
            queens.solve(true);
            //queens.solve_non_recursive(true);
        }
    }

    public synchronized void  step(int[] m_board)
    {
        game.update(m_board);
        try {
            wait();
        } catch (InterruptedException e) {}
        updateScreen=true;
    }
    public synchronized void singleStep()
    {
        notify(); // Wake up calls on step method
    }
    public void run()
    {
        while (true)
        {
            try {
                Thread.sleep(1000);
                singleStep();
                if (updateScreen)
                    repaint();
                updateScreen=false;
            } catch (InterruptedException e) {}
        }
    }


    ChessBoard(String name) {
        super(name);
        setSize(300, 400);
        ChessPiece.readInImages();
        boardDimensions = new BoardDimensions();
		
        queens = new Queens(8,  this);

        Solver solver = new Solver();
        solver.start();
        Thread t = new Thread(this);
        t.start();

        setVisible(true);
    }


    public void paint(Graphics screenGraphics) {

        Dimension d = getSize();
        if (!d.equals(oldDimension) || offScreenImage == null)
        {
            offScreenImage = createImage(d.width, d.height);
            oldDimension = d;
            offScreenGraphics = offScreenImage.getGraphics();
        }
        Graphics g = offScreenGraphics;
        g.setColor(Color.white);
        g.fillRect(0,0, d.width, d.height);
        Insets insets = super.getInsets();
        int top = insets.top;
        int left = insets.left;
        int w = (d.width-insets.left - insets.right)/8;
        int h = (d.height-top - insets.bottom)/8;
        boardDimensions.setParms(insets.left, top, w, h);

        for (int i=0; i < 8; i++)
        {
            for (int j=0; j < 8; j++)
            {
                int x = left+ j*w;
                int y = top + i*h;
                if ((i+j)%2==1)
                {
                    g.setColor(Color.green);
                    g.fillRect(x, y, w, h);
                }
                else
                {
                    g.setColor(Color.gray);
                    g.fillRect(x, y, w, h);
                }
            }
        }// end of outer for loop

        game.drawInPosition(g, boardDimensions);
        screenGraphics.drawImage(offScreenImage,  0, 0,  this);
    }


    public static void main(String[] args) {
        ChessBoard tryMe = new ChessBoard("The chessboard is the world, the chessPieces are the phenomena of the universe");
        //Quit program when window is closed
        tryMe.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    }
}


Last Updated: November 19, 2013 1:24 AM