8-Queens algorithm example?

Question

Anybody knows good/concise algorithm example for 8-queens? I googled and did not find any good example.

Answer 1

From Wikipedia:

This heuristic solves n queens for any n n ≥ 4 or n = 1:

1. Divide n by 12. Remember the remainder (n is 8 for the eight queens puzzle).
2. Write a list of the even numbers from 2 to n in order.
3. If the remainder is 3 or 9, move 2 to the end of the list.
4. Append the odd numbers from 1 to n in order, but, if the remainder is 8, switch pairs (i.e. 3, 1, 7, 5, 11, 9, …).
5. If the remainder is 2, switch the places of 1 and 3, then move 5 to the end of the list.
6. If the remainder is 3 or 9, move 1 and 3 to the end of the list.
7. Place the first-column queen in the row with the first number in the list, place the second-column queen in the row with the second number in the list, etc.

Answer 2

The point of the 8-queens problem is often just to illustrate the power of search combined with pruning. You can pretty much do a brute force search of the search space, but eliminate any partial solution when it violates the constraints of the solution (i.e. one queen checks another).

Just using this pruning, 8-queens is easily solvable.

If you want more efficient solutions that would be useful for e.g. 100 or 1000 queens, that's a different story and you can look at the stuff in wikipedia. But for 8-queens, brute force and pruning are enough. (i.e. do depth first search of the search space, eliminating any intermediate node that includes a queen in check).

Answer 3

to place queen on row r:

if r = 0 then you're done -- return ok
for each c [1 .. 8]:
  if (r,c) is safe:
    mark (r,c)
    if you can place queen on row r-1 then return ok
    unmark (r,c)  (if you're here, this c won't work)
return not ok     (if you're here, no c generated a solution)

(r,c) is safe if, for each row [r+1 .. 8]:

• (row,c) is not marked
• c - (row - r) < 1 or (row, c - (row - r)) is not marked
• c + (row - r) > 8 or (row, c + (row - r)) is not marked

Answer 4

try http://www.c-sharpcorner.com/UploadFile/prathore/EightQueensPuzzle01232009070910AM/EightQueensPuzzle.aspx

Answer 5

Here's a simple Java implementation of the naive recursive algorithm; it should be instructive.

public class NQueens {
    final static int N = 4;
    static int[] position = new int[N];

    public static void main(String[] args) {
        solve(0);
    }

    static boolean isSafe(int k, int p) {
//      for (int i = 1; i <= k; i++) {
//          int other = position[k - i];
//          if (other == p || other == p - i || other == p + i) {
//              return false;
//          }
//      }
        return true;
    }
    static void solve(int k) {
        if (k == N) {
            System.out.println(java.util.Arrays.toString(position));
        } else {
            for (char p = 0; p < N; p++) {
                if (isSafe(k, p)) {
                    position[k] = p;
                    solve(k+1);
                }
            }
        }
    }
}

Note that isSafe contains commented lines right now; it's done on purpose. With these lines commented, the program becomes a recursive N-tuple generator, where each value is between 0 (inclusive) and N (exclusive). That is, the program as is generates the following output:

[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 2]
[0, 0, 0, 3]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 0, 1, 2]
[0, 0, 1, 3]
:
:
[3, 3, 3, 0]
[3, 3, 3, 1]
[3, 3, 3, 2]
[3, 3, 3, 3]

This N-tuple generation is a concrete sub-problem of the NQueens problem. There are many questions already on stackoverflow on how to write an N-nested loops, when you don't know what N is. I feel that it's instructional to make a temporary stop at this problem and first understand its solution, with isSafe commented out to simply return true;, to first get a feel of what the recursion does.

Once you're comfortable that this recursive tuple generator works, simply uncomment those lines, and you will get a simple, naive, but working, NQueens solver. With N=5 and isSafe lines uncommented, the program now generates the following output:

[0, 2, 4, 1, 3]
[0, 3, 1, 4, 2]
[1, 3, 0, 2, 4]
[1, 4, 2, 0, 3]
[2, 0, 3, 1, 4]
[2, 4, 1, 3, 0]
[3, 0, 2, 4, 1]
[3, 1, 4, 2, 0]
[4, 1, 3, 0, 2]
[4, 2, 0, 3, 1]

Each line is a solution to the 5-queens problem. The i-th element of the array denotes the row position of the i-th queen placed on the i-th column (all indices are 0-based). So, the first solution looks like this on the board:

[0,2,4,1,3]

 Q · · · ·
 · · · Q ·
 · Q · · ·
 · · · · Q
 · · Q · ·

I will leave it as an exercise to understand why isSafe works, and how to print the board layout, and how to implement faster but more complicated recursive algorithms.

Happy learning.

Answer 6

Here is a simple C# Solution I think it works

public static class EightQueens
    {
        static   int[] board = new int[8];
        static int MaxRows = 8, MaxCols = 8;
        public static int[] GetPosition()
        {
            if (GetPosition(0)) return board;
            else return null;
        }
        public static bool IsCollision(int row, int col)
        {
            for (int i = 0; i < col; i++)
            {
                if (board[i] == row) return true; // Same Row
                if ((board[i] + col - i == row) || (board[i] - col + i == row))
                    return true;
            }
            return false;

        }
        public static bool GetPosition(int col)
        {
            if (col == MaxCols) return true;
            for (int row = 0; row < MaxRows; row++)
                if (!IsCollision(row, col))
                {
                    board[col] = row;
                    if (GetPosition(col + 1)) return true;
                }
            return false;

        }
    }

Answer 7

In EWD316, Dijkstra derives a solution to the Eight Queens problem rather formally. Try it, you might like it!

Answer 8

// Demonstration of the 8-Queens problem

// This handout shows interactively how the 8-Queens problem can be solved
// using recursion and backtracking (with exhaustive search with pruning).

// As far as this code goes, some improvements can definitely be made,
// especially with regard to the interface and the flexibility for the
// user.  However, it does an adequate job of showing the steps involved in
// solving the 8-Queens problem.

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

public class JRQueens extends JFrame implements Runnable
{
    public ChessSquare [][] squares;
    public boolean [] saferow;   // is the row empty?  true or false
    public boolean [] safeleftdiag; // is the left (from upper right to lower left)
    // diagonal unthreatened?  true or false
    public boolean [] saferightdiag; // is the right (from upper left to lower right)
    // diagonal unthreatened?  true or false

    private ShapePanel drawPanel; // panel for the board to be drawn -- see details
    // in class definition below
    private JLabel info;  // informative label
    private JButton runDemo; // button to allow interaction
    private Thread runThread; // thread to allow "motion"
    private int delay;   // delay between moves
    private PauseClass pauser; // class to allow execution to pause in between
    // solutions -- see details in definition below
    private boolean paused;  // is execution paused?  true or false
    private int sol, calls;

    public JRQueens(int delta)
    {
        super("Interactive 8 Queens Problem");
        delay = delta;
        drawPanel = new ShapePanel(450, 450);

        runDemo = new JButton("See Solutions");  // Set up button
        ButtonHandler bhandler = new ButtonHandler();
        runDemo.addActionListener(bhandler);

        info = new JLabel("The 8 Queens Problem", (int) CENTER_ALIGNMENT);

        Container c = getContentPane();   // Set up layout
        c.add(drawPanel, BorderLayout.CENTER);
        c.add(info, BorderLayout.NORTH);
        c.add(runDemo, BorderLayout.SOUTH);

        squares = new ChessSquare[8][8]; // initialize variables
        saferow = new boolean[8];
        safeleftdiag = new boolean[15];
        saferightdiag = new boolean[15];
        int size = 50;
        int offset = 25;
        for (int row = 0; row < 8; row++)
        {
            saferow[row] = true;  // all rows are safe
            for (int col = 0; col < 8; col++)
            {
                squares[row][col] = new ChessSquare(offset + col*size, 
                offset + row*size, 
                size, size);
            }
        }

        for (int i = 0; i < 15; i++)
        {                               // initialize all diagonals to safe
            safeleftdiag[i] = true;
            saferightdiag[i] = true;
        }
        sol = 0;
        calls = 0;

        runThread = null;

        setSize(475, 525);
        setVisible(true);
    }

    // Is the current location safe?  We check the row and both diagonals.
    // The column does not have to be checked since our algorithm proceeds in
    // a column by column manner.
    public boolean safe(int row, int col)
    {
        return (saferow[row] && safeleftdiag[row+col] &&
        saferightdiag[row-col+7]);
    }

    // This recursive method does most of the work to solve the problem.  Note
    // that it is called for each column tried in the board, but, due to
    // backtracking, will overall be called many many times.  Each call is from
    // the point of view of the current column, col.
    public void trycol(int col)
    {
        calls++; // increment number of calls made
        for (int row = 0; row < 8; row++)    // try all rows if necessary
        {
            // This test is what does the "pruning" of the execution tree --
            // if the location is not safe we do not bother to make a recursive
            // call from that position, saving overall many thousands of calls.
            // See notes from class for details.
            if (safe(row, col))
            {
                // if the current position is free from a threat, put a queen
                // there and mark the row and diags as unsafe
                saferow[row] = false;
                safeleftdiag[row+col] = false;
                saferightdiag[row-col+7] = false;
                (squares[row][col]).occupy();
                repaint();

                if (col == 7)      // queen safely on every column, announce
                {                  // solution and pause execution
                    sol++;
                    info.setText("Solution " + sol + " Found After " + calls + " Calls");
                    runDemo.setText("Click to Continue");
                    runDemo.setEnabled(true);
                    pauser.pause();
                }
                else
                {
                    // Still more columns left to fill, so delay a bit and then
                    // try the next column recursively
                    try
                    {
                        Thread.sleep(delay);
                    }
                    catch (InterruptedException e)
                    {
                        System.out.println("Thread error B");
                    }

                    trycol(col+1);  // try to put a queen onto the next column
                }

                saferow[row] = true;               // remove the queen from
                safeleftdiag[row+col] = true;      // the current row and
                saferightdiag[row-col+7] = true;   // unset the threats. The
                (squares[row][col]).remove();      // loop will then try the
                // next row down
            } 
        }
    // Once all rows have been tried, the method finishes, and execution
    // backtracks to the previous call.
    }

    // This method executes implicitly when the Thread is started.  Note that
    // its main activity is the call trycol(0), which starts the recursive
    // algorithm on its way.
    public void run()
    {
        paused = false;
        pauser = new PauseClass();
        trycol(0);
        repaint();
        info.setText("Program Completed: " + sol + " Solutions, "
        + calls + " Calls, "
        + (8*calls) + " iterations ");
    }

    public static void main(String [] args)
    {
        // Use the delay value entered by the user, or use 100 if no
        // value is entered.
        int delay;
        if (args != null && args.length >= 1)
        delay = Integer.parseInt(args[0]);
        else
        delay = 100;
        JRQueens win = new JRQueens(delay);

        win.addWindowListener(
            new WindowAdapter()
            {
                public void windowClosing(WindowEvent e)
                { System.exit(0); }
            }
        );
    }

    // This class is used to enable the execution to pause between
    // solutions.  The Java details of this class have to do with monitors
    // and synchronized Threads and are beyond the scope of the CS 1501
    // course.  However, if you are interested in learning more about these
    // Java features, feel free to look them up in the Java API.
    private class PauseClass
    {
        public synchronized void pause()
        {
            paused = true;
            try
            {
                wait();
            }
            catch (InterruptedException e)
            {
                System.out.println("Pause Problem");
            }
        }

        public synchronized void unpause()
        {
            paused = false;
            notify();
        }
    }

    // Class to handle button.  For more on the Java details, see
    // the API online.
    private class ButtonHandler implements ActionListener
    {
        public void actionPerformed(ActionEvent e)
        {
            if (e.getSource() == runDemo)
            {
                if (!paused)
                {
                    runDemo.setEnabled(false);
                    info.setText("Searching for Solutions");
                    runThread = new Thread(JRQueens.this);
                    runThread.start();
                }
                else
                {
                    runDemo.setEnabled(false);
                    info.setText("Searching for Solutions");
                    pauser.unpause();
                }
                repaint();
            }
        }
    }

    // Inner class to represent a square on the board.  This class extends
    // Rectangle2D.Double, which can be drawn graphically by the draw() method
    // of the Graphics2D class.  The main additions I have made in the subclass
    // are the occupied variable and the drawing of the Q if the space is
    // occupied.
    private class ChessSquare extends Rectangle2D.Double
    {
        private boolean occupied;

        public ChessSquare(double x1, double y1, double wid, double hei)
        {
            super(x1, y1, wid, hei);
            occupied = false;
        }

        public void draw(Graphics2D g2d)
        {
            g2d.draw(this);
            int x = (int) this.getX();
            int y = (int) this.getY();
            int sz = (int) this.getWidth();

            if (occupied)
            {
                g2d.setFont(new Font("Serif", Font.BOLD, 36));
                g2d.drawString("Q", x+10, y+sz-10);
            }
        }

        public void occupy()
        {
            occupied = true;
        }

        public void remove()
        {
            occupied = false;
        }

        public boolean isOccupied()
        {
            return occupied;
        }
    }

    // Class that allows the board to be rendered in a nice way.
    // See that Java API or a good book on Java graphics for more
    // details about this class.
    private class ShapePanel extends JPanel
    {
        private int prefwid, prefht;

        public ShapePanel (int pwid, int pht)
        {
            prefwid = pwid;
            prefht = pht;
        }

        public Dimension getPreferredSize()
        {
            return new Dimension(prefwid, prefht);
        }

        public void paintComponent (Graphics g)
        {
            super.paintComponent(g);
            Graphics2D g2d = (Graphics2D) g;
            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    (squares[i][j]).draw(g2d);
                }
            }    
        }
    }
}