Course: Harvard’s CS50
Problem Set 4: Sudoku
For this problem set you get to:
- Learn to use the ncurses library.
- Make a usable Sudoku game.
- (hacker4:) Drive home the usage of multiple source files in a single program.
- (hacker4:) Implement an algorithm that solves a sudoku game.
The problem set’s pdf covers a lot about the ncurses library that you should pay attention to. Although this assignment barely uses some of the basic functionality the ncurses library provides, You should take a look at the recommended reading, http://tldp.org/HOWTO/NCURSES-Programming-HOWTO/; a cursory look at the very least. — Some of the demo programs in the HOWTO are actually interesting, so dig in and enjoy.
The tough part (in pset4) is implementing a checkboard() function that checks for bad user input on the board. Everything else is pretty easy.
Here’s the source:
In order to complete hacker4, you’re going to need to have a working Sudoku game anyways, so do pset4 first.
There are many resources about this topic. You can achieve a Sudoku solver via many different approaches, ie. focus on the logic more -vs- focus on a search algorithm more, or just plain old brute force.
I chose to use the logic outlined in http://www.eddaardvark.co.uk/sudokusolver.html, slightly modified.
Excerpt from sudoku_solver.c:
/* * Functions here are used to solve the sudoku puzzle automatically * Follow the logic outlined in http://www.eddaardvark.co.uk/sudokusolver.html , * partially modified. we only look for one solution, and phase3 is split into two phases. * phase 1, Applying the Given Numbers * phase 2, Looking for Singletons * phase 3, Pairs (a) (frequency 2 pairs) * phase 4, Pairs (b) (matching pairs) * phase 5, Eliminating Bad Guesses. -- as in: guess until solved. */
sudoku.c (view | download)
sudoku.h (view | download)
sudoku_solver.c (view | download)
sudoku_solver.h (view | download)
dm8log.c (view | download)
dm8log.h (view | download)
…or download hacker4_sudoku.zip.
You’ll need to get debug.bin, n00b.bin and l33t.bin from the problem set’s distribution source package.
Use something like this to build:
gcc.exe -std=c99 -Wall -Wformat=0 -c -g -Werror -I/usr/include/ncurses -MMD -MP -MF sudoku_solver.o.d -o sudoku_solver.o sudoku_solver.c gcc.exe -std=c99 -Wall -Wformat=0 -c -g -Werror -I/usr/include/ncurses -MMD -MP -MF dm8log.o.d -o dm8log.o dm8log.c gcc.exe -std=c99 -Wall -Wformat=0 -c -g -Werror -I/usr/include/ncurses -MMD -MP -MF sudoku.o.d -o sudoku.o sudoku.c gcc.exe -std=c99 -Wall -Wformat=0 -o hacker4_sudoku sudoku_solver.o dm8log.o sudoku.o -L/lib/ncurses/ -lncurses --or-- (the above is equivalent to) this: gcc -ggdb -std=c99 -Wall -Werror -Wformat=0 -I/usr/include/ncurses -o sudoku sudoku.c dm8log.c sudoku_solver.c -L/lib/ncurses/ -lncurses
The paths given are valid for Cygwin; you may have to change them for other systems, or remove them altogether — you should not need them at all under Linux. Also, Cygwin tends to favor ncursesw (wide chars) over the regular ncurses, and you can use that instead, it’ll work.