-- Copyright (C) International Computer Science Institute, 1995.  COPYRIGHT  --
-- NOTICE: This code is provided "AS IS" WITHOUT ANY WARRANTY and is subject --
-- to the terms of the SATHER LIBRARY GENERAL PUBLIC LICENSE contained in    --
-- the file "Doc/License" of the Sather distribution.  The license is also   --
-- available from ICSI, 1947 Center St., Suite 600, Berkeley CA 94704, USA.  --
--------> Please email comments to "sather-bugs@icsi.berkeley.edu". <----------
--
-- solves the N queen problem
-- Version 1.0, June 1996, by Claudio Fleiner

class QUEEN is
   include AREF{CHAR};
   shared print_result:BOOL:=false;

   str:STR is 
      res::="QUEENS: ";
      loop res:=res+aelt!.int+" "; end;
      res:=res+"\n";
      return res;
   end;

   print is #OUT+str; end;

   pos(x:INT):INT is
      count::=0;
      if x=asize then
         if print_result then print; end;
	 return 1;
      else
	 loop i::=asize.times!;
	    if [i]=0.char then
	       ok::=true;
	       loop while!(ok);
	          j::=asize.times!;
		  ok:=[j].int=0 or (x+1-[j].int/=i-j and x+1-[j].int/=j-i);
	       end;
	       if ok then
	          [i]:=(x+1).char;
		  count:=count+pos(x+1);
		  [i]:=0.char;
	       end;
	    end;
         end;
      end;
      return count;
   end;

   pos:INT is return pos(0); end;
end;

class MAIN is
   test is
      b::=#QUEEN(8);
      QUEEN::print_result:=true;
      #OUT+("found "+b.pos+" solutions for the 8 - queen problem\n");
   end;

   usage is
      #ERR+"USAGE: queen TEST | [-p] size\n";
   end;

   main(argv:ARRAY{STR}):INT is
      size::=0;
      if argv.size=2 and argv[1]="TEST" then test; return 0; end;
      if argv.size=3 then
         if argv[1]="-p" then QUEEN::print_result:=true;
	 else usage; return 1; end;
	 size:=#INT(argv[2]);
      elsif argv.size=2 then
         size:=#INT(argv[1]);
      else 
	 usage; return 1;
      end;

      if size<1 or size>99 then usage; return 1; end;

      b::=#QUEEN(size);
      t::=#TIMES;
      found::=b.pos;
      d::=t.elapsed;
      #OUT+"found "+found+" solutions for the "+size+" - queen problem\n";
      #OUT+d.str;
      return 0;
   end;
end;
      
   
-- vim:sw=3:nosmartindent