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