/*
* 8-queen problem using brute force searching
* This solutions uses following strategies
*
* 1 - fix one queen in one column and generate all
* non-conflicting permutations - N! in total
* this is akin to solving the N-rook problem
* 2- eliminate from N! permutations - that do not
* pass the additional diagonal test
*
* @author Rajeev Jha
* @version 1.0
*
*/
import java.util.Set;
import java.util.HashSet;
public class queen8 {
private int[] columns ;
private char[] colNames ;
private int size ;
private int solutions ;
public queen8(int N) {
this.columns = new int[N] ;
for(int i=0 ; i < N ; i++) this.columns[i] = i+1 ;
this.colNames = new char[N] ;
char a = 'A' ;
for(int i=0 ; i < N ; i++) this.colNames[i] = (char) (a + i) ;
this.size = N ;
this.solutions = 0 ;
}
private void solve() {
this.generate(this.size);
}
/*
* permutation generator using a backtracking algo
* from http://www.cs.princeton.edu/~rs/talks/perms.pdf */
private void generate(int N){
int c ;
/* factorial 1, 1! case,just one possibility,print that ..*/
if ( N == 0 ) test_diagonal();
//algorithm adjusted for zero-based indexes ..
for(c = 0 ; c < N ; c++){
swap(c,N-1);
generate(N-1);
swap(c,N-1);
}
}
/* swap for permutation */
private void swap(int x, int y){
int tmp = this.columns[x] ;
this.columns[x] = this.columns[y] ;
this.columns[y] = tmp ;
}
/* for position of a queen in a column (a permutation)
* diagonal positions are given by moving
* one row up in next column and one row down in
* previous column */
private void test_diagonal(){
int x ;
for(int i = 0 ; i < this.columns.length ; i++) {
x = this.columns[i] ;
for(int j = i+1, k = 1; j < this.columns.length ; j++, k++) {
if((x+k) == this.columns[j]) return ;
if((x-k) == this.columns[j]) return ;
}
}
// diagonal test passed
print_board();
}
private void print_board() {
for(int i = 0 ; i < this.columns.length ; i++) {
System.out.print(this.colNames[i]);
System.out.print(this.columns[i] + " ");
}
System.out.println();
this.solutions++ ;
}
private int getNumSolutions() {
return this.solutions ;
}
public static void main(String[] args) throws Exception {
queen8 board = new queen8(8);
board.solve();
System.out.println(" \n Total " + board.getNumSolutions() + " solutions " );
}
}
rjha@mint13 ~/code/fun $ javac queen8.java
rjha@mint13 ~/code/fun $ java -classpath . queen8
A4 B2 C7 D3 E6 F8 G5 H1
A5 B2 C4 D7 E3 F8 G6 H1
A3 B5 C2 D8 E6 F4 G7 H1
A3 B6 C4 D2 E8 F5 G7 H1
A4 B7 C5 D3 E1 F6 G8 H2
A5 B7 C1 D3 E8 F6 G4 H2
A4 B6 C8 D3 E1 F7 G5 H2
A3 B6 C8 D1 E4 F7 G5 H2
A5 B3 C8 D4 E7 F1 G6 H2
A5 B7 C4 D1 E3 F8 G6 H2
A4 B1 C5 D8 E6 F3 G7 H2
A3 B6 C4 D1 E8 F5 G7 H2
A6 B4 C2 D8 E5 F7 G1 H3
A5 B2 C6 D1 E7 F4 G8 H3
A6 B4 C7 D1 E8 F2 G5 H3
A1 B7 C4 D6 E8 F2 G5 H3
A6 B2 C7 D1 E4 F8 G5 H3
A6 B8 C2 D4 E1 F7 G5 H3
A5 B8 C4 D1 E7 F2 G6 H3
A4 B8 C1 D5 E7 F2 G6 H3
A4 B7 C1 D8 E5 F2 G6 H3
A4 B2 C7 D5 E1 F8 G6 H3
A2 B5 C7 D4 E1 F8 G6 H3
A5 B7 C1 D4 E2 F8 G6 H3
A2 B7 C5 D8 E1 F4 G6 H3
A1 B7 C5 D8 E2 F4 G6 H3
A5 B1 C4 D6 E8 F2 G7 H3
A6 B4 C1 D5 E8 F2 G7 H3
A6 B3 C7 D2 E8 F5 G1 H4
A2 B7 C3 D6 E8 F5 G1 H4
A5 B1 C8 D6 E3 F7 G2 H4
A1 B5 C8 D6 E3 F7 G2 H4
A3 B6 C8 D1 E5 F7 G2 H4
A7 B5 C3 D1 E6 F8 G2 H4
A6 B3 C1 D7 E5 F8 G2 H4
A7 B3 C1 D6 E8 F5 G2 H4
A5 B7 C2 D6 E3 F1 G8 H4
A3 B6 C2 D7 E5 F1 G8 H4
A6 B2 C7 D1 E3 F5 G8 H4
A7 B3 C8 D2 E5 F1 G6 H4
A5 B3 C1 D7 E2 F8 G6 H4
A2 B5 C7 D1 E3 F8 G6 H4
A3 B6 C2 D5 E8 F1 G7 H4
A6 B1 C5 D2 E8 F3 G7 H4
A8 B3 C1 D6 E2 F5 G7 H4
A2 B8 C6 D1 E3 F5 G7 H4
A3 B7 C2 D8 E6 F4 G1 H5
A6 B3 C7 D2 E4 F8 G1 H5
A4 B2 C7 D3 E6 F8 G1 H5
A1 B6 C8 D3 E7 F4 G2 H5
A7 B1 C3 D8 E6 F4 G2 H5
A6 B3 C7 D4 E1 F8 G2 H5
A3 B8 C4 D7 E1 F6 G2 H5
A7 B4 C2 D8 E6 F1 G3 H5
A4 B6 C8 D2 E7 F1 G3 H5
A2 B6 C1 D7 E4 F8 G3 H5
A3 B6 C2 D7 E1 F4 G8 H5
A7 B2 C6 D3 E1 F4 G8 H5
A2 B4 C6 D8 E3 F1 G7 H5
A3 B6 C8 D2 E4 F1 G7 H5
A8 B4 C1 D3 E6 F2 G7 H5
A4 B8 C1 D3 E6 F2 G7 H5
A6 B3 C1 D8 E4 F2 G7 H5
A2 B6 C8 D3 E1 F4 G7 H5
A4 B7 C3 D8 E2 F5 G1 H6
A4 B8 C5 D3 E1 F7 G2 H6
A3 B5 C8 D4 E1 F7 G2 H6
A7 B4 C2 D5 E8 F1 G3 H6
A5 B7 C2 D4 E8 F1 G3 H6
A4 B2 C8 D5 E7 F1 G3 H6
A4 B1 C5 D8 E2 F7 G3 H6
A5 B1 C8 D4 E2 F7 G3 H6
A5 B2 C8 D1 E4 F7 G3 H6
A8 B2 C4 D1 E7 F5 G3 H6
A7 B2 C4 D1 E8 F5 G3 H6
A3 B7 C2 D8 E5 F1 G4 H6
A3 B1 C7 D5 E8 F2 G4 H6
A8 B2 C5 D3 E1 F7 G4 H6
A3 B5 C2 D8 E1 F7 G4 H6
A3 B5 C7 D1 E4 F2 G8 H6
A5 B2 C4 D6 E8 F3 G1 H7
A6 B3 C5 D8 E1 F4 G2 H7
A5 B8 C4 D1 E3 F6 G2 H7
A4 B2 C5 D8 E6 F1 G3 H7
A4 B6 C1 D5 E2 F8 G3 H7
A5 B3 C1 D6 E8 F2 G4 H7
A6 B3 C1 D8 E5 F2 G4 H7
A4 B2 C8 D6 E1 F3 G5 H7
A6 B3 C5 D7 E1 F4 G2 H8
A6 B4 C7 D1 E3 F5 G2 H8
A4 B7 C5 D2 E6 F1 G3 H8
A5 B7 C2 D6 E3 F1 G4 H8
Total 92 solutions
error_reporting(-1);
libxml_use_internal_errors(true);
function process_post($title,$category,$tags,$createdOn) {
if(empty($content)) { return ; }
// process post
}
// start:script
// wp.xml contains dump of wordpress posts
if (file_exists('wp.xml')) {
$doc = simplexml_load_file('wp.xml');
if($doc === false) {
echo "Failed loading XML\n";
foreach(libxml_get_errors() as $error) {
echo "\t", $error->message;
}
}
} else {
echo('Failed to open wp.xml.');
exit ;
}
foreach($doc->channel->item as $item) {
$title = $item->title ;
// content and other elements can be wrapped inside
// a separate namespace. To deal with such elements we
// use item->children on the namespace given in wp.xml
$ns_wp = $item->children("http://wordpress.org/export/1.1/");
$attachment = $ns_wp->attachment_url ;
if(empty($attachment)) {
$ns_content = $item->children("http://purl.org/rss/1.0/modules/content/");
$content = (string) $ns_content->encoded;
$link = $item->link ;
$pubDate = $item->pubDate ;
$createdOn = date("Y-m-d", strtotime($pubDate));
$tags = "" ;
$category = "" ;
// tags and category
// we can have multiple category elements inside an item
foreach($item->category as $elemCategory) {
if(strcmp($elemCategory["domain"],"category") == 0 ) {
$category = $category." ".$elemCategory["nicename"] ;
}
if(strcmp($elemCategory["domain"],"post_tag") == 0 ) {
$tags = $tags." ".$elemCategory["nicename"] ;
}
}
printf("title = %s, category = %s ,tags = %s , pub_date = %s \n",$title,$category,$tags,$createdOn);
process_post($title,$category,$tags,$createdOn);
}
}
