gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

OffTopic > Eight queens effeciency

#19517 - TaleriaKNT - Wed Apr 21, 2004 6:05 am

I recently had to write a program to solve the eight queens problem for a CS class, and found that my implementation of it was much different (and more effecient) than what the rest of the class did, so I tried searching around on the internet a bit to try and compare various methods, but most of them seem the same, or very similar.

My question then is directed at others who have seen the eight queens problem : What is the most efficient algorithm you've seen?

#19526 - poslundc - Wed Apr 21, 2004 2:51 pm

http://en.wikipedia.org/wiki/Eight_queens_puzzle

Interesting stuff; I'd not heard of the eight queens puzzle before.

Dan.

#19550 - sajiimori - Wed Apr 21, 2004 7:48 pm

What was your algorithm?

#19551 - TaleriaKNT - Wed Apr 21, 2004 9:03 pm

Well, rather than try to describe it all over again, here's an excerpt from the readme file I had to turn in with it.
Code:
Essentially, I'm using a brute force method, but I'm cutting
down the number of possibilities by A LOT ahead of time. Since
we know that there can be only one queen in each row and column,
we can think of their positions, not as where there are queens
in a two dimentional array, but instead, as a list of the
locations that the queen is on in each row. If you consider a
board such as  Q------- to be represented as 12345678, and then
               -Q------
               --Q-----
               ---Q----
               ----Q---
               -----Q--
               ------Q-
               -------Q
consider the arrangement 12345678 as possibility #0, then each
permutation of this list could be derived from that. ie:
12345678=0, 87654321=40319(8!-1). My algorithm considers the
board to represented exactly that way, and since we can determine
that there are exactly 40320 possible permutations, we can just
generate the board pattern associated with each one and check if
the diagonals are safe (since by definition, we know that the
vertical and horizontal are).


The important code to the algorithm is as follows (written in Ada95). The array ListMultiplier is a list of factorials, where the first element is the highest factorial and the last element is zero.
Code:
  SubType BoardRange Is Integer Range 1..8;
  Type BoardType Is Array(BoardRange)Of BoardRange;
  SubType BoardPossibility Is Natural Range 0..40319; --There are 8!=40320 possibilities.
  ListMultiplier:Array(BoardRange)Of Natural;         --Array of factorials for later calculations.

  Procedure GeneratePossibility(Num:In BoardPossibility;Board:Out BoardType)Is
    Available:Array(BoardRange)Of Boolean:=(Others => True);
    Cutter,Traverser,Chosen:Natural;
    NumCopy:BoardPossibility;
  Begin
    NumCopy:=Num; --Because we need to change it, but Ada won't let you.
    For MainCount In BoardRange'First..BoardRange'Last Loop --Account for each list item...
      If MainCount<BoardRange'Last Then --We need to know how much to remove from NumCopy.
        Cutter:=NumCopy/ListMultiplier(MainCount);
      Else
        Cutter:=0; --Avoid Divide by 0.
      End If;
      NumCopy:=NumCopy-Cutter*ListMultiplier(MainCount); --This was divided and multiplied back on to
      Traverser:=0;                                      --remove the fractional part.
      Chosen:=1;
      While Traverser<(Cutter+1)Loop --Find which item should be next in the list by looking through
        If Available(Chosen)Then     --for an empty slot that is far enough to account for the inverse
          Traverser:=Traverser+1;    --factorial of Cutter.
        End If;
        If Traverser<(Cutter+1)Then
          Chosen:=Chosen+1;
        End If;
      End Loop;
      Available(Chosen):=False; --Set column Chosen to not be available in the rest of the passes.
      Board(MainCount):=Chosen; --Set row MainCount of the board to have a queen in column Chosen.
    End Loop;
  End;

This takes a number from 0..40319 and changes it into a board layout. The layouts created are always safe in the vertical and horizontal directions, so I only need to check the diagonals. When I looked around on the internet afterwards, I didn't see any examples that looked like this, so I started to wonder if anyone else has done it this way.

#19554 - Miked0801 - Wed Apr 21, 2004 9:28 pm

Funny, but this is pretty similiar to how I would have gone about it. Solve 2 of the 4 direction trivially, then work from there. Cool