-- N-queens puzzle implemented with "Distinct Choices" pattern
-- Sergio Antoy
-- Tue Sep  4 13:16:20 PDT 2001
-- updated: Mon Sep 23 15:22:15 PDT 2002
-- updated: Wed Jun 28 13:41:40 PDT 2017

{-# OPTIONS_CYMAKE -F --pgmF=currypp --optF=defaultrules #-}

import Integer

main = queens (permute 5)

queens (_++[x]++y++[z]++_) | abs (x-z) == length y + 1 = failed
queens'default p = p

-- How does this permutation algorithm work?
-- Only the elements [0,1,...,n-1] can be permuted.
-- The reason is that each element is used as an index in a list.
-- A list, called store, of free variables of length n is created.
-- Then, the n iterations described below are executed.
-- At the i-th iteration, an element, say s,
-- of the initial list is non-deterministically selected.
-- This element is used as index in the store.
-- The s-th variable of the store is unified with i.
-- At the end of the iterations, the elements of the store
-- are a permutation of [0,1,...,n-1], i.e., the elements
-- are unique since two iterations cannot select the same index.

permute n = result n
   where result n = if n==0 then [] else pick n store : result (n-1)
         pick i store | store !! k == i = k where k = range n
         range n | n > 0 = range (n-1) ? (n-1)
         store free
-- end