Advertisement
Nordicus

'N' Queen problem

Nov 21st, 2012
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Pascal 3.45 KB | None | 0 0
  1. program FPProgT15;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. uses
  6.   {$IFDEF UNIX}{$IFDEF UseCThreads}
  7.   cthreads,
  8.   {$ENDIF}{$ENDIF}
  9.   Classes, math, SysUtils;
  10.  
  11. type
  12.   QueenArray = Array of Integer;
  13.  
  14.  
  15. var
  16.   MainQueens: QueenArray;
  17.   i, n, SuccessCounter, AttemptCounter: int64;
  18.   OverFlow: Boolean;
  19.   MyFile: TextFile;
  20.   today: TDateTime;
  21.   {$R *.res}
  22.  
  23. function isLegit(Queens: QueenArray): Boolean;
  24. var
  25.    i, j: integer;
  26.    final: boolean;
  27. begin
  28.      final := true;
  29.      for i := 1 to n do
  30.      begin
  31.        if final = true then
  32.        begin
  33.          for j := i - 1 downto 1 do
  34.          begin
  35.             if Queens[i] = Queens[j] then final := false
  36.             else if Queens[j] = Queens[i] - (i-j) then final := false
  37.             else if Queens[j] = Queens[i] + (i-j) then final := false;
  38.          end;
  39.        end;
  40.      if final = true then isLegit := true
  41.      else isLegit := false;
  42.      end;
  43. end;
  44.  
  45. procedure AddLineToFile(var FileToAppend: TextFile; LineToAdd: String);
  46. begin
  47.   Append(FileToAppend);
  48.   Writeln(FileToAppend, LineToAdd);
  49.   CloseFile(FileToAppend);
  50. end;
  51.  
  52. procedure quit;
  53. begin
  54.   //SolutionList.SaveToFile(IntToStr(n) + '_Solutions.txt');
  55.   writeln;
  56.   writeln;
  57.   writeln('Press <Enter> To Quit');
  58.   today := now;
  59.   writeln('Completed at: ' + TimeToStr(today));
  60.   readln;
  61. end;
  62.  
  63. procedure DrawBoard(Queens: QueenArray);
  64. var
  65.    i, j: integer;
  66.    isWhite: Boolean;
  67.    OutStr: String;
  68. begin
  69.   for i := n downto 1 do
  70.   begin
  71.   OutStr := '';
  72.     for j := 1 to n do
  73.     begin
  74.       if ((i + j) mod 2) = 0 then isWhite := false
  75.       else isWhite := true;
  76.       if Queens[j] = i then
  77.       begin
  78.         if isWhite = true then OutStr := OutStr + ' W Q'
  79.         else OutStr := OutStr + ' B Q';
  80.       end
  81.       else
  82.       begin
  83.         if isWhite = true then OutStr := OutStr + ' WNQ'
  84.         else OutStr := OutStr + ' BNQ'
  85.       end;
  86.     end;
  87.     Writeln(OutStr);
  88.     //SolutionList.Append(OutStr);
  89.     AddLineToFile(MyFile, OutStr);
  90.   end;
  91.   Writeln;
  92.   //SolutionList.Append('');
  93.   AddLineToFile(MyFile, '');
  94. end;
  95.  
  96. procedure AdvanceQueen(Index: Integer);
  97. var
  98.   i: integer;
  99. begin
  100.   if MainQueens[Index] < n then MainQueens[Index] := MainQueens[Index] + 1 //if there is room to progress then progress
  101.   else
  102.   begin
  103.     index := index + 1;
  104.     for i := Index - 1 downto 1 do
  105.     begin
  106.       MainQueens[i] := 1
  107.     end;
  108.     if Index <= n then AdvanceQueen(Index)
  109.     else OverFlow := True;
  110.   end;
  111. end;
  112.  
  113. procedure SolveForN;
  114. begin
  115.   SuccessCounter := 0;
  116.   SetLength(MainQueens, 0); //Clear the array
  117.   SetLength(MainQueens, n); //Reset its size
  118.   AssignFile(MyFile, (IntToStr(n) + '_Solutions.txt'));
  119.   ReWrite(MyFile);
  120.   for i := 1 to n do MainQueens[i] := 1; //initialise all the queens
  121.   OverFlow := False;
  122.   AttemptCounter := 0;
  123.   repeat
  124.   begin
  125.     AdvanceQueen(0);
  126.     AttemptCounter := AttemptCounter + 1;
  127.     if isLegit(MainQueens) = true then
  128.     begin
  129.       SuccessCounter := SuccessCounter + 1;
  130.       Today := now;
  131.       Writeln('Success on attempt: ' + inttostr(AttemptCounter) + ' at: ' + TimeToStr(today));
  132.       Writeln('Board No. ' + IntToStr(SuccessCounter));
  133.       AddLineToFile(MyFile, 'Board No. ' + IntToStr(SuccessCounter));
  134.       DrawBoard(MainQueens);
  135.     end
  136.     else if AttemptCounter mod 100000000 = 0 then writeln('Failed on attempt: ' + IntToStr(AttemptCounter) + ' out of 285311670611');
  137.   end;
  138.   until OverFlow = true;
  139. end;
  140.  
  141. begin
  142.   n := 11;
  143.   SolveForN;
  144.   quit;
  145. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement