C++ Sudoku Solver Using Pointers

As part of my Advanced Programming course at the University of Hull, I was tasked to create a program which can solve a Sudoku puzzle*. This program was required to read in a plain text file which defined the puzzle and then immediately solve it as quickly as possible. While it may not have been the most intuitive or user-friendly design, the point of the program was to implement a given data structure using C++ pointers to define the puzzle.

The program reads in the puzzle and stores each ‘square’ of the puzzle as a ‘cell’ object, which holds the value of the cell, whether it was given or not and a list – known as the ‘candidate list’ – which holds every possible value that cell could be. Each cell is then referenced by an array of pointers which define each row, column and block of the puzzle. This allowed me to easily implement a solving algorithm which uses, basically, a process of elimination to find the solution to the puzzle.

If the given puzzle is solvable, this program can solve it with a 100% success rating in my testing. Thanks to the efficiency of the data structure using pointers, my program can solve a puzzle with an average of 0.000086 seconds and 0.000123 seconds at the slowest**.

My code is available for download if you want to examine it for yourself and see the program in action.


* The algorithm and data structure were designed by Dr J Rayner of the University of Hull and given to me so I could implement it as part of university coursework.

** Timing is based on my own testing and was recorded by the program as a floating point variable to 6 decimal places.

Categories:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s