Course:CPSC312-2024/Nurikabe
Authors: Justin Burden, Nia Tzvetkova, Ramit Brata Biswas
(This is actually a sudoku puzzle, our plans changed but we cannot edit the title)
What is the problem?
Sudoku is logical puzzle game of Japanese origin. Its a 9x9 grid of 9 boxes, and every box, row, and column must be filled with the digits 1-9, without repeats. A starting grid has some, but not all of the numbers filled out, and it is expected to have enough clues to yield a unique solution.
We plan to implement a playable version of Sudoku in Haskell, including a simple interface in the terminal.
What is the something extra?
Like any sudoku software, our game has preloaded boards and allows for the user to select a difficulty and fill out the puzzle. As something extra, we also implemented a user input board feature, a hint generator, and a solver.
- User input boards: Our program comes with preloaded boards taken from the internet (sudoku.com), but the user can also upload a .txt file of a board they wish to use. If the uploaded board is invalid or the file name is incorrect, the program throws an exception and tells the user their file is invalid.
- Solver: When the program is started and a puzzle is chosen, it first tries to solve the puzzle using backtracking search. If it's not solvable it gives an error and if it's solvable it stores the solution. The user can also just request for the whole board to be solved by the program.
- Hint generator: Then, at any point in the game, the player can ask for a hint by specifying which cell they're stuck on, and the game will fill out the correct number for it.
What did we learn from doing this?
What worked well:
- Solver: Like we expected, the solver turned out to be pretty simple and straightforward to write. Haskell's pattern matching made it easier to break down the task into just writing a few one line validators, then letting the recursion handle the rest with backtracking. The code is easy to read and follow, there aren't too many cases or nested if statements (unlike my experience with coding a similar solver program in Python a few years ago).
- Console UI: We initially assumed that Haskell is a language primarily used only for algorithms and more math-y problems (like the ones that we write in class and during exams). However, while working on the command line interface, we realized that Haskell's IO Monad makes code that we'd initially assume to be more suited to procedural languages work quite well with the functional parts of the code, while keeping the rest of the program's features intact. If anything, using Haskell made the code cleaner and easier to debug since the type system ensured we could remove wrong code as it showed up.
What didn't work as well:
- GUI: Initially, we really wanted to also implement a basic GUI along with this program. However, we found this to be very difficult to do in Haskell. Haskell doesn't have many libraries, and it would've been much easier to implement the GUI in something like Python or Java. In our research we found one option (called threepenny), but we found it complicated enough to use that we decided it's better to shift our focus onto adding more features to the game and keeping it simple with a console UI instead.
- Nurikabe: Our initial plan was to do a Nurikabe game instead of Sudoku. Nurikabe is also a Japanese logic grid-type puzzle (basically some cells are numbered, then the goal is to shade some cells in the grid so that each numbered cell to be part of an unshaded contiguous piece of size equal to its number). Besides the issue that this would also likely need to involve a GUI, we found it very difficult to figure out what data structures to come up with for this project. Haskell felt too rigid with its strong type system, and we couldn't figure out how to join the fact that a state needs to contain the information that every cell is either numbered, shaded or unshaded, with this idea of several chunks of orthogonally adjacent cells being considered as one "island" of a certain size. We think an objected oriented language like Java would probably be better for this task because we can have something like an "island" class that contains "cell" subclasses. Also, there would be a lot more libraries we can take advantage of.
Overall, we felt that functional programming was a very good choice for a Sudoku project. Haskell's lazy evaluation strategy makes us not have to worry too much about optimizing our solving algorithm to reduce its runtime. The strong typing made it a lot easier than expected to implement and debug a basic UI (something that in our experience with other languages is usually very messy). However, for games that have more rules or are geometrically more complex (i.e. not just grids and squares), we recognize that some Haskell features (like its strong typing) or the fact that it's not object oriented would pose a challenge and make the programming task more complicated than it needs to be.
Work division
Justin: solver, data definitions
Ramit: user interface, custom board feature
Nia: wiki, fixing issues