Download Shareware and Freeware Software for Windows, Linux, Macintosh, PDA

line Home  |  About Us  |  Link To Us  |  FAQ  |  Contact

Serving Software Downloads in 976 Categories, Downloaded 36.962.409 Times

A Sudoku Solver in C 1.11

  Date Added: January 07, 2010  |  Visits: 2.299

A Sudoku Solver in C

Report Broken Link
Printer Friendly Version


Product Homepage
Download (182 downloads)

A Sudoku Solver in C is a console-based Linux program, written in C language, that solves Su Doku puzzles using deductive logic. It will only resort to trial-and-error and backtracking approaches upon exhausting its deductive moves. Puzzles must be of the standard 9x9 variety using the (ASCII) characters 1 through 9 for the puzzle symbols. Puzzles should be submitted as 81 character strings which, when read left-to-right will fill a 9x9 Sudoku grid from left-to-right and top-to-bottom. In the puzzle specification, the characters 1 - 9 represent the puzzle givens or clues. Any other non-blank character represents an unsolved cell. The puzzle solving algorithm is home grown. I did not borrow any of the usual techniques from the literature, e.g. Donald Knuths "Dancing Links." Instead I rolled my own from scratch as a personal challenge. As such, its performance can only be blamed on yours truly. Still, I feel it is quite fast. On a 333 MHz Pentium II Linux box it solves typical medium force puzzles in approximately 800 microseconds or about 1,200 puzzles per second, give or take. On an Athlon XP 3000 it solves about 6,600 puzzles per sec. (Solving time is dependent upon degree of difficulty, so YMMV.) Description of Algorithm: The puzzle algorithm initially assumes every unsolved cell can assume every possible value. It then uses the placement of the givens to refine the choices available to each cell. I call this the markup phase. After markup completes, the algorithm then looks for singleton cells with values that, due to constraints imposed by the row, column, or 3x3 region, may only assume one possible value. Once these cells are assigned values, the algorithm returns to the markup phase to apply these changes to the remaining candidate solutions. The markup/singleton phases alternate until either no more changes occur, or the puzzle is solved. I call the markup/singleton elimination loop the Simple Solver because in a large percentage of cases it solves the puzzle. If the simple solver portion of the algorithm doesnt produce a solution, then more advanced deductive rules are applied. Ive implemented two additional rules as part of the deductive puzzle solver. The first is subset elimination wherein a row/column/region is scanned for X number of cells with X number of matching candidate solutions. If such subsets (or tuples) are found in the row, column, or region, then the candidates values from the subset may be eliminated from all other unsolved cells within the row, column, or region, respectively. The next deductive rule examines each region looking for candidate values that exclusively align themselves along a single row or column, i.e. a vector. If such candidate values are found, then they may be eliminated from the cells outside of the region that are part of the aligned row or column. Note that each of the advanced deductive rules calls all preceeding rules, in order, if that advanced rule has effected a change in puzzle markup. Finally, if no solution is found after iteratively applying all deductive rules, then we begin trial-and-error using recursion for backtracking. A working copy is created from our puzzle, and using this copy the first cell with the smallest number of candidate solutions is chosen. One of the solutions values is assigned to that cell, and the solver algorithm is called using this working copy as its starting point. Eventually, either a solution, or an impasse is reached. If we reach an impasse, the recursion unwinds and the next trial solution is attempted. If a solution is found (at any point) the values for the solution are added to a list. Again, so long as we are examining all possibilities, the recursion unwinds so that the next trial may be attempted. It is in this manner that we enumerate puzzles with multiple solutions. Note that it is certainly possible to add to the list of applied deductive rules. The techniques known as "X-Wing" and "Swordfish" come to mind. On the other hand, adding these additional rules will, in all likelihood, slow the solver down by adding to the computational burden while producing very few results. Ive seen the law of diminishing returns even in some of the existing rules, e.g. in subset elimination I only look at two and three valued subsets because taking it any further than that degraded performance. Whats New in This Release: - Code optimization has resulted in a 30% increase in speed..

Requirements: No special requirements
Platforms: Linux
Keyword: C Is C Language Deductive In C Linux Program Puzzle Puzzles Solver Su Doku Puzzles Sudoku Sudoku Solver Written In
Users rating: 0/10

License: Freeware Size: 25.6 KB
A SUDOKU SOLVER IN C RELATED
Science  -  PyDespike 1.0.0
PyDespike is a cross platform (Windows, Mac, Linux) program written in Python using the PyQt and PyQwt libraries used to graphically process (despike) raman or other spectroscopic data in an efficient manner.
3.21 MB  
Development Tools  -  C# Matlab Program Launcher 1.0
C# Matlab Program Launcher v1.1Amitabh Vermaamitabh@amitabhverma.comThis C# code provides a sleek loader that would execute your Matlab script or function without the requirement to launch Matlab manually. **This loader requires Matlab to be...
839.68 KB  
Business  -  Delta Code 2.0
The Delta code is an nonlinear aeroelastic solver written in fortran 90. At the momentonly vortex lattice aerodynamics is available but the hope is for a higher fidelity aerodynamicmodel to be developed for use in the current code. Linux and Unix.
5.42 MB  
Miscellaneous Communications Tools  -  HPTalx 1.3.1a
This is HPTalx, a HP Calculator PC communications program for Linux, initially written by Bruno Barberi Gnecco, extended by Rafael Ostertag and released under the GNU Public License. Use it at your own risk; the authors are not responsible for...
204.8 KB  
Business  -  Getbinnews 1.0.9
Getbinnews is a newsreader developed in C using the GTK user interface (for Linux, FreeBSD and OpenBSD OS) . The aim of Getbinnews is to extract in some newsgroups a binary file (mp3, jpg, gif,mpg, asf, avi, divx...) splited in articles with...
204.8 KB  
Database Tools  -  CLucene - a C++ search engine 2.3.3.4
CLucene is a C++ port of Lucene: the high-performance, full-featured text search engine written in Java. CLucene is faster than lucene as it is written in C++.
2.14 MB  
Development Tools  -  LibTPT 1.0
TPT is a template scripting language implemented in C , designed to be integrated with C programs. It is intended as a fast, lightweight replacement for fullblown scripting languages, providing an easy interface for embedding TPT scripts in C...
 
Games  -  C-doku 0.4
C-doku is a logic game written in C based on the well known rules of the Sudoku.
4.13 MB  
Libraries  -  mGSTEP 0.558
mGSTEP project is an core elements in NeXTs (now Apple) OPENSTEP/Cocoa Objective-C class libraries implementation. The principal design goal is the development of a modular application development framework suitable for use in embedded devices...
655.36 KB  
Arcade Style Games  -  RocksnDiamonds 3.2.3
RocksnDiamonds is an arcade style game for Linux, Windows, Mac OS X and DOS in the tradition of: "Boulder Dash" (C 64) "Emerald Mine" (Amiga) "Supaplex" (Amiga/PC) "Sokoban" (PC). Rocks'n'Diamonds Homepage
2.9 MB  
NEW DOWNLOADS IN GAMES, PUZZLES
Games  -  Forge Of Empire 3
In the browser game Forge of Empires you can build your own city and experience all of history from its perspective - from the stone age on through the centuries. Explore new technologies that ring in a new era. Leave a mark with unique,...
4.26 MB  
Games  -  JediMUD 1.0
JediMUD is a Multi User Dungeon (MUD) game. In other words, it's a text-based role-playing game with users from all over the world. During your travels, you will encounter characters run by real people, challenge the computer-generated...
92.16 KB  
Games  -  WorldForge::Eris 1.3.18
Eris is designed to simplify client development (and promote code reuse) by providing a common system to deal with the back-end Atlas tasks. Notably, Eris encapsulates most of the work in getting Atlas entities available on your client, logging...
583.68 KB  
Games  -  SportsPHool for Linux 1.0
SportsPHool is a PHP/MySQL-based sports pick 'em application, similar to the pick 'em games on ESPN and other sports sites. SportsPHool will track winners/losers, play against the spread, run multiple sports games, and build dynamic graphs.
368.64 KB  
Games  -  Pentagram 20101015
Pentagram is a project aiming to create an Ultima 8 engine for use on modern operating systems, including Linux, Mac OS X and Windows.
5.58 MB  
Puzzles  -  xJigsaw 2.1.0
xJigsaw combines xpuz 2.6 with a simple gui that allows easy creation of jigsaw puzzles from image types jpeg,png,bmp,tiff or gif. The puzzles can be played from with xJigsaw, or stand-alone executable puzzles can be created that will run...
3.24 MB  
Puzzles  -  Pushover 0.0.3
Pushover is a fun puzzle game originally published by Ocean in 1992. In this game you control an ant that can walk along platforms that are connected with ladders. On those platforms are dominos that need to fall according to some rules.
20.63 MB  
Puzzles  -  Simon Tatham's Portable Puzzle Collection 0.61
Simon Tatham's Portable Puzzle Collection is an assortment of single-player puzzle games for Linux users. It contains a reimplementation of Minesweeper where every puzzle is guaranteed to be solvable, a number of logic puzzles originally invented...
2.26 MB  
Puzzles  -  Tetzle 2.0.0
Tetzle is a jigsaw puzzle game that uses tetrominoes for the pieces. Any image can be imported and used to create puzzles with a wide range of sizes. Games are saved automatically, and you can select between currently in progress games.
583.68 KB  
Puzzles  -  4DTris 0.4.2
4D-TRIS is an alteration of the well-known Tetris game. The game field is extended to 4D space, which has to filled up by the gamer with 4D hyper cubes. The software is written in C and uses OpenGL and SDL .
583.68 KB