Course:CPSC312-2023/Sudoku
Authors: Sayan Saha, Tate Zingle
What is the problem?
We created 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?
Our initial idea for an extra component was a hint generator. Since we had a solution board to go off of for each game board, this ended up being quite manageable. To add on to this initial idea, we created a backtracking solver, which returns a list of all possible solutions for a board. 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 (as mentioned in the ‘What we learned’ section).
What did we learn from doing this?
By doing this project we became much more comfortable working with IO types as well as working with randomness. It was a very steep learning curve figuring out how to manage the changing types, as well as how to pass IO generated variables to functions that didn’t take IO types. Once we established that, the randomizer elements of our project went much more smoothly!
It was also an adjustment to make a large project that worked without side effects, since in the past we had largely worked with global variables that can be constantly modified, especially in game projects like this one. We had to find a way to update our boards through recursion instead.
In terms of our board generation, we went through a few different ways of building one before we found a technique that made a board efficiently. We found that working off of a set board, and then scrambling it with a randomizer to create a solution, and then removing numbers with a randomizer to create a game board was the best approach. Our initial approach was to randomly create a board, which took much too long once the possible numbers in a row became limited, and to erase elements systematically by checking if once each element was erased the board would still be solvable. Once we added a fixed board whose elements we randomly moved, and a random eraser that randomly checks each element, we found that things ran much more quickly.
What is the bottom line?
Overall we felt that functional programming was partially suitable. Using it for the main game part was a good way to keep track of our board states and to make sure that the only changes being made to the boards were ones directly caused by the player’s choice at each turn.
However, we felt that functional programming may not have been the best choice for our board generators. We had functions with many nested do and if statements, as well as recursion, which made our code very clunky, both in terms of runtime and debugging. If we were using an imperative language, this aspect of our game would have been much more efficient. This was a particular issue for switching elements in the board (which was the first step of our board shuffling algorithm), checking elements one by one for the initial eraser algorithm (though we switched to a random one for a more efficient runtime), and in the rest of our board shuffling functions, where we have to create and return a newBoard each time we made a change.
An imperative language would have also made managing random numbers much easier. We really struggled with finding ways to work around the changing types and the variability that random numbers offer (as mentioned in the 'What we learned' section). Had we used an imperative language, integrating these numbers into our code would have been much easier.
All in all, when the game was relying on predetermined steps and processes that a player could select, we found functional programming to be very helpful, and we found it to be a bit of a hindrance when dealing with the more variable aspects of our program.