Tags

, , , , , , , ,

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.

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!

Advertisements