A simple program to generate an iterative solver for the N-queens problem

NQueensGenerator.java

/* N-Queens non-recursive code generator
 * Andrew Smith, UT Computer Science 2022
 * [email protected]
 *
 * LICENSE:
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */


import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;

public class NQueensGenerator {
    private static PrintWriter out = null;
    private static int boardSize;

    public static void printIndentedLine(String line, int indentLevel) {
        // Add two spaces until desired indentation level is reached
        for (int i = 0; i < indentLevel; i++)
            out.print("  ");
        out.println(line);
    }

    public static void generateLoop(int levelsRemaining, int indentLevel) {
        // Loop level to generate
        int nestingLevel = boardSize - levelsRemaining;

        // Base case: levelsRemaining == 0 at last possible column
        if (levelsRemaining == 0) {
            printIndentedLine("if (queensAreSafe(queenRows)) {", indentLevel);
            printIndentedLine("printSolution(queenRows);", indentLevel + 1);
            printIndentedLine("numSolutions++;", indentLevel + 1);
            printIndentedLine("}", indentLevel);
            return;
        }

        // Otherwise, print the next loop
        printIndentedLine("if (queensAreSafe(queenRows)) {", indentLevel);
        printIndentedLine(String.format("for (int r%d = 0; r%d < BOARD_SIZE; r%d++) {", nestingLevel, nestingLevel, nestingLevel), indentLevel + 1);
        printIndentedLine(String.format("queenRows[%d] = r%d;", nestingLevel, nestingLevel), indentLevel + 2);
        // Recursively write the next loop level to the output file
        generateLoop(levelsRemaining - 1, indentLevel + 2);
        printIndentedLine(String.format("queenRows[%d] = NO_QUEEN;", nestingLevel), indentLevel + 2);
        printIndentedLine("}", indentLevel + 1);
        printIndentedLine("}", indentLevel);
    }

    public static void main(String[] args) {
        // Get board size from first command line argument
        try {
            boardSize = Integer.valueOf(args[0]);
        } catch (NumberFormatException e) {
            System.out.println("First argument must be an integer board size.");
            System.exit(1);
        }

        // Check for valid board size
        if (boardSize <= 0) {
            System.out.println("Board size must be greater than or equal to 1.");
            System.exit(1);
        }

        // Get filename from second command line argument
        String fileName = args[1];
        // Ensure that we are writing to a valid Java file
        if (!(fileName.endsWith(".java"))) {
            System.out.println("The second argument must be a valid Java file name.");
            System.exit(1);
        }
        // Strip file extension to get class name
        String className = fileName.substring(0, fileName.length() - 5);

        // Initialise writer
        try {
            out = new PrintWriter(new File(fileName));
        } catch (IOException e){
            System.out.println("Second argument must be a valid file name.  This file may not be accessible, or you " +
                               "may not have permission to write to the specified file.");
            System.exit(1);
        }

        // Write class header
        out.println(String.format("public class %s {", className));
        out.println("  private final static int NO_QUEEN = -1;");
        out.println("  private static int numSolutions = 0;");
        out.println(String.format("  private final static int BOARD_SIZE = %d;", boardSize));

        out.println();
        out.println("  public static boolean queensAreSafe(int[] board) {\n" +
                    "    // Check all combinations of queen positions\n" +
                    "    for (int i = 0; i < BOARD_SIZE; i++) {\n" +
                    "      // Break once a row has been found to contain no queens\n" +
                    "      if (board[i] == NO_QUEEN)\n" +
                    "          break;\n\n" +
                    "      for (int j = i + 1; j < BOARD_SIZE; j++) {\n" +
                    "        if (board[j] == NO_QUEEN)\n" +
                    "          break;\n\n" +
                    "        // If two queens in same row, queens are not safe\n" +
                    "        if (board[i] == board[j])\n" +
                    "          return false;\n\n" +
                    "        double queenSlope = (double) (board[j] - board[i]) / (j - i);\n" +
                    "        // If two queens are on the same diagonal, queens are not safe\n" +
                    "        if (queenSlope == 1.0 || queenSlope == -1.0)\n" +
                    "          return false;\n" +
                    "      }\n" +
                    "    }\n\n" +
                    "    return true;\n" +
                    "  }");

        out.println();
        out.println("  public static void printSolution(int[] board) {\n" +
                    "    StringBuilder sb = new StringBuilder();\n" +
                    "    for (int r = 0; r < BOARD_SIZE; r++) {\n" +
                    "      for (int c = 0; c < BOARD_SIZE; c++) {\n" +
                    "        if (board[r] == c)\n" +
                    "          sb.append('q');\n" +
                    "        else\n" +
                    "          sb.append('.');\n" +
                    "      }\n" +
                    "      sb.append(\"\\n\");\n" +
                    "    }\n" +
                    "    System.out.println(sb.toString());\n" +
                    "  }");

        out.println();
        out.println("  public static void main(String[] args) {");
        out.println("    // We store the positions of all queens as follows: array index = column, value at index = row");
        out.println("    int[] queenRows = new int[BOARD_SIZE];");
        out.println("    for (int i = 0; i < BOARD_SIZE; i++)");
        out.println("      queenRows[i] = NO_QUEEN;");
        out.println();

        // Begin generating loops
        generateLoop(boardSize, 2);

        // Finish class
        out.println("    System.out.printf(\"Total number of solutions: %d\\n\", numSolutions);");
        out.println("  }");
        out.println("}");

        // Avoid unclosed file handler (not possible to be null, but we shall appease the Java compiler anyway)
        if (out != null)
            out.close();
    }
}