
\:    N queens problem solved in zoem.

\:    This solution uses recursion (naturally), maintaining dictionaries
\:    with push#1 and pop#1. It also uses a crude form of iteration
\:    using apply#2. Failure is escalated back using throw#2 and catch#2.
\:    This constitutes a non-trivial example of apply#2 / throw#2 / catch#2
\:    used in conjunction.

\:    A more customary solution is to use while#2 rather than the
\:    latter method -- see 8q2.azm.

\:    This solution has caused two zoem weak spots to be addressed:
\:    -  inability to cleanly assign a vararg to a data key.
\:     -> now possible with \set{{modes}{u}}{%{key}}{{a}{b}{c}{e}{t}{c}}
\:    -  inability to effect global key updates while dictionaries are pushed.
\:     -> now possible with \set{''key}{..} (and \''key access).


\if{\let{!\defined{key}{N} || \N < 1}}{
   \write{stderr}{device}{Use e.g. zoem -i 8q -s N=9 to solve the 9-queen problem\@{\N}}
   \set{N}{8}
}{}
\setx{N}{\let{floor(\N)}}

\set{n_backtrack}{0}
\set{p_backtrack}{0}
                  \: When updating these we have to be careful
                  \: to do it in the bottom global dictionary,
                  \: not in a higher stacked transient dictionary.

\set{%{lists}{0}}{}

\set{n1}{0}
\set{n}{1}

                  \: Precompute all lists that we are going to feed
                  \: to apply#2. This is only slightly wasteful.
\while{\let{\n<=\N}}{
                  \: This uses recently introduced primitive set#3.
                  \: The u modifier indicates the value argument
                  \: should not be parsed as a key-value list.
   \set{{modes}{xu}}{%{lists}{\n}}{\%{lists}{\n1} {\n1}}

   \set{%{positions}{\n}}{}
   \setx{n1}{\n}
   \setx{n}{\let{\n+1}}
}

                  \: for shorter print statement
\def{pp#1}{\%{positions}{\1}}


                  \:
                  \:
                  \:     5 |  .  .  .  .  .  .         
                  \:     4 |  .  .  *  .  .  .
                  \:     3 |  .  .  .  .  ?  .
                  \:     2 |  .  *  .  .  .  .
                  \:     1 |  .  .  .  *  .  .
                  \:     0 |  *  .  .  .  .  .
                  \:       |________________________
                  \: col:  |              4  5  6  7
                  \: c:       0  1  2  3

                  \: for c in 0..col-1 get the position and see whether it
                  \: is compatible with col,row
\formatted{

   \def{testcompat#1}{
      \setx{c}{\1}

      \if{\let{
            \%{positions}{\c}==\row
         || abs(\%{positions}{\c}-\row) == abs(\col-\c)
         }
       }{\setx{''n_backtrack}{\let{\''n_backtrack+1}}
         \throw{towel}{}
      }{}
   }

                  \: Try whether row would fit col.
   \def{testrow#1}{
      \push{testrow}
         \setx{row}{\1}
         \catch{towel}{
            \apply{testcompat#1}{\%{lists}{\col}}
         }
                  \: Alternative is to use \while rather than apply+catch
                  \: still, timing seems to be OK for this approach.

         \if{\cmp{eq}{\__zoemstat__}{done}}{
            \setx{%{positions}{\col}}{\row}
            \if{\let{\col<\N-1}}{
               \extendcol{\let{\col+1}}
            }{
               \write{\__fnout__}{device}{\@{\N}\pp{0}}
               \set{t}{1}
               \while{\let{\t<\N}}{
                  \write{\__fnout__}{device}{\`{s}\pp{\t}}
                  \setx{t}{\let{\t+1}}
               }
               \setx{d_bt}{\let{\''n_backtrack-\''p_backtrack}}
               \write{\__fnout__}{device}{\ifdef{key}{trace}{\`{s}(\''n_backtrack, \d_bt)}\@{\n}}
               \setx{''p_backtrack}{\''n_backtrack}
            }
         }{}
      \pop{testrow}
   }

                  \: 0..col-1 columns are OK
                  \: Try to extend to column col.
   \def{extendcol#1}{
      \push{extendcol}
         \setx{col}{\1}
         \apply{testrow#1}{\%{lists}{\N}}
      \pop{extendcol}
   }
}

                  \: vanish#1 omits the filter/output stage in an attempt
                  \: to gain some speed -- it only results in side effects (yay!)
                  \: such as the \write#2 invocation above.
                  \: However, because we used formatted#1 we really don't
                  \: gain anything as all result strings have length zero
                  \: anyway.
\vanish{\extendcol{0}}

\write{stderr}{device}{Backtracked \''n_backtrack times\@{\n}}

