Method 3 - Hard code!
Method 1: Be lazy and use brute force.
Constrain the starting board positions to only those with 1 queen per each row and column.
Slow but workable for 8x8 boards.
Method 1 Test run: 3 runs, each run testing up to 1000 permutations.
Time: 0.0058 seconds
Results: 2 unique solutions found. (Click to view on chess board)
{ a4:'wQ', b2:'wQ', c8:'wQ', d5:'wQ', e7:'wQ', f1:'wQ', g3:'wQ', h6:'wQ' }{ a8:'wQ', b4:'wQ', c1:'wQ', d3:'wQ', e6:'wQ', f2:'wQ', g7:'wQ', h5:'wQ' }
Method 1: PHP Code:
<?php
/////////////////////////////////////////////////////////////////////
// Solve 8 Queens Puzzle
// Use brute force, with queens randomly placed 1 per row/column
// modified from https://gist.github.com/Xeoncross/1015646
// modified from http://paulbutler.org/archives/n-queens-in-a-tweet/
//
function solve8queens( $n=8, $attempts=1000 ) {
$i = 0;
$s = range(1,$n); // init the chess board
while( $i <= $attempts ) {
shuffle($s); // randomly place 1 queen per row/column
$a = s($s,range(1,$n)); // test for attacks on rows/columns - permutations [1..n]
$b = s(s($s,range($n,1)),2*$n); // test for attacks on diagonals - permutations [n..1] with constant factor 2*n
$c = array_merge($a,$b); // combine row/col and diagonals checks.
if( count(array_unique($c))==2*$n ) { // if there are 2*n numbers in the array, then solution is found
// output in chessboad.js/JSON format, for 8x8 board:
$s[0] = 'a' . $s[0]; $s[1] = 'b' . $s[1]; $s[2] = 'c' . $s[2]; $s[3] = 'd' . $s[3];
$s[4] = 'e' . $s[4]; $s[5] = 'f' . $s[5]; $s[6] = 'g' . $s[6]; $s[7] = 'h' . $s[7];
$solution = join(":'wQ', ",$s);
return "{ $solution:'wQ' }" ;
}
$i++;
}
} // end function solve8queens
// add two arrays of numbers together
function s($a,$b){
if( !is_array($b) ) { $b = array_fill(0,count($a),$b); } // no second array? make one with all 0's
foreach( $a as $i=>$k ) { $r[$i] = $k + $b[$i]; }
return $r;
}
Method 2: Find all solutions, using bitwise math for board checks,
first finds the 12 fundamental solutions, then the 92 based on rotations/reflections.
Method 2 Test run:
Time: 0.0281 seconds
Results: 92 unique solutions found. (Click to view on chess board)
{ a1:'wQ', e2:'wQ', h3:'wQ', f4:'wQ', c5:'wQ', g6:'wQ', b7:'wQ', d8:'wQ' }{ a1:'wQ', f2:'wQ', h3:'wQ', c4:'wQ', g5:'wQ', d6:'wQ', b7:'wQ', e8:'wQ' }{ a1:'wQ', g2:'wQ', d3:'wQ', f4:'wQ', h5:'wQ', b6:'wQ', e7:'wQ', c8:'wQ' }{ a1:'wQ', g2:'wQ', e3:'wQ', h4:'wQ', b5:'wQ', d6:'wQ', f7:'wQ', c8:'wQ' }{ b1:'wQ', d2:'wQ', f3:'wQ', h4:'wQ', c5:'wQ', a6:'wQ', g7:'wQ', e8:'wQ' }{ b1:'wQ', e2:'wQ', g3:'wQ', a4:'wQ', c5:'wQ', h6:'wQ', f7:'wQ', d8:'wQ' }{ b1:'wQ', e2:'wQ', g3:'wQ', d4:'wQ', a5:'wQ', h6:'wQ', f7:'wQ', c8:'wQ' }{ b1:'wQ', f2:'wQ', a3:'wQ', g4:'wQ', d5:'wQ', h6:'wQ', c7:'wQ', e8:'wQ' }{ b1:'wQ', f2:'wQ', h3:'wQ', c4:'wQ', a5:'wQ', d6:'wQ', g7:'wQ', e8:'wQ' }{ b1:'wQ', g2:'wQ', c3:'wQ', f4:'wQ', h5:'wQ', e6:'wQ', a7:'wQ', d8:'wQ' }{ b1:'wQ', g2:'wQ', e3:'wQ', h4:'wQ', a5:'wQ', d6:'wQ', f7:'wQ', c8:'wQ' }{ b1:'wQ', h2:'wQ', f3:'wQ', a4:'wQ', c5:'wQ', e6:'wQ', g7:'wQ', d8:'wQ' }{ c1:'wQ', a2:'wQ', g3:'wQ', e4:'wQ', h5:'wQ', b6:'wQ', d7:'wQ', f8:'wQ' }{ c1:'wQ', e2:'wQ', b3:'wQ', h4:'wQ', a5:'wQ', g6:'wQ', d7:'wQ', f8:'wQ' }{ c1:'wQ', e2:'wQ', b3:'wQ', h4:'wQ', f5:'wQ', d6:'wQ', g7:'wQ', a8:'wQ' }{ c1:'wQ', e2:'wQ', g3:'wQ', a4:'wQ', d5:'wQ', b6:'wQ', h7:'wQ', f8:'wQ' }{ c1:'wQ', e2:'wQ', h3:'wQ', d4:'wQ', a5:'wQ', g6:'wQ', b7:'wQ', f8:'wQ' }{ c1:'wQ', f2:'wQ', b3:'wQ', e4:'wQ', h5:'wQ', a6:'wQ', g7:'wQ', d8:'wQ' }{ c1:'wQ', f2:'wQ', b3:'wQ', g4:'wQ', a5:'wQ', d6:'wQ', h7:'wQ', e8:'wQ' }{ c1:'wQ', f2:'wQ', b3:'wQ', g4:'wQ', e5:'wQ', a6:'wQ', h7:'wQ', d8:'wQ' }{ c1:'wQ', f2:'wQ', d3:'wQ', a4:'wQ', h5:'wQ', e6:'wQ', g7:'wQ', b8:'wQ' }{ c1:'wQ', f2:'wQ', d3:'wQ', b4:'wQ', h5:'wQ', e6:'wQ', g7:'wQ', a8:'wQ' }{ c1:'wQ', f2:'wQ', h3:'wQ', a4:'wQ', d5:'wQ', g6:'wQ', e7:'wQ', b8:'wQ' }{ c1:'wQ', f2:'wQ', h3:'wQ', a4:'wQ', e5:'wQ', g6:'wQ', b7:'wQ', d8:'wQ' }{ c1:'wQ', f2:'wQ', h3:'wQ', b4:'wQ', d5:'wQ', a6:'wQ', g7:'wQ', e8:'wQ' }{ c1:'wQ', g2:'wQ', b3:'wQ', h4:'wQ', e5:'wQ', a6:'wQ', d7:'wQ', f8:'wQ' }{ c1:'wQ', g2:'wQ', b3:'wQ', h4:'wQ', f5:'wQ', d6:'wQ', a7:'wQ', e8:'wQ' }{ c1:'wQ', h2:'wQ', d3:'wQ', g4:'wQ', a5:'wQ', f6:'wQ', b7:'wQ', e8:'wQ' }{ d1:'wQ', a2:'wQ', e3:'wQ', h4:'wQ', b5:'wQ', g6:'wQ', c7:'wQ', f8:'wQ' }{ d1:'wQ', a2:'wQ', e3:'wQ', h4:'wQ', f5:'wQ', c6:'wQ', g7:'wQ', b8:'wQ' }{ d1:'wQ', b2:'wQ', e3:'wQ', h4:'wQ', f5:'wQ', a6:'wQ', c7:'wQ', g8:'wQ' }{ d1:'wQ', b2:'wQ', g3:'wQ', c4:'wQ', f5:'wQ', h6:'wQ', a7:'wQ', e8:'wQ' }{ d1:'wQ', b2:'wQ', g3:'wQ', c4:'wQ', f5:'wQ', h6:'wQ', e7:'wQ', a8:'wQ' }{ d1:'wQ', b2:'wQ', g3:'wQ', e4:'wQ', a5:'wQ', h6:'wQ', f7:'wQ', c8:'wQ' }{ d1:'wQ', b2:'wQ', h3:'wQ', e4:'wQ', g5:'wQ', a6:'wQ', c7:'wQ', f8:'wQ' }{ d1:'wQ', b2:'wQ', h3:'wQ', f4:'wQ', a5:'wQ', c6:'wQ', e7:'wQ', g8:'wQ' }{ d1:'wQ', f2:'wQ', a3:'wQ', e4:'wQ', b5:'wQ', h6:'wQ', c7:'wQ', g8:'wQ' }{ d1:'wQ', f2:'wQ', h3:'wQ', b4:'wQ', g5:'wQ', a6:'wQ', c7:'wQ', e8:'wQ' }{ d1:'wQ', f2:'wQ', h3:'wQ', c4:'wQ', a5:'wQ', g6:'wQ', e7:'wQ', b8:'wQ' }{ d1:'wQ', g2:'wQ', a3:'wQ', h4:'wQ', e5:'wQ', b6:'wQ', f7:'wQ', c8:'wQ' }{ d1:'wQ', g2:'wQ', c3:'wQ', h4:'wQ', b5:'wQ', e6:'wQ', a7:'wQ', f8:'wQ' }{ d1:'wQ', g2:'wQ', e3:'wQ', b4:'wQ', f5:'wQ', a6:'wQ', c7:'wQ', h8:'wQ' }{ d1:'wQ', g2:'wQ', e3:'wQ', c4:'wQ', a5:'wQ', f6:'wQ', h7:'wQ', b8:'wQ' }{ d1:'wQ', h2:'wQ', a3:'wQ', c4:'wQ', f5:'wQ', b6:'wQ', g7:'wQ', e8:'wQ' }{ d1:'wQ', h2:'wQ', a3:'wQ', e4:'wQ', g5:'wQ', b6:'wQ', f7:'wQ', c8:'wQ' }{ d1:'wQ', h2:'wQ', e3:'wQ', c4:'wQ', a5:'wQ', g6:'wQ', b7:'wQ', f8:'wQ' }{ e1:'wQ', a2:'wQ', d3:'wQ', f4:'wQ', h5:'wQ', b6:'wQ', g7:'wQ', c8:'wQ' }{ e1:'wQ', a2:'wQ', h3:'wQ', d4:'wQ', b5:'wQ', g6:'wQ', c7:'wQ', f8:'wQ' }{ e1:'wQ', a2:'wQ', h3:'wQ', f4:'wQ', c5:'wQ', g6:'wQ', b7:'wQ', d8:'wQ' }{ e1:'wQ', b2:'wQ', d3:'wQ', f4:'wQ', h5:'wQ', c6:'wQ', a7:'wQ', g8:'wQ' }{ e1:'wQ', b2:'wQ', d3:'wQ', g4:'wQ', c5:'wQ', h6:'wQ', f7:'wQ', a8:'wQ' }{ e1:'wQ', b2:'wQ', f3:'wQ', a4:'wQ', g5:'wQ', d6:'wQ', h7:'wQ', c8:'wQ' }{ e1:'wQ', b2:'wQ', h3:'wQ', a4:'wQ', d5:'wQ', g6:'wQ', c7:'wQ', f8:'wQ' }{ e1:'wQ', c2:'wQ', a3:'wQ', f4:'wQ', h5:'wQ', b6:'wQ', d7:'wQ', g8:'wQ' }{ e1:'wQ', c2:'wQ', a3:'wQ', g4:'wQ', b5:'wQ', h6:'wQ', f7:'wQ', d8:'wQ' }{ e1:'wQ', c2:'wQ', h3:'wQ', d4:'wQ', g5:'wQ', a6:'wQ', f7:'wQ', b8:'wQ' }{ e1:'wQ', g2:'wQ', a3:'wQ', c4:'wQ', h5:'wQ', f6:'wQ', d7:'wQ', b8:'wQ' }{ e1:'wQ', g2:'wQ', a3:'wQ', d4:'wQ', b5:'wQ', h6:'wQ', f7:'wQ', c8:'wQ' }{ e1:'wQ', g2:'wQ', b3:'wQ', d4:'wQ', h5:'wQ', a6:'wQ', c7:'wQ', f8:'wQ' }{ e1:'wQ', g2:'wQ', b3:'wQ', f4:'wQ', c5:'wQ', a6:'wQ', d7:'wQ', h8:'wQ' }{ e1:'wQ', g2:'wQ', b3:'wQ', f4:'wQ', c5:'wQ', a6:'wQ', h7:'wQ', d8:'wQ' }{ e1:'wQ', g2:'wQ', d3:'wQ', a4:'wQ', c5:'wQ', h6:'wQ', f7:'wQ', b8:'wQ' }{ e1:'wQ', h2:'wQ', d3:'wQ', a4:'wQ', c5:'wQ', f6:'wQ', b7:'wQ', g8:'wQ' }{ e1:'wQ', h2:'wQ', d3:'wQ', a4:'wQ', g5:'wQ', b6:'wQ', f7:'wQ', c8:'wQ' }{ f1:'wQ', a2:'wQ', e3:'wQ', b4:'wQ', h5:'wQ', c6:'wQ', g7:'wQ', d8:'wQ' }{ f1:'wQ', b2:'wQ', g3:'wQ', a4:'wQ', c5:'wQ', e6:'wQ', h7:'wQ', d8:'wQ' }{ f1:'wQ', b2:'wQ', g3:'wQ', a4:'wQ', d5:'wQ', h6:'wQ', e7:'wQ', c8:'wQ' }{ f1:'wQ', c2:'wQ', a3:'wQ', g4:'wQ', e5:'wQ', h6:'wQ', b7:'wQ', d8:'wQ' }{ f1:'wQ', c2:'wQ', a3:'wQ', h4:'wQ', d5:'wQ', b6:'wQ', g7:'wQ', e8:'wQ' }{ f1:'wQ', c2:'wQ', a3:'wQ', h4:'wQ', e5:'wQ', b6:'wQ', d7:'wQ', g8:'wQ' }{ f1:'wQ', c2:'wQ', e3:'wQ', g4:'wQ', a5:'wQ', d6:'wQ', b7:'wQ', h8:'wQ' }{ f1:'wQ', c2:'wQ', e3:'wQ', h4:'wQ', a5:'wQ', d6:'wQ', b7:'wQ', g8:'wQ' }{ f1:'wQ', c2:'wQ', g3:'wQ', b4:'wQ', d5:'wQ', h6:'wQ', a7:'wQ', e8:'wQ' }{ f1:'wQ', c2:'wQ', g3:'wQ', b4:'wQ', h5:'wQ', e6:'wQ', a7:'wQ', d8:'wQ' }{ f1:'wQ', c2:'wQ', g3:'wQ', d4:'wQ', a5:'wQ', h6:'wQ', b7:'wQ', e8:'wQ' }{ f1:'wQ', d2:'wQ', a3:'wQ', e4:'wQ', h5:'wQ', b6:'wQ', g7:'wQ', c8:'wQ' }{ f1:'wQ', d2:'wQ', b3:'wQ', h4:'wQ', e5:'wQ', g6:'wQ', a7:'wQ', c8:'wQ' }{ f1:'wQ', d2:'wQ', g3:'wQ', a4:'wQ', c5:'wQ', e6:'wQ', b7:'wQ', h8:'wQ' }{ f1:'wQ', d2:'wQ', g3:'wQ', a4:'wQ', h5:'wQ', b6:'wQ', e7:'wQ', c8:'wQ' }{ f1:'wQ', h2:'wQ', b3:'wQ', d4:'wQ', a5:'wQ', g6:'wQ', e7:'wQ', c8:'wQ' }{ g1:'wQ', a2:'wQ', c3:'wQ', h4:'wQ', f5:'wQ', d6:'wQ', b7:'wQ', e8:'wQ' }{ g1:'wQ', b2:'wQ', d3:'wQ', a4:'wQ', h5:'wQ', e6:'wQ', c7:'wQ', f8:'wQ' }{ g1:'wQ', b2:'wQ', f3:'wQ', c4:'wQ', a5:'wQ', d6:'wQ', h7:'wQ', e8:'wQ' }{ g1:'wQ', c2:'wQ', a3:'wQ', f4:'wQ', h5:'wQ', e6:'wQ', b7:'wQ', d8:'wQ' }{ g1:'wQ', c2:'wQ', h3:'wQ', b4:'wQ', e5:'wQ', a6:'wQ', f7:'wQ', d8:'wQ' }{ g1:'wQ', d2:'wQ', b3:'wQ', e4:'wQ', h5:'wQ', a6:'wQ', c7:'wQ', f8:'wQ' }{ g1:'wQ', d2:'wQ', b3:'wQ', h4:'wQ', f5:'wQ', a6:'wQ', c7:'wQ', e8:'wQ' }{ g1:'wQ', e2:'wQ', c3:'wQ', a4:'wQ', f5:'wQ', h6:'wQ', b7:'wQ', d8:'wQ' }{ h1:'wQ', b2:'wQ', d3:'wQ', a4:'wQ', g5:'wQ', e6:'wQ', c7:'wQ', f8:'wQ' }{ h1:'wQ', b2:'wQ', e3:'wQ', c4:'wQ', a5:'wQ', g6:'wQ', d7:'wQ', f8:'wQ' }{ h1:'wQ', c2:'wQ', a3:'wQ', f4:'wQ', b5:'wQ', e6:'wQ', g7:'wQ', d8:'wQ' }{ h1:'wQ', d2:'wQ', a3:'wQ', c4:'wQ', f5:'wQ', b6:'wQ', g7:'wQ', e8:'wQ' }
Method 2: PHP Code:
<?php
// Find all 8 Queens solutions
// modified from http://rosettacode.org/wiki/N-queens_problem#PHP
function solve8queens_2() {
$boardX = 8;
$boardY = 8;
// create the different possible rows
for ($x = 0; $x < $boardX; ++$x){ $row[$x] = 1 << $x; }
// create all the possible orders of rows, will be equal to [boardY]!
$solcount = 0;
$solutions = array();
while ($row != false) {
if(checkBoard($row,$boardX)){
if(!in_array($row,$solutions)){
$solutions[] = $row;
$solutions = findRotation($row,$boardX,$solutions);
++$solcount;
}
}
$row = pc_next_permutation($row);
}
return $solutions;
} // end function
//////////////////////////////////////////////////
// Function to rotate a board 90 degrees
function rotateBoard($p, $boardX) {
$a=0;
while ($a < count($p)) {
$b = strlen(decbin($p[$a]))-1;
$tmp[$b] = 1 << ($boardX - $a - 1);
++$a;
}
ksort($tmp);
return $tmp;
}
// This function will find rotations of a solution
function findRotation($p, $boardX,$solutions){
$tmp = rotateBoard($p,$boardX);
// Rotated 90
if (in_array($tmp,$solutions)) {} else {$solutions[] = $tmp;}
$tmp = rotateBoard($tmp,$boardX);
// Rotated 180
if (in_array($tmp,$solutions)){} else {$solutions[] = $tmp;}
$tmp = rotateBoard($tmp,$boardX);
// Rotated 270
if (in_array($tmp,$solutions)){} else {$solutions[] = $tmp;}
// Reflected
$tmp = array_reverse($p);
if (in_array($tmp,$solutions)){} else {$solutions[] = $tmp;}
$tmp = rotateBoard($tmp,$boardX);
// Reflected and Rotated 90
if (in_array($tmp,$solutions)){} else {$solutions[] = $tmp;}
$tmp = rotateBoard($tmp,$boardX);
// Reflected and Rotated 180
if (in_array($tmp,$solutions)){} else {$solutions[] = $tmp;}
$tmp = rotateBoard($tmp,$boardX);
// Reflected and Rotated 270
if (in_array($tmp,$solutions)){} else {$solutions[] = $tmp;}
return $solutions;
}
// output board in chessboard.js/JSON format
function renderBoard($p,$boardX) {
$sol = array();
for ($y = 0; $y < $boardX; ++$y) {
for ($x = 0; $x < $boardX; ++$x) {
if ($p[$y] == 1 << $x) { $sol[] = numtoalpha($x) . ($y+1); }
}
}
$solution = join(":'wQ', ",$sol);
return "{ $solution:'wQ' }" ;
}
function numtoalpha($n) {
switch($n) {
default: return;
case '0': return 'a'; case '1': return 'b'; case '2': return 'c'; case '3': return 'd';
case '4': return 'e'; case '5': return 'f'; case '6': return 'g'; case '7': return 'h';
}
}
//This function allows me to generate the next order of rows.
function pc_next_permutation($p) {
$size = count($p) - 1;
// slide down the array looking for where we're smaller than the next guy
for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { }
// if this doesn't occur, we've finished our permutations
// the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
if ($i == -1) { return false; }
// slide down the array looking for a bigger number than what we found before
for ($j = $size; $p[$j] <= $p[$i]; --$j) { }
// swap them
$tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
// now reverse the elements in between by swapping the ends
for (++$i, $j = $size; $i < $j; ++$i, --$j) { $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp; }
return $p;
}
// check the current state to see if there are any solutions
function checkBoard($p,$boardX) {
$a = 0; // the row being checked
while ($a < count($p)) {
$b = 1;
while ($b < ($boardX - $a)){
$x = $p[$a+$b] << $b; // shift p[a+b], b bits left
$y = $p[$a+$b] >> $b; // shift p[a+b], b bits right
if ($p[$a] == $x | $p[$a] == $y) { return false; } // a queen is under attack
++$b;
}
++$a;
}
return true;
}
Method 3: Hard code!
Why waste time computing all solutions on every page load? Just do it once.
Use any method to solve all 92 solutions,
then hardcode the results into your program to use as needed!
Absolutely the fastest method ;)
Method 3: PHP Code:
<?php
// All 8 Queens solutions in an array
// Format: JSON/chessboard.js
$solutions[] = "{ a1:'wQ', e2:'wQ', h3:'wQ', f4:'wQ', c5:'wQ', g6:'wQ', b7:'wQ', d8:'wQ' }";
$solutions[] = "{ a1:'wQ', f2:'wQ', h3:'wQ', c4:'wQ', g5:'wQ', d6:'wQ', b7:'wQ', e8:'wQ' }";
$solutions[] = "{ a1:'wQ', g2:'wQ', d3:'wQ', f4:'wQ', h5:'wQ', b6:'wQ', e7:'wQ', c8:'wQ' }";
$solutions[] = "{ a1:'wQ', g2:'wQ', e3:'wQ', h4:'wQ', b5:'wQ', d6:'wQ', f7:'wQ', c8:'wQ' }";
$solutions[] = "{ b1:'wQ', d2:'wQ', f3:'wQ', h4:'wQ', c5:'wQ', a6:'wQ', g7:'wQ', e8:'wQ' }";
$solutions[] = "{ b1:'wQ', e2:'wQ', g3:'wQ', a4:'wQ', c5:'wQ', h6:'wQ', f7:'wQ', d8:'wQ' }";
$solutions[] = "{ b1:'wQ', e2:'wQ', g3:'wQ', d4:'wQ', a5:'wQ', h6:'wQ', f7:'wQ', c8:'wQ' }";
$solutions[] = "{ b1:'wQ', f2:'wQ', a3:'wQ', g4:'wQ', d5:'wQ', h6:'wQ', c7:'wQ', e8:'wQ' }";
$solutions[] = "{ b1:'wQ', f2:'wQ', h3:'wQ', c4:'wQ', a5:'wQ', d6:'wQ', g7:'wQ', e8:'wQ' }";
$solutions[] = "{ b1:'wQ', g2:'wQ', c3:'wQ', f4:'wQ', h5:'wQ', e6:'wQ', a7:'wQ', d8:'wQ' }";
$solutions[] = "{ b1:'wQ', g2:'wQ', e3:'wQ', h4:'wQ', a5:'wQ', d6:'wQ', f7:'wQ', c8:'wQ' }";
$solutions[] = "{ b1:'wQ', h2:'wQ', f3:'wQ', a4:'wQ', c5:'wQ', e6:'wQ', g7:'wQ', d8:'wQ' }";
$solutions[] = "{ c1:'wQ', a2:'wQ', g3:'wQ', e4:'wQ', h5:'wQ', b6:'wQ', d7:'wQ', f8:'wQ' }";
$solutions[] = "{ c1:'wQ', e2:'wQ', b3:'wQ', h4:'wQ', a5:'wQ', g6:'wQ', d7:'wQ', f8:'wQ' }";
$solutions[] = "{ c1:'wQ', e2:'wQ', b3:'wQ', h4:'wQ', f5:'wQ', d6:'wQ', g7:'wQ', a8:'wQ' }";
$solutions[] = "{ c1:'wQ', e2:'wQ', g3:'wQ', a4:'wQ', d5:'wQ', b6:'wQ', h7:'wQ', f8:'wQ' }";
$solutions[] = "{ c1:'wQ', e2:'wQ', h3:'wQ', d4:'wQ', a5:'wQ', g6:'wQ', b7:'wQ', f8:'wQ' }";
$solutions[] = "{ c1:'wQ', f2:'wQ', b3:'wQ', e4:'wQ', h5:'wQ', a6:'wQ', g7:'wQ', d8:'wQ' }";
$solutions[] = "{ c1:'wQ', f2:'wQ', b3:'wQ', g4:'wQ', a5:'wQ', d6:'wQ', h7:'wQ', e8:'wQ' }";
$solutions[] = "{ c1:'wQ', f2:'wQ', b3:'wQ', g4:'wQ', e5:'wQ', a6:'wQ', h7:'wQ', d8:'wQ' }";
$solutions[] = "{ c1:'wQ', f2:'wQ', d3:'wQ', a4:'wQ', h5:'wQ', e6:'wQ', g7:'wQ', b8:'wQ' }";
$solutions[] = "{ c1:'wQ', f2:'wQ', d3:'wQ', b4:'wQ', h5:'wQ', e6:'wQ', g7:'wQ', a8:'wQ' }";
$solutions[] = "{ c1:'wQ', f2:'wQ', h3:'wQ', a4:'wQ', d5:'wQ', g6:'wQ', e7:'wQ', b8:'wQ' }";
$solutions[] = "{ c1:'wQ', f2:'wQ', h3:'wQ', a4:'wQ', e5:'wQ', g6:'wQ', b7:'wQ', d8:'wQ' }";
$solutions[] = "{ c1:'wQ', f2:'wQ', h3:'wQ', b4:'wQ', d5:'wQ', a6:'wQ', g7:'wQ', e8:'wQ' }";
$solutions[] = "{ c1:'wQ', g2:'wQ', b3:'wQ', h4:'wQ', e5:'wQ', a6:'wQ', d7:'wQ', f8:'wQ' }";
$solutions[] = "{ c1:'wQ', g2:'wQ', b3:'wQ', h4:'wQ', f5:'wQ', d6:'wQ', a7:'wQ', e8:'wQ' }";
$solutions[] = "{ c1:'wQ', h2:'wQ', d3:'wQ', g4:'wQ', a5:'wQ', f6:'wQ', b7:'wQ', e8:'wQ' }";
$solutions[] = "{ d1:'wQ', a2:'wQ', e3:'wQ', h4:'wQ', b5:'wQ', g6:'wQ', c7:'wQ', f8:'wQ' }";
$solutions[] = "{ d1:'wQ', a2:'wQ', e3:'wQ', h4:'wQ', f5:'wQ', c6:'wQ', g7:'wQ', b8:'wQ' }";
$solutions[] = "{ d1:'wQ', b2:'wQ', e3:'wQ', h4:'wQ', f5:'wQ', a6:'wQ', c7:'wQ', g8:'wQ' }";
$solutions[] = "{ d1:'wQ', b2:'wQ', g3:'wQ', c4:'wQ', f5:'wQ', h6:'wQ', a7:'wQ', e8:'wQ' }";
$solutions[] = "{ d1:'wQ', b2:'wQ', g3:'wQ', c4:'wQ', f5:'wQ', h6:'wQ', e7:'wQ', a8:'wQ' }";
$solutions[] = "{ d1:'wQ', b2:'wQ', g3:'wQ', e4:'wQ', a5:'wQ', h6:'wQ', f7:'wQ', c8:'wQ' }";
$solutions[] = "{ d1:'wQ', b2:'wQ', h3:'wQ', e4:'wQ', g5:'wQ', a6:'wQ', c7:'wQ', f8:'wQ' }";
$solutions[] = "{ d1:'wQ', b2:'wQ', h3:'wQ', f4:'wQ', a5:'wQ', c6:'wQ', e7:'wQ', g8:'wQ' }";
$solutions[] = "{ d1:'wQ', f2:'wQ', a3:'wQ', e4:'wQ', b5:'wQ', h6:'wQ', c7:'wQ', g8:'wQ' }";
$solutions[] = "{ d1:'wQ', f2:'wQ', h3:'wQ', b4:'wQ', g5:'wQ', a6:'wQ', c7:'wQ', e8:'wQ' }";
$solutions[] = "{ d1:'wQ', f2:'wQ', h3:'wQ', c4:'wQ', a5:'wQ', g6:'wQ', e7:'wQ', b8:'wQ' }";
$solutions[] = "{ d1:'wQ', g2:'wQ', a3:'wQ', h4:'wQ', e5:'wQ', b6:'wQ', f7:'wQ', c8:'wQ' }";
$solutions[] = "{ d1:'wQ', g2:'wQ', c3:'wQ', h4:'wQ', b5:'wQ', e6:'wQ', a7:'wQ', f8:'wQ' }";
$solutions[] = "{ d1:'wQ', g2:'wQ', e3:'wQ', b4:'wQ', f5:'wQ', a6:'wQ', c7:'wQ', h8:'wQ' }";
$solutions[] = "{ d1:'wQ', g2:'wQ', e3:'wQ', c4:'wQ', a5:'wQ', f6:'wQ', h7:'wQ', b8:'wQ' }";
$solutions[] = "{ d1:'wQ', h2:'wQ', a3:'wQ', c4:'wQ', f5:'wQ', b6:'wQ', g7:'wQ', e8:'wQ' }";
$solutions[] = "{ d1:'wQ', h2:'wQ', a3:'wQ', e4:'wQ', g5:'wQ', b6:'wQ', f7:'wQ', c8:'wQ' }";
$solutions[] = "{ d1:'wQ', h2:'wQ', e3:'wQ', c4:'wQ', a5:'wQ', g6:'wQ', b7:'wQ', f8:'wQ' }";
$solutions[] = "{ e1:'wQ', a2:'wQ', d3:'wQ', f4:'wQ', h5:'wQ', b6:'wQ', g7:'wQ', c8:'wQ' }";
$solutions[] = "{ e1:'wQ', a2:'wQ', h3:'wQ', d4:'wQ', b5:'wQ', g6:'wQ', c7:'wQ', f8:'wQ' }";
$solutions[] = "{ e1:'wQ', a2:'wQ', h3:'wQ', f4:'wQ', c5:'wQ', g6:'wQ', b7:'wQ', d8:'wQ' }";
$solutions[] = "{ e1:'wQ', b2:'wQ', d3:'wQ', f4:'wQ', h5:'wQ', c6:'wQ', a7:'wQ', g8:'wQ' }";
$solutions[] = "{ e1:'wQ', b2:'wQ', d3:'wQ', g4:'wQ', c5:'wQ', h6:'wQ', f7:'wQ', a8:'wQ' }";
$solutions[] = "{ e1:'wQ', b2:'wQ', f3:'wQ', a4:'wQ', g5:'wQ', d6:'wQ', h7:'wQ', c8:'wQ' }";
$solutions[] = "{ e1:'wQ', b2:'wQ', h3:'wQ', a4:'wQ', d5:'wQ', g6:'wQ', c7:'wQ', f8:'wQ' }";
$solutions[] = "{ e1:'wQ', c2:'wQ', a3:'wQ', f4:'wQ', h5:'wQ', b6:'wQ', d7:'wQ', g8:'wQ' }";
$solutions[] = "{ e1:'wQ', c2:'wQ', a3:'wQ', g4:'wQ', b5:'wQ', h6:'wQ', f7:'wQ', d8:'wQ' }";
$solutions[] = "{ e1:'wQ', c2:'wQ', h3:'wQ', d4:'wQ', g5:'wQ', a6:'wQ', f7:'wQ', b8:'wQ' }";
$solutions[] = "{ e1:'wQ', g2:'wQ', a3:'wQ', c4:'wQ', h5:'wQ', f6:'wQ', d7:'wQ', b8:'wQ' }";
$solutions[] = "{ e1:'wQ', g2:'wQ', a3:'wQ', d4:'wQ', b5:'wQ', h6:'wQ', f7:'wQ', c8:'wQ' }";
$solutions[] = "{ e1:'wQ', g2:'wQ', b3:'wQ', d4:'wQ', h5:'wQ', a6:'wQ', c7:'wQ', f8:'wQ' }";
$solutions[] = "{ e1:'wQ', g2:'wQ', b3:'wQ', f4:'wQ', c5:'wQ', a6:'wQ', d7:'wQ', h8:'wQ' }";
$solutions[] = "{ e1:'wQ', g2:'wQ', b3:'wQ', f4:'wQ', c5:'wQ', a6:'wQ', h7:'wQ', d8:'wQ' }";
$solutions[] = "{ e1:'wQ', g2:'wQ', d3:'wQ', a4:'wQ', c5:'wQ', h6:'wQ', f7:'wQ', b8:'wQ' }";
$solutions[] = "{ e1:'wQ', h2:'wQ', d3:'wQ', a4:'wQ', c5:'wQ', f6:'wQ', b7:'wQ', g8:'wQ' }";
$solutions[] = "{ e1:'wQ', h2:'wQ', d3:'wQ', a4:'wQ', g5:'wQ', b6:'wQ', f7:'wQ', c8:'wQ' }";
$solutions[] = "{ f1:'wQ', a2:'wQ', e3:'wQ', b4:'wQ', h5:'wQ', c6:'wQ', g7:'wQ', d8:'wQ' }";
$solutions[] = "{ f1:'wQ', b2:'wQ', g3:'wQ', a4:'wQ', c5:'wQ', e6:'wQ', h7:'wQ', d8:'wQ' }";
$solutions[] = "{ f1:'wQ', b2:'wQ', g3:'wQ', a4:'wQ', d5:'wQ', h6:'wQ', e7:'wQ', c8:'wQ' }";
$solutions[] = "{ f1:'wQ', c2:'wQ', a3:'wQ', g4:'wQ', e5:'wQ', h6:'wQ', b7:'wQ', d8:'wQ' }";
$solutions[] = "{ f1:'wQ', c2:'wQ', a3:'wQ', h4:'wQ', d5:'wQ', b6:'wQ', g7:'wQ', e8:'wQ' }";
$solutions[] = "{ f1:'wQ', c2:'wQ', a3:'wQ', h4:'wQ', e5:'wQ', b6:'wQ', d7:'wQ', g8:'wQ' }";
$solutions[] = "{ f1:'wQ', c2:'wQ', e3:'wQ', g4:'wQ', a5:'wQ', d6:'wQ', b7:'wQ', h8:'wQ' }";
$solutions[] = "{ f1:'wQ', c2:'wQ', e3:'wQ', h4:'wQ', a5:'wQ', d6:'wQ', b7:'wQ', g8:'wQ' }";
$solutions[] = "{ f1:'wQ', c2:'wQ', g3:'wQ', b4:'wQ', d5:'wQ', h6:'wQ', a7:'wQ', e8:'wQ' }";
$solutions[] = "{ f1:'wQ', c2:'wQ', g3:'wQ', b4:'wQ', h5:'wQ', e6:'wQ', a7:'wQ', d8:'wQ' }";
$solutions[] = "{ f1:'wQ', c2:'wQ', g3:'wQ', d4:'wQ', a5:'wQ', h6:'wQ', b7:'wQ', e8:'wQ' }";
$solutions[] = "{ f1:'wQ', d2:'wQ', a3:'wQ', e4:'wQ', h5:'wQ', b6:'wQ', g7:'wQ', c8:'wQ' }";
$solutions[] = "{ f1:'wQ', d2:'wQ', b3:'wQ', h4:'wQ', e5:'wQ', g6:'wQ', a7:'wQ', c8:'wQ' }";
$solutions[] = "{ f1:'wQ', d2:'wQ', g3:'wQ', a4:'wQ', c5:'wQ', e6:'wQ', b7:'wQ', h8:'wQ' }";
$solutions[] = "{ f1:'wQ', d2:'wQ', g3:'wQ', a4:'wQ', h5:'wQ', b6:'wQ', e7:'wQ', c8:'wQ' }";
$solutions[] = "{ f1:'wQ', h2:'wQ', b3:'wQ', d4:'wQ', a5:'wQ', g6:'wQ', e7:'wQ', c8:'wQ' }";
$solutions[] = "{ g1:'wQ', a2:'wQ', c3:'wQ', h4:'wQ', f5:'wQ', d6:'wQ', b7:'wQ', e8:'wQ' }";
$solutions[] = "{ g1:'wQ', b2:'wQ', d3:'wQ', a4:'wQ', h5:'wQ', e6:'wQ', c7:'wQ', f8:'wQ' }";
$solutions[] = "{ g1:'wQ', b2:'wQ', f3:'wQ', c4:'wQ', a5:'wQ', d6:'wQ', h7:'wQ', e8:'wQ' }";
$solutions[] = "{ g1:'wQ', c2:'wQ', a3:'wQ', f4:'wQ', h5:'wQ', e6:'wQ', b7:'wQ', d8:'wQ' }";
$solutions[] = "{ g1:'wQ', c2:'wQ', h3:'wQ', b4:'wQ', e5:'wQ', a6:'wQ', f7:'wQ', d8:'wQ' }";
$solutions[] = "{ g1:'wQ', d2:'wQ', b3:'wQ', e4:'wQ', h5:'wQ', a6:'wQ', c7:'wQ', f8:'wQ' }";
$solutions[] = "{ g1:'wQ', d2:'wQ', b3:'wQ', h4:'wQ', f5:'wQ', a6:'wQ', c7:'wQ', e8:'wQ' }";
$solutions[] = "{ g1:'wQ', e2:'wQ', c3:'wQ', a4:'wQ', f5:'wQ', h6:'wQ', b7:'wQ', d8:'wQ' }";
$solutions[] = "{ h1:'wQ', b2:'wQ', d3:'wQ', a4:'wQ', g5:'wQ', e6:'wQ', c7:'wQ', f8:'wQ' }";
$solutions[] = "{ h1:'wQ', b2:'wQ', e3:'wQ', c4:'wQ', a5:'wQ', g6:'wQ', d7:'wQ', f8:'wQ' }";
$solutions[] = "{ h1:'wQ', c2:'wQ', a3:'wQ', f4:'wQ', b5:'wQ', e6:'wQ', g7:'wQ', d8:'wQ' }";
$solutions[] = "{ h1:'wQ', d2:'wQ', a3:'wQ', c4:'wQ', f5:'wQ', b6:'wQ', g7:'wQ', e8:'wQ' }";