CSCI-1200 Data Structures - Fall 2024 Homework 6 - Recursive Kurotto Solver
CSCI-1200 Data Structures — Fall 2024 Homework 6 — Recursive Kurotto Solver
In this homework we will develop a solver for a paper-and-pencil puzzle game named Kurotto. The input to Kurotto is a 2D rectangular grid where all the cells are initially water. Some of the cells in the grid are labeled with a non-negative integer. To solve the puzzle we will shade some of the un-numbered cells in the grid. Each cell we shade becomes land. Land cells that share a horizontal or vertical edge are joined to form islands. Cells that have numbers cannot be shaded, they will remain water. A Kurotto puzzle is solved if each numbered cell is touching (along horizontal or vertical edges) islands whose area sums exactly to the number in that cell. For our homework, we will work with inputs that may have no solutions, exactly one solution, or multiple solutions. The small example below has 3 different solutions! One of the solutions has 5 islands and the other two solutions have 3 islands.
4444
23232323 10101010
You are encouraged to play through example puzzles so you understand the rules. First focus on verifying that a proposed solution of shaded cells is indeed a complete and valid solution. Then think about how you create a solution by filling in shaded cells yourself. Even though the rules are very simple, this puzzle is surprisingly difficult! As you play, think about how you as a human solve these puzzles. As the puzzles grow larger how and why does it become more challenging? Can you generalize your method of finding a solution so you can teach a friend how to play and ultimately, “teach” the computer to play? Here is a link with more information about the game and some medium and larger puzzles:
https://www.gmpuzzles.com/blog/kurotto-rules-and-info/
IMPORTANT NOTE: You may not search for, study, or use any code or techniques related to existing solvers for this puzzle game. Please carefully read the entire assignment and study the examples before beginning your implementation.
Command Line Arguments & Input/Output
Your program will accept one or more command line arguments. The required first argument is the name of a puzzle board file. The input file for the puzzle in the diagrams above is shown on the right. The board is contained in a simple ASCII art frame. The space character represents water cells. The ’#’ character represents land. Digits ’0’ through ’9’ represent the numbered cells 0-9, and then we switch to letters: ’a’=10, ’b’=11, etc.
+-----+ |4| || |23| |1 0 | +-----+
The output of your program will print to std::cout. We can use file redirection ( > output4.txt ) on the command line to write scoop up the output and save it to a file. See the provided output files for sample output from each of these command lines. If no other command line arguments are specified, your program should search for and print a single valid solution to the puzzle (if any exists). If there are multiple solutions, your code can print any solution. If the optional --find_all_solutions command line argument is specified, your program should output all solutions, they can be printed in any order.
./kurotto_solver.out input4.txt > output4.txt
./kurotto_solver.out input4.txt --find_all_solutions > output4_all.txtHowever, before you tackle finding one or all solutions, it is important that you can identify all of the islands in a proposed/possible solution. Since the input and output file formats match, we can actually feed a sample output file as input to the program and then compute and print information about the solution board. The optional command line argument --no_solver will skip the search to find solutions and instead just analyze the shaded land cells already on the board.
When the optional command line argument --print_islands is specified, your program should collect the land cells within the diagram, group them into islands, and then print this information. An example of this output is shown on the left. Note that you can print the islands in any order, and likewise the col, row grid positions within each island can be printed in any order.
./kurotto_solver.out output4.txt --no_solver --print_islands > output4_print_islands.txt
./kurotto_solver.out output4.txt --no_solver --print_check_solution
> output4_print_check_solution.txt
./kurotto_solver.out input4_buggy.txt --no_solver --print_check_solution
> output4_buggy_print_check_solution.txt
+-----+
|#4## |
|# #|
| 2#3#|
|1# 0 |
+-----+
ISLAND COUNT = 5
ISLAND:
ISLAND:
ISLAND:
ISLAND:
ISLAND: (1,3)
(0,0) (0,1)
(2,0) (3,0)
(4,1) (4,2)
(2,2)
+-----+ Once you have correctly
+-----+
|#4## |
|##|
|23#|
|1#0|
+-----+
Location (1,0) = 4
Location (1,2) should be 2 is 1
Location (3,2) should be 3 is 2
Location (0,3) = 1
Location (3,3) = 0
Puzzle is NOT SOLVED
|#4## |
|# #|
| 2#3#|
|1#0| is satisfied. When the optional
+-----+ command line argument
Location (1,0) = 4
Location (1,2) = 2
Location (3,2) = 3
Location (0,3) = 1
Location (3,3) = 0
Puzzle is solved
--print_check_solution is provided the program should output information about each numbered location on the board and the total area of adjacent islands.
identified the islands on the board, you can proceed to verify that each numbered cell
And finally, here is an example command line using the final
--print_solution_count. Be sure to study the sample input and output files on the website.
./kurotto_solver.out input4.txt --find_all_solutions --print_islands
--print_check_solution --print_solution_count > output4_all_print.txt
We provide basic code to handle the required and optional command line arguments and a function to read the puzzle board. You may modify the provided code as necessary to complete the assignment.
Additional Requirements: Recursion & Big O Notation
You must use recursion in a non-trivial way in your solution – e.g., for detecting islands, for shading land blocks, and for enumerating all possible solutions to the puzzles. As always, we recommend you work on this program in logical steps. IMPORTANT NOTE: This problem is computationally expensive, even for medium-sized puzzles! Be sure to create your own simple test cases as you debug your program.
As always, use good coding style when you design and implement your program. You are encouraged but not required to write one or more new classes for this assignment. Make thoughtful decisions about how to efficiently use the STL classes we have discussed in lecture and lab.
