(ns superqueens
    (:require [clojure.data.int-map :as i]))

(def N (Integer/parseInt (read-line)))
; (def N 14)

(defn between [v1 v2 v]
    (and (<= v1 v) (<= v v2)))

(defn between-xy [v1x v1y v2x v2y px py]
    (and (between v1x v2x px) (between v1y v2y py)))

(defn blocked [qx qy x y]
    (or
        (= x qx)
        (= (- x qx) (- y qy))
        (= (- x qx) (- qy y))
        (between-xy (- qx 2)(- qy 2) (+ qx 2)(+ qy 2) x y)))

(def BLOCKERS
    (vec (for [qy (range N) qx (range N)]
        (i/int-set (for [y (range N) x (range N) :when (blocked qx qy x y)]
               (+ x (* N y)))))))

(defn place [row board]
  (if (< row N)
   (let [pmin (* N row)]
     (reduce + (for [p (range pmin (+ N pmin))
                     :when (nil? (board p))]
                 (place 
                    (inc row)
                    (i/union board (BLOCKERS p))))))
   1))

(let [t0 (System/currentTimeMillis)]
  (println (place 0 (i/int-set)))
  (format "Time: %d" (- (System/currentTimeMillis) t0)))

import Control.Monad (guard)

import qualified Data.IntSet as Set

placeNSuperQueens :: Int -> Int
placeNSuperQueens n
    = length (go Set.empty Set.empty Set.empty
                 (100, 100) -- y value of last two columns. For first column,
                            -- represents nonsense value that passes knight check.
                 n)
    where go _ _ _ _ 0
              = return () -- If go had an extra argument that accumulated y
                          -- positions, it could return valid placements easily.
                          -- The tuple of the last two columns would then
                          -- be unnecessary. It currently returns unit as this
                          -- information is not needed.
          go horizontals diagonals antidiagonals (y1, y2) left = do
              y <- [1..n]
              let x = n - left
                  -- These next two variables are key. To the right, a mapping
                  -- from board position to diagonals (\) and antidiagonals (/).
                  currentDiagonal = y - x
                  currentAntidiagonal = y + x
              -- Perform knight checks first, as they are quicker.
              guard $ abs (y2 - y) /= 2 
              guard $ abs (y1 - y) /= 1
              -- Queen operations use sets, and are thus slower.
              -- We want to discard failing placements quickly.
              guard $ y `Set.notMember` horizontals
              guard $ currentDiagonal `Set.notMember` diagonals
              guard $ currentAntidiagonal `Set.notMember` antidiagonals
              go (Set.insert y horizontals)
                 (Set.insert currentDiagonal diagonals)
                 (Set.insert currentAntidiagonal antidiagonals)
                 (y2, y)
                 (left - 1)

main :: IO ()
main = interact $ show . placeNSuperQueens . read