From UBC Wiki


Authors: Tristan MacKinlay, Al Smith, Rob Willoughby

What is the problem?

For people who are stuck on their morning sudoku, we will create a program to help them cheat so they can finish it and get on with their day. The basic version will be able to take in a 9x9 board that is partially solved and will be able to produce all possible solutions to it.

What is the something extra?

There are two 'something extras' we are planning on implementing. The first is the ability to produce all possible valid Sudoku boards (all 6,670,903,752,021,072,936,960 of them). The second is to expand the traditional 9x9 solver to a larger board as well (potentially a 25x25). We may also attempt to make a solver that will work with a board of size n^2.

What did we learn from doing this?

The biggest takeaway from the project was around debugging Prolog. This proved more difficult than expected since if there was an invalid predicate in the code it would just return False rather than outputting an error. The Prolog debug mode was also finicky to use and did not provide as much information as we expected. Additionally, we attempted to create a solver that could work for an arbitrary size of n^2. We were unable to do this given issues around how domains were represented in the Prolog package clfpd. While using this package made solving a defined board easier (mainly around having a defined domain and the ability to check that each element in the domain only appeared once) it actually made solving for a board of size n^2 impossible. Prolog is also a really interesting language to try and create all valid Sudoku boards in given the implicit backtracking happening. This means that it only needs to find one possible answer to start outputting results rather than finding all possible answers.

Links to code etc