# Robson » Little Red Book » Eight Queens

## Chapter 9 - Question 5

The chess board and pieces are a source of many intriguing problems. One such is:

Eight queens are to be placed on a chess board in such a way that no queen could capture any of the others.

### Solution 1

I'm going to work this out by feeding some simple rules into a script and then making the script do the hard work.

Horizontal matching is sorted by only placing one queen on each row.

Vertical matching is sorted by taking any array of the values 0 to 7 and shuffling it, then placing the queen for each row on the corresponding square across.

So all solutions generated will be fine horizontal and vertical. This means the actual work is taken up by generating solutions until one works for diagonals as well.

PHP:

`<?`
`    // all queens must be on a different vertical line`
`    \$pos = array(0, 1, 2, 3, 4, 5, 6, 7);`
`    `
`    // loop at least once`
`    do`
`    {`
`        // use a random order each time`
`        shuffle(\$pos);`
`    `
`        // loop through each row`
`        for (\$n = 0; \$n < 8; \$n++)`
`        {`
`            // write empty squares across`
`            \$board[\$n] = array_fill(0, 8, 0);`
`            // place a queen in one square`
`            // this takes care of horizontal matching`
`            \$board[\$n][\$pos[\$n]] = 1;`
`        }`
`        `
`        // reset the invalid variable`
`        \$invalid = false;`
`        // loop through each row`
`        for (\$a = 0; \$a < 8 && !\$invalid; \$a++)`
`        {`
`            // loop through each potential column`
`            for (\$b = 0; \$b < 12 && !\$invalid; \$b++)`
`            {`
`                // determine the difference between each row`
`                // this is then used to calculate the position of all the potential hits`
`                \$diff = (\$b - \$a) + 1;`
`                // check the diagonal rule`
`                \$invalid = `
`                    // check it's inside the board and not the same square`
`                    \$a-\$diff >= 0 && \$a-\$diff <= 7 && \$diff &&`
`                    (`
`                        // check if the square is inside the board`
`                        // and check if it's occupied`
`                        (\$pos[\$a]-\$diff >= 0 && \$pos[\$a]-\$diff < 8 && \$board[\$a-\$diff][\$pos[\$a]-\$diff] == 1)`
`                        ||`
`                        (\$pos[\$a]+\$diff >= 0 && \$pos[\$a]+\$diff < 8 && \$board[\$a-\$diff][\$pos[\$a]+\$diff] == 1)`
`                    );`
`            }`
`        }`
`        // increment the attempts`
`        \$counter++;`
`    }`
`    // loop until a valid solution is found`
`    // or until too many attempts have been made`
`    while (\$invalid && \$counter < 1000);`
` `
`    // check if the loop terminated because it took too long`
`    if (\$invalid)`
`        // just fail with a message`
`        echo 'The script has stopped early because a solution was not found in time. '`
`           . 'Try refreshing this page to find a solution.';`
`    else`
`    {    `
`        // output the board`
`        for (\$n = 0; \$n < 8; \$n++)`
`            // show the empty and filled squares`
`            echo implode('', \$board[\$n]) . '<br/>';`
`            `
`        // show how many tries it took to find a solution`
`        echo 'Attempts: ' . \$counter . '.';`
`    }`
`?>`

Which produces:

00100000
00000100
00010000
10000000
00000001
00001000
00000010
01000000
Attempts: 173.

## Log

• November 9, 2005 - Added solution 1.
© 2004-19 robson | cc unless stated