/*  Copyright (c) 2006, Philip Busch <broesel@studcs.uni-sb.de>
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions are met:
 *
 *   - Redistributions of source code must retain the above copyright notice,
 *     this list of conditions and the following disclaimer.
 *   - Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *   - Neither the name of the author nor the names of its contributors may
 *     be used to endorse or promote products derived from this software
 *     without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 *  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 *  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 *  ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 *  LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 *  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 *  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 *  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 *  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 *  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 *  POSSIBILITY OF SUCH DAMAGE.
 */

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

inline int is_conflict(int _cboard[], int _col) {
	int i;
	
	for(i = 0; i < _col; i++) {
		if((_cboard[i] == _cboard[_col])               // gleiche Zeile
		|| (_cboard[i] + i == _cboard[_col] + _col)    // gleiche Diag.
		|| (_cboard[i] - i == _cboard[_col] - _col)) { // gleiche Diag.
		        return(1);
		}
	}
	return(0);
}

void print_board(int _cboard[], int _size) {
	int i = 0;
	
	for(; i < _size; i++) {
		printf("%i", _cboard[i]);
	}
	printf("\n");
}

void solve_queensproblem(int _size) {
	int cboard[_size];
	int col = 0;
	int solutions = 0;
	int tries     = 0;
	int i = 0;
	
	// initialize checkerboard
	for(; i < _size; i++)
	        cboard[i] = 0;

	for(;;) {
		if(cboard[col] > _size-1) {   // no valid options left, go back
			cboard[col] = 0;
			if(col == 0) break;
			col -= 1;
			cboard[col]++;
		} else if(!is_conflict(cboard, col)) {               // advance
			if(col == _size-1) {
				solutions++;
				print_board(cboard, _size);
			}
			col += 1;
		} else {                             // retry at current column
			cboard[col]++;
		}

		tries++;
	}

	printf("%i solutions with %i tries\n", solutions, tries);
}

int main(int argc, char *argv[]) {
	if(argc != 2) {
		printf("USAGE: %s <size>\n", argv[0]);
		exit(EXIT_FAILURE);
	} else {
		solve_queensproblem(atoi(argv[argc-1]));
	}

	return(0);
}