**Tags**

Assignments, C-fu, CS50, CS50 hacker4, CS50 pset4, Harvard CS50, Programming in C, Sudoku game, Sudoku Solver

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.

## pset4

### 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.

## hacker4

### 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.

Enjoy!