

Solve the eight queens puzzle.



You can extend the problem to solve the puzzle with a board of size   NxN.

For the number of solutions for small values of   N,   see   OEIS: A000170.



Related tasks

 A* search algorithm
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Knight's tour
 Peaceful chess queen armies
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


module NQueens {
    inherits {
        Heron.Windows.Console;
    }
    fields {
        n : Int = 4;
        sols : List = new List();
    }
    methods {
        PosToString(row : Int, col : Int) : String {
            return "row " + row.ToString() + ", col " + col.ToString();
        }
        AddQueen(b : Board, row : Int, col : Int)
        {
            if (!b.TryAddQueen(row, col))
                return;            
            if (row < n - 1)
                foreach (i in 0..n-1)
                   AddQueen(new Board(b), row + 1, i);
            else
                sols.Add(b);
        }        
        Main() {
            foreach (i in 0..n-1)
                AddQueen(new Board(), 0, i);
            foreach (b in sols) {
                b.Output();
                WriteLine("");
            }
            WriteLine("Found " + sols.Count().ToString() + " solutions");
        }
    }
}
 
class Board {
    fields {
        rows = new List();
    }
    methods {
        Constructor() {
            foreach (r in 0..n-1) {
                var col = new List();
                foreach (c in 0..n-1)
                    col.Add(false);
                rows.Add(col);
            }
        }
        Constructor(b : Board) {
            Constructor();
            foreach (r in 0..n-1)
                foreach (c in 0..n-1)
                    SetSpaceOccupied(r, c, b.SpaceOccupied(r, c));
        }
        SpaceOccupied(row : Int, col : Int) : Bool {
            return rows[row][col];
        }
        SetSpaceOccupied(row : Int, col : Int, b : Bool)  {
            rows[row][col] = b;
        }
        ValidPos(row : Int, col : Int) : Bool {
            return ((row >= 0) && (row < n)) && ((col >= 0) && (col < n)); 
        }
        VectorOccupied(row : Int, col : Int, rowDir : Int, colDir : Int) : Bool {
            var nextRow = row + rowDir;
            var nextCol = col + colDir;
            if (!ValidPos(nextRow, nextCol)) 
                return false;
            if (SpaceOccupied(nextRow, nextCol)) 
                return true;
            return VectorOccupied(nextRow, nextCol, rowDir, colDir);
        }
        TryAddQueen(row : Int, col : Int) : Bool {
            foreach (rowDir in -1..1)
                foreach (colDir in -1..1)
                    if (rowDir != 0 || colDir != 0)
                        if (VectorOccupied(row, col, rowDir, colDir))
                            return false;
            SetSpaceOccupied(row, col, true);
            return true;
        }
        Output() {
            foreach (row in 0..n-1) {
                foreach (col in 0..n-1) {
                    if (SpaceOccupied(row, col)) {
                        Write("Q");
                    }
                    else {
                        Write(".");
                    }
                }
                WriteLine("");
            }
        }
    }
}