, , , , , , , ,

Sudoku Snapshot -- Game auto-solved in ~1 second

Course: Harvard’s CS50

Problem Set 4: Sudoku

pset4/hacker4 is another fun and interesting assignment.

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.


Implement sudoku.

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:

dm8log.c (view | download)
dm8log.h (view | download)
sudoku.c (view | download)
sudoku.h (view | download)
…or download pset4_sudoku.zip.



Sudoku Solver

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.