Triangular N Queens Problem

[justinsbabe5000]

I have the following code:

import javax.swing.*;
import java.util.*;
import java.awt.*;
import java.util.List;

public class Main
{

    // This is a list of all possible positions on the
    // triangular N-queens. Positions are 1-based.
    static List<Position> boardPositions;
    public static void main(String[] args)
    {
       String input = JOptionPane.showInputDialog(null,
                   "Triangular Queens: Enter a positive integer", "6" );
       int n = Integer.parseInt(input.trim());

       boardPositions = getBoardPositions(n);
       Stack<Position> partialSol = new Stack<Position>();
       System.out.println("Size of maximal placement is " + (2*n + 1)/3);
       extendQueensPlacement(partialSol, 0, n);

       System.out.println("Size of solution is " + partialSol.size());
       for (Position p : partialSol)
           System.out.print(p + "   ");
       Board queensDisplay = new Board(n, partialSol);
       JOptionPane.showMessageDialog(null, queensDisplay, "Triangular N Queens",
               JOptionPane.INFORMATION_MESSAGE);
    }
    /**
     *
     * @param partialSol
     * @param k the index of the boardPosition we are about to try to include
     * in partialSol. This is an index into the static class member boardPositions
     * whick is a List of Position objects.
     * @param n
     * @return true if the partial solution is successfully extended to a
     * complete solution, and returns false otherwise. If the false is returned, then
     * the partial solution with the same value it had at the call.
     */
    public static boolean extendQueensPlacement(Stack<Position> partialSol,
                                                int k, int n)
    {
        if(isComplete(partialSol, n))
            return true;

        for(k = 0; k < boardPositions.size(); k++)
        {
            if(!attacks(boardPositions.get(k), partialSol))
                partialSol.add(boardPositions.get(k));
        }

        return false;
    }

    /**
     * Checks to see if a partial solution is a complete solution.
     * @param partialSolution
     * @param n The size of the board.
     * @return true or false as appropriate
     */
    static boolean isComplete(Stack<Position> partialSolution, int n)
    {
        return partialSolution.size() == (2*n + 1)/3;
    }

    /**
     * Check to see if two position attack each other
     * @param p A position on the board (1-based)
     * @param q A position on the board (1-based)
     * @return true if they attack each other, false otherwise.
     */
    static boolean attacks(Position p, Position q)
    {
        return p.row == q.row || p.col == q.col || p.row - p.col == q.row - q.col;
    }

    /**
     * Checks to see a position attacks and position in a given list of
     * positions.
     * @param p a single position
     * @param posList a list of positions
     * @return true if p attacks at least one position in posList
     */
    static boolean attacks(Position p, List<Position> posList)
    {
        for (Position pos : posList)
        {
            if (attacks(p, pos)) return true;
        }
        return false;
    }
    /**
     * This method may not be needed. It removes from posList all positions
     * that attack pos. It returns the list of positions removed in this manner.
     * @param pos
     * @param posList
     * @return a list of all positions in posList, OTHER THAN pos, that attack
     * pos.
     */
    static List<Position> removeAttackers(Position pos, List<Position> posList)
    {
        List<Position> attackers = new ArrayList<Position>();
        for (int k = 0; k < posList.size(); )
        {
            Position p = posList.get(k);
            if (attacks(pos, p))
            {
                posList.remove(p);
                if (p != pos) attackers.add(p);
            }
            else k++;
        }
        return attackers;
    }
    /**
     * Used to generate the list of 1-based triangular board positions.
     * 1, 1 through n, n
     * @param n
     * @return list of triangular board positions.
     */
    static List<Position> getBoardPositions(int n)
    {
        List<Position> boardPosition = new ArrayList<Position>();
        for (int row = 1; row <= n; row ++)
            for (int col = 1; col <= row; col++)
                boardPosition.add(new Position(row, col));
        return boardPosition;
    }

    /** Used for debugging
     * Prints all Positions in a list
     * @param posList
     */
    static void println(List<Position>posList)
    {
        for (Position p : posList)
            System.out.print(p + " ");
        System.out.println();
    }
}

/**
 * A position indicating on the board for the triangular
 * N queens problem.
 * @author gcm
 */
class Position
{
    public final int row, col;
    public Position(int row, int col)
    {
        this.row = row; 
        this.col = col;
    }
    public String toString()
    {
        return "[" + row + "," + col + "]";        
    }
}

// A Graphical view of the triangular board with the queens placed.
// The constructor takes a list of queen positions and a board size
// and creates a JPanel neatly showing the placement of the queens.
class Board extends JPanel
{
    private int n; // size of board
    Board(int n, List<Position> placements)
    {
        super(new GridLayout(n, 2*n-1));
        this.n = n;
        // create the labels to diplay the placements
        JTextField labels [][] = new JTextField[n][2*n-1];
        for (int row = 0; row < n; row++)
            for (int col = 0; col < 2*n-1; col++)
            {
                labels[row][col] = new JTextField(" ");               
                add(labels[row][col]);
                labels[row][col].setEditable(false);
            }

        for (int r = 0; r < n; r++)
        {
            int startCol = n-1-r;
            for (int k = 0; k < r+1; k++)
            {
                labels[r][startCol + 2*k].setBackground(Color.YELLOW);
            }
        }
        // place the queens
        for (Position p : placements)
        {
            int r = p.row-1;
            int c = p.col-1;
            //labels[r][c].setForeground(Color.RED);
            //labels[r][c].setText("Q");
            labels[r][n-1 -r + 2*c].setForeground(Color.RED);
            labels[r][n-1 -r + 2*c].setText("Q");
            labels[r][n-1 -r + 2*c].setToolTipText(p.toString());

        }
    }

}

What I can't figure out how to do is the public static boolean extendQueensPlacement(Stack<Position> partialSol, int k, int n) method. I check to see if it is a complete solution and if it is I return true and if it is not a complete solution then I go through each board position and add to partialSol if it does not attack any position in partialSol.

Now what I can't figure out how to do is when all board positions have been checked and partialSol is not a complete solution so backtrack and try another boardPosition. Not really sure how to do the backtracking.

[justinsbabe5000]

I've written the following code for the public static boolean extendQueensPlacement(Stack<Position> partialSol, int k, int n) method. It seems to be working for any even number size (n) but when the size (n) is odd it doesn't work. I tested when n is 5 and it worked but when n is 7 the solution size is 3 but should be 5 and when n is 9 the solution size is 4 when it should be 6. Not sure how to fix this for odd number size (n).

public static boolean extendQueensPlacement(Stack<Position> partialSol,
                                                              int k, int n)
 {
       // to hold the position of the removed queen (position)
       // used to find the the index in boardPositions that
       // equals this position
       Stack<Position> tempPosition = new Stack<Position>();
        
        // if a complete solution return true
        if(isComplete(partialSol, n))
                return true;
        
        // add the first position to partialSol
        partialSol.add(boardPositions.get(0));

        // for each board position
        for(k = 1; k < boardPositions.size(); k++)
        {
            // if it is a valid position add to partialSol
            if(!attacks(boardPositions.get(k), partialSol))
            {
                partialSol.add(boardPositions.get(k));
            }

            // if k is equal to size of boardPositions - 1
            // and it is not a complete solution
            if(k == boardPositions.size() - 1 && !isComplete(partialSol, n))
            {
                // add the last element in partialSol to tempPosition
                // set k to be the index of boardPosition after the index that
                // equals the position in tempPosition
                // remove the last element from partialSol
                tempPosition.add(partialSol.get(partialSol.size() - 1));
                k = boardPositions.indexOf(tempPosition.pop()) + 1;
                partialSol.remove(partialSol.size() - 1);
            }
        }

        // if not a complete solution return false
        return false;
    }

How do I modify this to work for odd numbered sizes?