1 /*
   2  * My solution to the n-queens puzzle, one of the classical problems of the
   3  * structural programming. It asks in how many ways you can arrange n chess
   4  * queens on an n-times-n chessboard without breaking the rules that no two
   5  * chess queens can be in the same row, column or diagonal.
   6  */
   7 
   8 // Import some functions we need to communicate with the outside world from
   9 // JavaScript...
  10 Function printString(PointerToCharacter str)
  11   Which Returns Nothing Is External;
  12 Function clearScreen() Which Returns Nothing Is External;
  13 Function shouldWePrintChessBoards() Which Returns Integer32 Is External;
  14 
  15 // Declare the "Queen" structure and write relevant functions.
  16 Structure Queen Consists Of
  17   Integer32 row, column;
  18 EndStructure
  19 
  20 Function areQueensInTheSameColumn(PointerToQueen first, PointerToQueen second)
  21   Which Returns Integer32 Does
  22     Return first->column = second->column;
  23 EndFunction
  24 
  25 Function areQueensInTheSameRow(PointerToQueen first, PointerToQueen second)
  26   Which Returns Integer32 Does
  27     Return first->row = second->row;
  28 EndFunction
  29 
  30 Function areQueensOnTheSameDiagonal(PointerToQueen first,
  31                                     PointerToQueen second)
  32   Which Returns Integer32 Does
  33     Return first->row + first->column = second->row + second->column or
  34            first->row - first->column = second->row - second->column;
  35 EndFunction
  36 
  37 Function areQueensAttackingEachOther(PointerToQueen first,
  38                                      PointerToQueen second)
  39   Which Returns Integer32 Does
  40     Return areQueensInTheSameRow(first, second) or
  41            areQueensInTheSameColumn(first, second) or
  42            areQueensOnTheSameDiagonal(first, second);
  43 EndFunction
  44 
  45 // Let's write a structure representing an array of queens...
  46 Structure ChessBoard Consists Of
  47   Integer32 length;
  48   Queen queens[12]; // There are too many solutions for over 12 queens.
  49 EndStructure
  50 
  51 Function chessBoardContainsThatQueen(PointerToChessBoard chessBoard,
  52                                      PointerToQueen queen)
  53                                       Which Returns Integer32 Does
  54   Integer32 i := 0;
  55   While i < chessBoard->length Loop
  56     If chessBoard->queens[i].column = queen->column and
  57        chessBoard->queens[i].row    = queen->row    Then
  58       Return 1;
  59     EndIf
  60     i += 1;
  61   EndWhile
  62   Return 0;
  63 EndFunction
  64 
  65 // Now, let's forward-declare the functions we will write later.
  66 // Putting them here would make the code less legible.
  67 Function validatePartialSolutionAndTryToExtend(PointerToChessBoard chessBoard,
  68                                                Integer32 n)
  69 	 Which Returns Integer32 Is Declared;
  70 
  71 Function convertIntegerToString(PointerToCharacter str,
  72                                 Integer32 n)
  73   Which Returns Nothing Is Declared;
  74 
  75 Function strcat(PointerToCharacter dest,
  76                 PointerToCharacter src) Which Returns Nothing Is Declared;
  77 
  78 Function strlen(PointerToCharacter str) Which Returns Integer32 Is Declared;
  79 
  80 // Let's write the function that JavaScript is supposed to call...
  81 Function nQueensPuzzle(Integer32 n) Which Returns Integer32 Does
  82   clearScreen();
  83   If not(1 <= n <= 12) Then
  84     printString("Please enter a number between 1 and 12!");
  85     Return -1;
  86   EndIf
  87   InstantiateStructure ChessBoard chessBoard;
  88   Character stringToBePrinted[64] := {0};
  89   PointerToCharacter stringToBePrinted := AddressOf(stringToBePrinted[0]);
  90   strcat(stringToBePrinted, "Solving the n-queens puzzle for ");
  91   convertIntegerToString(stringToBePrinted + strlen(stringToBePrinted),
  92                          n);
  93   strcat(stringToBePrinted,":\n");
  94   printString(stringToBePrinted);
  95   Integer32 result := validatePartialSolutionAndTryToExtend(AddressOf(chessBoard), n);
  96   stringToBePrinted[0] := 0;
  97   strcat(stringToBePrinted, "Found ");
  98   convertIntegerToString(stringToBePrinted + strlen(stringToBePrinted),
  99                          result);
 100   strcat(stringToBePrinted, " solutions!");
 101   printString(stringToBePrinted);
 102   Return result;
 103 EndFunction
 104 
 105 // I guess moving this code out of "validatePartialSolutionAndTryToExtend"
 106 // makes the code more legible.
 107 Function printAsASolution(PointerToChessBoard chessBoard)
 108   Which Returns Nothing Does
 109     Character stringToBePrinted[64] := {0};
 110     Character stringToBeAdded[8];
 111     Integer32 i := 0;
 112     While i < chessBoard->length Loop
 113       stringToBeAdded[0] := 'A' + chessBoard->queens[i].column;
 114       convertIntegerToString(AddressOf(stringToBeAdded[1]),
 115                              chessBoard->queens[i].row + 1);
 116       strcat(AddressOf(stringToBeAdded[0]), " ");
 117       strcat(AddressOf(stringToBePrinted[0]),
 118              AddressOf(stringToBeAdded[0]));
 119       i += 1;
 120     EndWhile
 121     strcat(AddressOf(stringToBePrinted[0]), "\n");
 122     printString(AddressOf(stringToBePrinted[0]));
 123     If shouldWePrintChessBoards() Then
 124         stringToBePrinted[0] := 0;
 125         PointerToCharacter stringToBePrinted := AddressOf(stringToBePrinted[0]);
 126         strcat(stringToBePrinted, "  +");
 127         i := 0;
 128         While i < chessBoard->length Loop
 129           strcat(stringToBePrinted, "-+");
 130           i += 1;
 131         EndWhile
 132         strcat(stringToBePrinted, "\n");
 133         printString(stringToBePrinted);
 134         i := chessBoard->length;
 135         While i > 0 Loop
 136           stringToBePrinted[0] := 0;
 137           // Align the row numbers to the right.
 138           If i < 10 Then
 139             strcat(stringToBePrinted, " ");
 140           EndIf
 141           convertIntegerToString(stringToBePrinted + strlen(stringToBePrinted), i);
 142           strcat(stringToBePrinted, "|");
 143           Integer32 j := 0;
 144           While j < chessBoard->length Loop
 145             InstantiateStructure Queen newQueen;
 146             newQueen.column :=     j;
 147             newQueen.row    := i - 1;
 148             strcat(stringToBePrinted,
 149                    chessBoardContainsThatQueen(chessBoard, AddressOf(newQueen))?
 150                    "Q|":
 151                    mod(i + j - 1, 2)?
 152                    " |": // White field.
 153                    "*|"  // Black field.
 154             );
 155             j += 1;
 156           EndWhile
 157           strcat(stringToBePrinted, "\n");
 158           printString(stringToBePrinted);
 159           stringToBePrinted[0] := 0;
 160           strcat(stringToBePrinted, "  +");
 161           j := 0;
 162           While j < chessBoard->length Loop
 163             strcat(stringToBePrinted, "-+");
 164             j += 1;
 165           EndWhile
 166           strcat(stringToBePrinted, "\n");
 167           printString(stringToBePrinted);
 168           i -= 1;
 169         EndWhile
 170         stringToBePrinted[0] := 0;
 171         PointerToCharacter stringToBeAdded := AddressOf(stringToBeAdded[0]);
 172         stringToBeAdded[2] := 0;
 173         stringToBeAdded[0] := ' ';
 174         strcat(stringToBePrinted, "  ");
 175         i := 0;
 176         While i < chessBoard->length Loop
 177           stringToBeAdded[1] := 'A' + i;
 178           strcat(stringToBePrinted, stringToBeAdded);
 179           i += 1;
 180         EndWhile
 181         strcat(stringToBePrinted, "\n");
 182         printString(stringToBePrinted);
 183     EndIf
 184 EndFunction
 185 
 186 // Now, let's implement the brute-force algorithm.
 187 Function validatePartialSolutionAndTryToExtend // A name suggested by a Reddit user called tobega:
 188 // https://www.reddit.com/r/ProgrammingLanguages/comments/1ay30y8/comment/krwdde9/?utm_source=share&utm_medium=web3x&utm_name=web3xcss&utm_term=1&utm_content=share_button
 189                                                (PointerToChessBoard chessBoard,
 190                                                Integer32 n) 
 191 					       Which Returns Integer32 Does
 192   // First, do some sanity checks useful for debugging...
 193   If chessBoard->length > n Then
 194     printString("Bug: Chessboard length too large!");
 195     Return 0;
 196   EndIf
 197   Integer32 i := 0, j := 0;
 198   While i < chessBoard->length Loop
 199     If chessBoard->queens[i].column < 0 or
 200        chessBoard->queens[i].row    < 0 or
 201        chessBoard->queens[i].column > n or
 202        chessBoard->queens[i].row    > n Then
 203       printString("Bug: Corrupt chessboard!");
 204       Return 0;
 205     EndIf
 206     i += 1;
 207   EndWhile
 208   // Check if there is a contradiction (queens attacking
 209   // each other) in what we have thus far...
 210   i := j := 0;
 211   While i < chessBoard->length Loop
 212     j := i + 1;
 213     While j < chessBoard->length Loop
 214       If not(i = j) and areQueensAttackingEachOther(
 215                           AddressOf(chessBoard->queens[i]),
 216                           AddressOf(chessBoard->queens[j])
 217                         ) Then
 218         Return 0;
 219       EndIf
 220       j += 1;
 221     EndWhile
 222     i += 1;
 223   EndWhile
 224   // Check if this is a solution...
 225   If chessBoard->length = n Then
 226     printAsASolution(chessBoard);
 227     Return 1;
 228   EndIf
 229   // If this is not a complete solution, but there are no contradictions
 230   // in it, branch the recursion into searching for complete solutions
 231   // based on this one.
 232   Integer32 result := 0;
 233   i := 0;
 234   While i<n Loop
 235     InstantiateStructure ChessBoard newChessBoard := ValueAt(chessBoard);
 236     newChessBoard.length += 1;
 237     newChessBoard.queens[chessBoard->length].column := chessBoard->length;
 238     newChessBoard.queens[chessBoard->length].row := i;
 239     result += validatePartialSolutionAndTryToExtend(AddressOf(newChessBoard), n);
 240     i += 1;
 241   EndWhile
 242   Return result;
 243 EndFunction
 244 
 245 // Now go the helper functions related to string manipulation,
 246 // copied from the Dragon Curve program. They are named the same
 247 // as the corresponding functions in the standard C library.
 248 Function strlen(PointerToCharacter str) Which Returns Integer32 Does
 249      Integer32 length := 0;
 250      While ValueAt(str + length) Loop
 251          length := length + 1;
 252      EndWhile
 253      Return length;
 254 EndFunction
 255 
 256 Function strcpy(PointerToCharacter dest,
 257                 PointerToCharacter src) Which Returns Nothing Does
 258     While ValueAt(src) Loop
 259         ValueAt(dest) := ValueAt(src);
 260         dest          :=     dest + 1;
 261         src           :=      src + 1;
 262      EndWhile
 263     ValueAt(dest) := 0;
 264 EndFunction
 265 
 266 Function strcat(PointerToCharacter dest,
 267                 PointerToCharacter src) Which Returns Nothing Does
 268     strcpy(dest + strlen(dest), src);
 269 EndFunction
 270 
 271 Function reverseString(PointerToCharacter string) Which Returns Nothing Does
 272     PointerToCharacter pointerToLastCharacter := string + strlen(string) - 1;
 273     While pointerToLastCharacter - string > 0 Loop
 274         Character tmp                   := ValueAt(string);
 275         ValueAt(string)                 := ValueAt(pointerToLastCharacter);
 276         ValueAt(pointerToLastCharacter) := tmp;
 277         string                          := string + 1;
 278         pointerToLastCharacter          := pointerToLastCharacter - 1;
 279     EndWhile
 280 EndFunction
 281 
 282 Function convertIntegerToString(PointerToCharacter string,
 283                                 Integer32 number)
 284     Which Returns Nothing Does
 285     Integer32 isNumberNegative := 0;
 286     If number < 0 Then
 287         number           := -number;
 288         isNumberNegative :=       1;
 289     EndIf
 290     Integer32 i := 0;
 291     While number > 9 Loop
 292         ValueAt(string + i) := '0' + mod(number, 10);
 293         number              :=           number / 10;
 294         i                   :=                 i + 1;
 295     EndWhile
 296     ValueAt(string + i) := '0' + number;
 297     i                   :=        i + 1;
 298     If isNumberNegative Then
 299         ValueAt(string + i) :=   '-';
 300         i                   := i + 1;
 301     EndIf
 302     ValueAt(string + i) := 0;
 303     reverseString(string);
 304 EndFunction
 305