Programming Challenge Problem - Eight Queens

[johndeaton]

Hello All,

I was recently looking for problems online to practice my code writing. I came across this problem, and I thought others may like to try it. Here is the question: where can you place eight queens on a chess board such that none of them can take any of the others. I'd like to see how others did it. Post your solutions. Here is what I did.

main.c

#include <stdio.h>
#include <stdlib.h>
#include "pos_func.h"

int main()
{
    queen_t queen_1, queen_2, queen_3, queen_4, queen_5, queen_6, queen_7, queen_8;
    int r1, r2, r3, r4, r5, r6, r7, r8, r9;
    bool_e stop = FALSE;
    srand(time(0));
    long int iterations = 0;
    while(!stop)
    {
        iterations++;
        if ((iterations%100000 == 0)) printf(".");
        do
        {
            r1 = rand()%65;
            r2 = rand()%65;
            r3 = rand()%65;
            r4 = rand()%65;
            r5 = rand()%65;
            r6 = rand()%65;
            r7 = rand()%65;
            r8 = rand()%65;
        } while (r1 == r2 || r1 == r3 || r1 == r4 || r1 == r5 || r1 == r6 || r1 == r7 || r1 == r8 ||
                 r2 == r3 || r2 == r4 || r2 == r5 || r2 == r6 || r2 == r7 || r2 == r8 ||
                 r3 == r4 || r3 == r5 || r3 == r6 || r3 == r7 || r3 == r8 ||
                 r4 == r5 || r4 == r6 || r4 == r7 || r4 == r8 ||
                 r5 == r6 || r5 == r7 || r5 == r8 || r6 == r7 || r6 == r8 || r7 == r8 ||
                 !r1 || !r2 || !r3 || !r4 || !r5 || !r6 || !r7 || !r8);
        find_position(&queen_1, r1);
        find_position(&queen_2, r2);
        find_position(&queen_3, r3);
        find_position(&queen_4, r4);
        find_position(&queen_5, r5);
        find_position(&queen_6, r6);
        find_position(&queen_7, r7);
        find_position(&queen_8, r8);
        if (!take_one(&queen_1, &queen_2) && !take_one(&queen_1, &queen_3) && !take_one(&queen_1, &queen_4) && !take_one(&queen_2, &queen_3) &&
            !take_one(&queen_2, &queen_4) && !take_one(&queen_3, &queen_4) && !take_one(&queen_5, &queen_1) && !take_one(&queen_5, &queen_2) &&
            !take_one(&queen_5, &queen_3) && !take_one(&queen_5, &queen_4) && !take_one(&queen_6, &queen_1) && !take_one(&queen_6, &queen_2) &&
            !take_one(&queen_6, &queen_3) && !take_one(&queen_6, &queen_4) && !take_one(&queen_6, &queen_5) && !take_one(&queen_7, &queen_1) &&
            !take_one(&queen_7, &queen_2) && !take_one(&queen_7, &queen_3) && !take_one(&queen_7, &queen_4) && !take_one(&queen_7, &queen_5) &&
            !take_one(&queen_7, &queen_6) && !take_one(&queen_8, &queen_1) && !take_one(&queen_8, &queen_2) && !take_one(&queen_8, &queen_3) &&
            !take_one(&queen_8, &queen_4) && !take_one(&queen_8, &queen_5) && !take_one(&queen_8, &queen_6) && !take_one(&queen_8, &queen_7))
        {
        stop = TRUE;
        printf("\nQueen 1 - Row %d - Column %d.\n",queen_1.row,queen_1.column);
        printf("Queen 2 - Row %d - Column %d.\n",queen_2.row,queen_2.column);
        printf("Queen 3 - Row %d - Column %d.\n",queen_3.row,queen_3.column);
        printf("Queen 4 - Row %d - Column %d.\n",queen_4.row,queen_4.column);
        printf("Queen 5 - Row %d - Column %d.\n",queen_5.row,queen_5.column);
        printf("Queen 6 - Row %d - Column %d.\n",queen_6.row,queen_6.column);
        printf("Queen 7 - Row %d - Column %d.\n",queen_7.row,queen_7.column);
        printf("Queen 8 - Row %d - Column %d.\n",queen_8.row,queen_8.column);
        printf("%d",iterations);
        }
    }
}

pos_func.h

ifndef _POS_FUNC_H_
#define _POS_FUNC_H_

typedef enum
{
    FALSE = 0,
    TRUE
} bool_e;

typedef struct
{
    unsigned char row;
    unsigned char column;
} queen_t;

extern void find_position(queen_t *queen, unsigned char pos_num);
extern bool_e same_row(queen_t *queen1, queen_t *queen2);
extern bool_e same_column(queen_t *queen1, queen_t *queen2);
extern bool_e same_diagonal(queen_t *queen1, queen_t *queen2);
extern bool_e take_one(queen_t *queen1, queen_t *queen2);

#endif // _POS_FUNC_H_

pos_func.c

#include "pos_func.h"

void find_position(queen_t *queen, unsigned char pos_num)
{
    if (!(pos_num % 8))
    {
        queen->row = (pos_num / 8);
        queen->column = 8;
    }
    else
    {
        queen->row = (pos_num / 8) + 1;
        queen->column = pos_num % 8;
    }
}

bool_e same_row(queen_t *queen1, queen_t *queen2)
{
    if (queen1->row == queen2->row) return TRUE;
    else return FALSE;
}

bool_e same_column(queen_t *queen1, queen_t *queen2)
{
    if (queen1->column == queen2->column) return TRUE;
    else return FALSE;
}

bool_e same_diagonal(queen_t *queen1, queen_t *queen2)
{
    if (queen1->column - queen2->column == queen1->row - queen2->row || queen2->column - queen1->column == queen2->row - queen1->row) return TRUE;
    else if (queen2->column - queen1->column == queen1->row - queen2->row || queen2->column - queen1->column == queen1->row - queen2->row) return TRUE;
    else return FALSE;
}

bool_e take_one(queen_t *queen1, queen_t *queen2)
{
    return (same_row(queen1,queen2) || same_column(queen1,queen2) || same_diagonal(queen1,queen2));
}

Enjoy!

[christop]

Does your solution actually solve the Eight Queens problem? As it randomly generates positions for all 8 queens, it appears to be astronomically unlikely to solve the problem before the death of our sun. It's like using the bogosort algorithm to sort a list containing 64 elements.

This also looks wrong:

r1 = rand()%65;

That will generate a value between 0 and 64, inclusive, which is 65 distinct values. A chessboard has only 64 squares.

Edit: I just tested it, and it solved the problem in about 110 million tries. Now that I think about it, the number of iterations won't be as large as I thought. It's really 64^8 iterations, not something like 2^64.

[johndeaton]

It works on my machine within 30 seconds. Try to compile it on yours and see if it works. I noticed that zero was included in that statement. That is why I added the !r1, !r2, ..., !r8 to the do while statement. Here is the output from the last execution.

[dmh2000]

one way to solve it is to simply generate all permutations and check them. ok i cheated and i used C++ to generate the permutations because that is so much easier. per Wikipedia there are 92 solutions. this generates all of them. i also imagine my 'check' function probably could be simplified.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>

int isValid(char board[8][8],int row,int col)
{
	int r;
	int c;

	// check for diagonal up right
	r = row+1;
	c = col+1;
	while((r<8)&&(c<8)) {
		if (board[r][c] == 'X') {
			return 0;
		}
		r++;
		c++;
	}
	// check for diagonal up left
	r = row+1;
	c = col-1;
	while((r<8)&&(c>=0)) {
		if (board[r][c] =='X') {
			return 0;
		}
		r++;
		c--;
	}

	// check for diagonal down right
	r = row-1;
	c = col+1;
	while((r>=0)&&(c<8)) {
		if (board[r][c] == 'X') {
			return 0;
		}
		r--;
		c++;
	}
	// check for diagonal down left
	r = row-1;
	c = col-1;
	while((r>=0)&&(c>=0)) {
		if (board[r][c] == 'X') {
			return 0;
		}
		r--;
		c--;
	}

	board[row][col] = 'X';
	
	return 1;
}

int check(int cols[8],char board[8][8]) 
{
	int c;
	int r;
	memset(board,' ',sizeof(char) * 8 * 8);
	for(r=0;r<8;++r) {
		c = cols[r];
		if (!isValid(board,r,c)) {
			return 0;
		}
	}
	return 1;
}

int main(int argc,char *argv[])
{
	bool b;
	int result;

	unsigned long long count;
	int cols[8] = {0,1,2,3,4,5,6,7};
	char board[8][8];

	count = 0;
	for(;;) {
		b = std::next_permutation(cols,cols+8);
		if (b == false) break;

		result = check(cols,board);
		if (result != 0) {
			++count;
		}
	}
	printf("%llu\n",count);
	return 0;
}

[Nominal Animal]

Here's the approach I'd use. It's pretty much unoptimized, but as it finds the 92 solutions in under two seconds on my machine (Athlon II X4 640 3GHz). I did not verify each and every one of the solutions, but they look like the right ones at a quick glance.

#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <errno.h>
#include <stdio.h>

/* The chess board and the queens are described using
 * a single uint64_t variable, with a nonzero bit describing
 * a queen, and a zero bit describing a vacant square.
 *
 * Chess square A1 = bit 0 = row 0, col 0.
 * Chess square A8 = bit 7 = row 0, col 7.
 * Chess square H1 = bit 56 = row 7, col 0.
 * Chess square H8 = bit 63 = row 7, col 7.
 *
 *  8   56 57 58 59 60 61 62 63
 *  7   48 49 50 51 52 53 54 55
 *  6   40 41 42 43 44 45 46 47
 *  5   32 33 34 35 36 37 38 39
 *  4   24 25 26 27 28 29 30 31
 *  3   16 17 18 19 20 21 22 23
 *  2    8  9 10 11 12 13 14 15
 *  1    0  1  2  3  4  5  6  7
 *
 *       A  B  C  D  E  F  G  H
*/

#define QUEEN(row,col) ( ((uint64_t)1) << ((row) * 8 + (col)) )

/* A bit mask of squares that are affected when a queen is placed at index.
*/
static uint64_t affected[8][8];

/* Known solutions:
*/
static size_t    solutions_max = 0;
static size_t    solutions     = 0;
static uint64_t *solution      = NULL;

/* Add a new solution.
 * TODO: Keep solutions sorted, and do a binary search instead.
*/
static inline int add_solution(const uint64_t board)
{
    /* Is there room for a new solution? */
    if (solutions >= solutions_max) {
        const size_t    max = (solutions | (size_t)1023) + 1025;
        const size_t    bytes = max * sizeof (uint64_t);
        uint64_t       *tmp;

        /* Overflow? */
        if (max < solutions || bytes / sizeof (uint64_t) != max)
            return ENOMEM;

        tmp = realloc(solution, bytes);
        if (!tmp)
            return ENOMEM;

        solutions_max = max;
        solution = tmp;
    }

    /* Already known? */
    {   const uint64_t       *head = solution;
        const uint64_t *const tail = solution + solutions;

        while (head < tail)
            if (*(head++) == board)
                return EEXIST;
    }

    /* Append. */
    solution[solutions++] = board;
    return 0;
}        

/* Recursive function to place a new queens onto the
 * specified chess board.
*/
static int place_queens(const uint64_t board, int queens)
{
    int row, col, result;

    /* Is this a final solution? No more queens to place? */
    if (queens < 1) {
        result = add_solution(board);
        if (result == EEXIST)
            return 0;
        else
            return result;
    }

    /* Try placing a queen on each vacant spot on the board.
     * We can only place a new queen on an empty square,
     * if it will not affect the existing queens.
    */
    for (row = 0; row < 8; row++)
        for (col = 0; col < 8; col++)
            if (!(board & affected[row][col])) {
                result = place_queens(board | QUEEN(row, col), queens - 1);
                if (result)
                    return result;
            }

    return 0;
}

int main(void)
{
    int     result, row, col;
    size_t  i;

    /* Construct the bit masks corresponding to Queen reaches.
     * TODO: This is inefficient, and should be optimized.
    */
    {   int r, c;

        for (row = 0; row < 8; row++)
            for (col = 0; col < 8; col++) {
                uint64_t  reach = 0;

                for (r = 0; r < 8; r++) reach |= QUEEN(r, col);
                for (c = 0; c < 8; c++) reach |= QUEEN(row, c);

                r = row; c = col; while (r-- > 0 && c-- > 0) reach |= QUEEN(r, c);
                r = row; c = col; while (r++ < 7 && c-- > 0) reach |= QUEEN(r, c);
                r = row; c = col; while (r-- > 0 && c++ < 7) reach |= QUEEN(r, c);
                r = row; c = col; while (r++ < 7 && c++ < 7) reach |= QUEEN(r, c);

                affected[row][col] = reach;
            }
    }

    result = place_queens(0, 8);
    switch (result) {

    case 0:
        /* No error */
        break;

    case ENOMEM:
        fprintf(stderr, "Out of memory: too many solutions found (%lu).\n", (unsigned long)solutions);
        return 1;

    default:
        /* All other errors are unexpected, but report them anyway. */
        fprintf(stderr, "%s.\n", strerror(errno));
        return 1;
    }

    printf("Found %lu solutions:\n\n", (unsigned long)solutions);

    for (i = 0; i < solutions; i++) {
        printf("Solution %lu, 0x%08lx%08lx:\n", (unsigned long)i + 1UL,
                 (unsigned long)(solution[i] >> 32) & 0xFFFFFFFFUL,
                 (unsigned long)(solution[i] & 0xFFFFFFFFUL));

        fputs("\t\t    A B C D E F G H\n\n", stdout);
        for (row = 0; row < 8; row++) {
            printf("\t\t%d  ", 8 - row);

            for (col = 0; col < 8; col++)
                if (solution[i] & QUEEN(row, col))
                    fputs(" Q", stdout);
                else
                    fputs(" .", stdout);

            fputs("\n", stdout);
        }

        fputs("\n\n", stdout);
    }

    return 0;
}

I recommend compiling it with

gcc file.c -std=c99 -Wall -pedantic -O3 -fomit-frame-pointer -o binary

on x86 and x86-64 in Linux. The code itself is C99, and should compile on all architectures.

The idea is that since there are only two states for each square -- empty or Queen -- you can use a single uint64_t to represent the entire board state.

The affected[row][col] array contains the pattern of squares reachable ("affected") by a Queen placed at row row, column col. A new Queen can only be placed on the board if it cannot reach any of the existing queens; i.e. if board & affected[rowcol] is zero.

Each Queen is placed by a recursive function, place_queens(board, queens). It will try each possible position, recursing whenever the placement is successful.

[oogabooga]

This is about as simple as I can make it.

#include <stdio.h>
#include <stdlib.h>

#define SIZE 8

void print_board(int b[][SIZE]) {
    int x, y;
    for (y = 0; y < SIZE; y++) {
        for (x = 0; x < SIZE; x++)
            printf("%d ", b[x][y]);
        putchar('\n');
    }
}

int legal_move(int b[][SIZE], int row, int col) {
    int r;
    for (r = 0; r <= row; r++)
        if (b[col][r] ||
            (col-(row-r) >= 0    && b[col-(row-r)][r]) ||
            (col+(row-r) <  SIZE && b[col+(row-r)][r]))
            return 0;
    return 1;
}

void place_queen(int b[][SIZE], int row) {
    if (row == SIZE) { // solution
        print_board(b);
        exit(0);
    } else {
        int col;
        for (col = 0; col < SIZE; col++)
            if (legal_move(b, row, col)) {
                b[col][row] = 1;
                place_queen(b, row + 1);
                b[col][row] = 0;
            }
    }
}

int main(void) {
    int b[SIZE][SIZE] = {{0}};
    place_queen(b, 0); // start placing queens at row 0
    return 0;
}

[itsme86]

Here's a C# attempt. It only finds one solution, but it doesn't cheat at all except to assume that there will only be 1 queen in each row.

    class Program
    {
        static void Main(string[] args)
        {
            double[] times = new double[10];

            for (int run = 0; run < times.Length; ++run)
            {

                System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
                sw.Start();

                Board board = new Board();

                uint moves = 0;

                while (!board.QueensAreSafe())
                {
                    Queen queenToMove = null;
                    for (int i = 7; i >= 0; --i)
                    {
                        Queen queen = board.Queens[i];
                        if (queen.X < 7)
                        {
                            queenToMove = queen;
                            break;
                        }
                    }
                    if (queenToMove == null)
                    {
                        Console.WriteLine("No solution.");
                        return;
                    }

                    queenToMove.X++;
                    moves++;

                    for (int i = queenToMove.ID + 1; i < 8; ++i)
                        board.Queens[i].X = 0;
                }

                sw.Stop();
                times[run] = sw.Elapsed.TotalSeconds;

                Console.WriteLine("Run #{0}: Solution in {1} moves, {2} seconds:", run + 1, moves.ToString("#,0"), times[run]);
                StringBuilder sb = new StringBuilder("  ");
                foreach (Queen queen in board.Queens)
                    sb.AppendFormat(" ({0},{1})", queen.X, queen.Y);
                sb.AppendLine();
                Console.WriteLine(sb.ToString());
            }

            Console.WriteLine("Average run length: {0} seconds.", times.Sum() / times.Length);
        }
    }

    public class Board
    {
        public Queen[] Queens { get; private set; }

        public Board()
        {
            Queens = new Queen[8];

            for (int i = 0; i < 8; ++i)
                Queens[i] = new Queen(i, 0, i);
        }

        public bool QueensAreSafe()
        {
            for (int i = 0; i < 7; ++i)
                if (Queens[i].CanTakeAQueen(Queens, i + 1))
                    return false;

            return true;
        }
    }

    public class Queen
    {
        public int ID { get; private set; }
        public int X { get; set; }
        public int Y { get; set; }

        public Queen(int id, int x, int y)
        {
            ID = id;
            X = x;
            Y = y;
        }

        public bool CanTakeAQueen(Queen[] queens, int startIndex)
        {
            for (int i = startIndex; i < 8; ++i)
            {
                Queen q = queens[i];
                if (q.X == X || q.Y == Y || Math.Abs(q.X - X) == Math.Abs(q.Y - Y))
                    return true;
            }

            return false;
        }
    }

And here are my result times:

Run #1: Solution in 1,299,851 moves, 0.0349848 seconds:
   (0,0) (4,1) (7,2) (5,3) (2,4) (6,5) (1,6) (3,7)

Run #2: Solution in 1,299,851 moves, 0.0327236 seconds:
   (0,0) (4,1) (7,2) (5,3) (2,4) (6,5) (1,6) (3,7)

Run #3: Solution in 1,299,851 moves, 0.0328079 seconds:
   (0,0) (4,1) (7,2) (5,3) (2,4) (6,5) (1,6) (3,7)

Run #4: Solution in 1,299,851 moves, 0.0371899 seconds:
   (0,0) (4,1) (7,2) (5,3) (2,4) (6,5) (1,6) (3,7)

Run #5: Solution in 1,299,851 moves, 0.0339623 seconds:
   (0,0) (4,1) (7,2) (5,3) (2,4) (6,5) (1,6) (3,7)

Run #6: Solution in 1,299,851 moves, 0.0327008 seconds:
   (0,0) (4,1) (7,2) (5,3) (2,4) (6,5) (1,6) (3,7)

Run #7: Solution in 1,299,851 moves, 0.0345848 seconds:
   (0,0) (4,1) (7,2) (5,3) (2,4) (6,5) (1,6) (3,7)

Run #8: Solution in 1,299,851 moves, 0.033962 seconds:
   (0,0) (4,1) (7,2) (5,3) (2,4) (6,5) (1,6) (3,7)

Run #9: Solution in 1,299,851 moves, 0.033191 seconds:
   (0,0) (4,1) (7,2) (5,3) (2,4) (6,5) (1,6) (3,7)

Run #10: Solution in 1,299,851 moves, 0.0347766 seconds:
   (0,0) (4,1) (7,2) (5,3) (2,4) (6,5) (1,6) (3,7)

Average run length: 0.03408837 seconds.
Press any key to continue . . .

[Nominal Animal]

Here's a C# attempt. It only finds one solution, but it doesn't cheat at all except to assume that there will only be 1 queen in each row.

It is not really a solution if it only finds one out of the 92. In particular, showing how fast you can find one solution is misleading; it is definitely not comparable in any way to any of the other running times mentioned above.

Why don't you fix your program so it returns all possible combinations?

My solution does not cheat in any way at all either, and it finds all possible solutions in under two seconds. You will find that your program will find a lot of duplicates; i.e. many initial conditions produce the exact same result; your running time will definitely not be 92*0.03 seconds. The duplicates occur naturally, because you can place the Queens in any order, and still end up with the exact same configuration.

Just for fun, I modified my algorithm to place horses instead of Queens. Since there are a lot more pieces that can be placed, finding the configurations is much slower. I'm still running the program looking for solutions, but right now it's already found four configurations for twenty-five horses not threatened by each other, and 200 configurations for twenty-four horses. If I don't get bored first, I'll report my findings later on.

Edited to add: D'oh. You can obviously place 32 horses on the chess board, in two configurations: all on black, or all on white squares. Still, my approach seems quite acceptable. In particular, changing it to another piece (different movement pattern) was trivial.

[itsme86]

It is not really a solution if it only finds one out of the 92. In particular, showing how fast you can find one solution is misleading; it is definitely not comparable in any way to any of the other running times mentioned above.

Really? Check the OP's post and the 3 posts following it. You were actually the second person to deviate from the OP's challenge by finding all 92 combinations. I guess that means my running time is no more misleading than the OP's, doesn't it? Hmm.

Try again.

[Nominal Animal]

deviate from the OP's challenge by finding all 92 combinations. I guess that means my running time is no more misleading than the OP's, doesn't it?

Correct. The solution OP posted is only a partial answer to the puzzle, and so is yours.

You assume that showing one combination is a solution to the question "Where can you place eight queens on a chess board such that none of them can take any of the others?". It is not. The answer to that question is the full set of solutions. A single combination is only a partial answer, similar to "for example, like thus".

A single combination only fully answers the question "Can you place eight queens on a chess board such that none of them can take any of the others?".

Remember, these are logic puzzles. Use logic, don't just follow whatever errors the OP happens to make.

[laserlight]

You assume that showing one combination is a solution to the question "Where can you place eight queens on a chess board such that none of them can take any of the others?". It is not.

Actually, it is a solution, by definition

To avoid ambiguity, there should have been a follow up: "Show one such position." or "Show all the (distinct?) positions."