CPSC312-2023: Sudoku (Prolog)
What is the problem?
We are going to be repeating our Project 1. We will aim to create an interactive Sudoku game where the player is presented with a partially filled game board (of options 'easy', 'medium', and 'hard'), and then can fill in the solution.
What is the something extra?
We created a hint generator, so that the player can ask for a hint that fills in a number for them when they are stuck. They can then choose to continue the game, or ask for another hint. We also implemented a solver that has functionality to generate all possible solutions to a given Sudoku board. This solver was implemented using the cplfd library and Prolog constraints made the solver quite fast compared to a simple backtracking solver written in Haskell. We also implemented a random board generator that uses a solved base board to generate a new Sudoku game in order to increase the randomness of the boards that we gave the player.
What did we learn from doing this?
As in Project 1, we once again had to adapt to working without side effects. Unlike Project 1, beyond simply passing a new board every time we modified it, we also had to make sure that every time we modified the board, the unmodified values were limited to the ones that were in the previous board. Since Prolog only limits results to what must be true, we had to build a lot of guards to confirm that we were only modifying one or two values while keeping the rest of them the same. This contributed significantly to the runtime when generating and emptying boards, which reinforced the importance of helper functions in distilling and simplifying code.
Furthermore, having to work in basic true/false terms to build an entire game helped us understand the levels of complexity that goes into programming in other languages. Where we instinctively wanted to do a complex process in one line of code, we were forced to spell out exactly what we wanted to see. Although perhaps more tedious than other languages, it gave us a much more in depth understanding of what was actually happening every time we modified a board.
It also reminded us that there are many opportunities to simplify our work; in many scenarios where we would not have simplified, we were forced to by the constraints of Prolog. This kept us from overcomplicating the way we went about building our game; we weren’t able to add significant complexity without also contributing to the runtime, so we had to find ways to build our program efficiently.
We also had some difficulty with the fact that Prolog doesn’t have a null case. Initially in our solver we wanted to represent empty slots as actually empty, but since the closest Prolog has to empty is _, which can be anything, by using this our emptier simply just returned the solution board we had sent to be emptied. To solve this, we wrote a helper that converts the 0's we use as place holders to free variables (_) when we are trying to find solutions for the board. This way our emptier functions successfully, but we are also able to solve it.
What is the bottom line?
While we did have the benefit of having a deeper understanding of what was happening in our system, Prolog posed a real challenge for us. Having to create an entire database that builds true/false statements upon themselves to eventually create the desired function means that each complex action we needed to do had many nested calls within it. This created high runtimes, which we would have liked to avoid.
Overall, Prolog gave us the benefit of understanding our program and manipulating it on the most basic level. However, it had the drawback of not allowing us to easily change boards without going through a series of calls that contributed to significant runtime, as well as the difficulty of not having a null value, which would have been ideal for representing empty spaces.
In terms of implementing the solver, while we initially had a lot of difficulty as we were trying to implement it using a backtracking algorithm similar to our Haskell solution, our final implementation worked really well. The cplfd library made things easy in the end and allowed for a concise solution that makes use of the labeling functionality in the library and Prolog constraints to produce solutions to Sudoku boards really quickly. Based on this, we believe that Prolog would be a good fit for similar search problems and solvers. However, input/output is pretty clunky to work with in Prolog which makes it unideal for implementing interactive games like we did.