n_queen.py

# !/usr/bin/env python
# -*- coding:utf-8 -*-

# Written by sota1235
# Date 2014/3/2

import sys

"""
board上の(x,y)の縦横斜めの値にnを足す
"""
def changeBoard(board, x, y, n, p):
    N = n

    # 縦横にnを足す
    for i in range(N):
        board[x][i] += p
        board[i][y] += p

    # 右下がり斜め
    if x > y:
        for i in range(N - abs(x - y)):
            board[i+(x-y)][i] += p
    elif x <= y:
        for i in range(N - abs(x - y)):
            board[i][i+(y-x)] += p

    # 左下がり斜め
    if (x+y) < N:
        for i in range(x + y + 1):
            board[i][x+y-i] += p
    elif (x+y) >= N:
        for i in range(x + y + N + 1, N):
            board[x+y-i][i] += p

    board[x][y] -= 3

    return board

"""
queenのx行にQueenをセット
"""
def setQueen(x, board, queen):
    N = len(queen)
    """
    print N
    print x
    """
    # i=N で終了
    if x == N:
        printQueen(queen)
        return

    for y in range(N):
        if board[x][y] == 0:
            queen[x] = y+1
            board = changeBoard(board, x, y, N, 1)
            setQueen(x+1, board, queen)
            board = changeBoard(board, x, y, N, -1)
"""
結果出力
"""
def printQueen(queen):
    j = 0
    ans = str(len(queen)) + " queen: "
    for i in queen:
        ans += str(i) + " "
    print ans

"""
Main
"""
def __main__(N):
    board = [[0 for i in range(N)] for j in range(N)]
    queen = [0 for i in range(N)]
    setQueen(0, board, queen)


# Nの入力
N = int(raw_input("N = "))
__main__(N)