Nonogram-SAT-Mappings

This project is incomplete for the purposes of mathematical proofs and Nonogram solving. It was sufficient for my coursework, which did not require either of those in their entirety.

For an explanation of the purpose of this project, read the included paper, "Exploring the NPC Space with Nonograms".

Included code files:

• nonogram.py
• sat.py
• sat_to_nonogram.py
• nonogram_to_sat.py

You must have all 4 Python files in the same directory in order to run them.

Requirements:

• Python 3.11.0
• Python 3.11.0 modules:
• NumPy

How to Run:

nonogram.py:

From the directory that nonograms.py is in, run the following from the command line without quotation marks: "python nonograms.py" In order to enable debug mode, run the following command instead: "python nonograms.py debug". Debug mode will print extra information during program execution to the terminal. In order to alter the sanity coefficient, run the following command "python nonograms.py (anything) ". Increasing the sanity coefficient above its default value of 1 may increase runtime for no benefit. Decreasing the sanity coefficient below its default value of 1 may cause the program to exhibit unintended behavior. A sanity coefficient below 1 will probably cause the heuristic solving algorithm to exit prematurely, making the partial brute force algorithm activate sooner. This may also increase runtime.

Select your option when the prompt appears:

1. Create a random nonogram puzzle. You will be prompted for the n and m dimensions. After inputting the n and m dimensions, the program will print the information for the randomly generated puzzle, including the clues and key. Then, the heuristic solving algorithm will attempt to solve the puzzle by looking only at the clues (not the key). If the heuristic solving algorithm fails, you will be asked if the program should attempt a partial brute-force solution to the puzzle. If you input "y", the program will attempt a brute-force solution to the puzzle. If you input "n", the program will not attempt to solve the puzzle any further. Then, you will asked if you would like to write the puzzle to a file. If you input "y", you will be prompted for a filename. Include a name and extension, if you would like. The file will be saved in the directory of nonograms.py. If you input "n", the program will return to the start of the execution loop.
2. Read a nonogram puzzle from a file. You will be prompted for the filename. If the file is loaded successfully, the solving process will work the same way as option 1 works.
3. Write all possible nonograms of a given size. You will be prompted for the n and m dimensions. BE WARNED: The program will attempt to generate a number of puzzles and write a number of files equal to 2^(n*m). The files will all be written to a directory in the same folder as nonograms.py. The folder will be named "nxm" where n and m are the dimensions given. WARNING: The runtime of this option increases exponentially!
4. Solve all possible nonograms of a given size. You will be prompted for the n and m dimensions. The puzzles must be generated by option 3. The expected directory name and puzzle names are the same as generated by option 3. WARNING: The runtime of this option increases exponentially! 5: Input an x dimension, a y dimension, and a decimal number. The decimal number will be converted to a binary number, which will in turn be used to generate a puzzle with the binary number as its key. This option is useful for creating a puzzle with a specific key. The clues are automatically populated by the program. Then, you will asked if you would like to write the puzzle to a file. If you input "y", you will be prompted for a filename. Include a name and extension, if you would like. The file will be saved in the directory of nonograms.py. If you input "n", the program will return to the start of the execution loop.

The prompt will repeat until an option other than 1, 2, 3, or 4 is selected. At that point, the program will halt execution.

sat.py:

From the directory that sat.py is in, run the following from the command line without quotation marks: "python sat.py " should be a single string with no spaces. It should refer to the filename of a .dat file containing a SAT in the format of CS 470 Project 3's SAT problems. If the file is in a different directory than the directory sat.py is in, provide the full filepath. No spaces are allowed. The filepath should like within the directory of sat.py.

The program will print the SAT, the satisifiability of the problem, and every combination of values that satisfy the SAT (if any).

sat_to_nonogram.py:

From the directory that sat_to_nonogram.py is in, run the following from the command line without quotation marks: "python sat_to_nonogram.py " should be a single string with no spaces. It should refer to the filename of a .dat file containing a SAT in the format of CS 470 Project 3's SAT problems. If the file is in a different directory than the directory sat_to_nonogram.py is in, provide the full filepath. No spaces are allowed. The filepath should like within the directory of sat_to_nonogram.py.

The program will print the SAT and the satisifiability of the problem. It will then print the X clues, Y clues, and key of the nonogram generated from the SAT. Then, you will asked if you would like to write the puzzle to a file. If you input "y", you will be prompted for a filename. Include a name and extension, if you would like. The file will be saved in the directory of nonograms.py.

nonogram_to_sat.py:

Arguments:

1. write?
2. mode
3. x
4. y

Argument 1 should be set to "true" or "1" to write out the generated SAT to a file. Some variants are accepted, but the default value is False. Argument 2 should be set to , "of", or "upto". runs the program on a single nonogram file. "of" runs the program on all nonograms of the size set by arguments 3 and 4. "upto" runs the program on all nonograms up to the size set by arguments 3 and 4. If argument 2 is set to "of" or "upto", the program expects the files to be present in the format generated by nonogram.py's generate all option. This includes both the filepath and filename. Arguments 1 and 2 are mandatory in all cases. If mode is set to a filename, arguments 3 and 4 are also mandatory. Arguments 3 and 4 are the x and y dimensions of the nonograms, respectively.

The program runs the nonogram to SAT conversion on every nonogram selected by the above arguments. WARNING: For larger puzzles, the runtime may be extremely high. If writing to file was selected, the program will print the filepath of every created file.

Performance Tests for nonogram.py:

Heuristic Approach n*m: pass/total

• 1*1: 2/2
• 1*2: 4/4
• 1*3: 8/8
• 1*4: 16/16
• 2*2: 14/16
• 2*3: 52/64
• 2*4: 184/256
• 3*3: 384/512
• 3*4: 2572/4096
• 4*4: 30273/65536

Heuristic Approach with Partial Brute-Force n*m: pass/total, average brute-force attempts per puzzle, runtime

• 1*1: 2/2, (none), <0.01s
• 1*2: 4/4, (none), <0.01s
• 1*3: 8/8, (none), <0.01s
• 1*4: 16/16, (none), <0.01s
• 2*2: 16/16, 7.5, <0.01s
• 2*3: 64/64, 7.5, 0.02s
• 2*4: 256/256, 25.5, 0.13s
• 3*3: 512/512, 20.6, 0.24s
• 3*4: 4096/4096, 108.9, 7.6s
• 4*4: 65535/65535, 2448.6, 3354.5s

The heuristic method is not always capable of extending a partially complete clue based on the cells that are already filled. I estimate that another 30% of the heuristically unsolved puzzles could be solved heuristically with this change. The heuristic method performs best when the clues permit trivial solving of clues. Small puzzle dimensions also increase the probability of success greatly. These reasons are elaborated upon in the paper.