Let us develop a C program to resolve the Sudoku square
ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
Let us develop a C program to resolve the Sudoku square
I want a Sudoku square on my epitaph.
The square of 81. You inscripbe a number in the range of 1 to 9. Ah, my headstone is so splendid. Now if you are content to read : no number appears twice in a row and so for the column, if not I can't attempt resurrection. No twice appearance in a folk (3x3 square). Don't be lamented about your time, here is an instance : http://www.puzzle.jp/images/sudoku_01.gif
Me, wretch, can't resolve the problem alone, I want to use C, mu heartfelt grattitude to you thanks to whom the little wretch succeeds !
Not as easy as it sounds. For a start, C isn't the ideal language to write it in as it doesn't have many built-in functions. You'd be better off at least with C++ which has things like a vector class in the std lib, or even better yet, Java.
I wrote a web-based solver a while ago in PHP - it won't solve all problems but it can do the straightforward bits - it'll use logic as far as it can, but some Sudoku problems require guesswork and then unwinding if the guess was wrong - my program can't do that.
If you're interested in seeing the PHP version let me know and I'll post the source to it on my website. PHP is very similar to C syntacically so it's not difficult to translate - but you would need a list/vector structure of some sort at the very minimum.
as far as it can, but some Sudoku problems require guesswork and then unwinding if the guess was wrong
yeah, I came to the same conclusion.
I eventually had to resort to guesswork.
I did it in lisp with the expectation of converting it to C but it's
really fast with lisp anyway. 0.07 seconds on average and that's also
writing out three HTML files with the original, the solution, and a debug grid.
Last edited by bigearsbilly; 08-22-2005 at 05:19 AM.
I'd certainly be interested in hearing how someone else did it - mine's fine as far as it goes but it can't cope with the really difficult puzzles which have multiple paths, only one of which is correct.
Ok, here's the comments I put in my code....
be interesting to see if you understand it ok.
I've looked at other sourceforge solutions but there are
very few comments in them.
Code:
;;
;; Method
;; ======
;; A 'square' is a box containing a number or blank. The grid is 9x9 squares.
;; A 'box' is a sub-grid of 3x3 squares. The grid is 3x3 boxes.
;;
;; Each square on the grid is given a row, a column and a Box
;; Rows and columns 1 - 9 and the boxes are:
;;
;;
;; +-------+-------+-------+
;; | | | |
;; | A | B | C |
;; | | | |
;; +-------+-------+-------+
;; | | | |
;; | D | E | F |
;; | | | |
;; +-------+-------+-------+
;; | | | |
;; | G | H | I |
;; | | | |
;; +-------+-------+-------+
;;
;; This makes it easy to retrieve boxes rows and columns
;; without continually calculating the position.
;;
;; Each box is given a list of possibles. Namely: (1 2 3 4 5 6 7 8 9)
;;
;; Setting a number
;; ================
;; As a number is set in a square, it's row, column and box are all retrieved
;; and each square has the number removed from it's list of possibles.
;; So if a '3' is set in a square, then the squares in the relevent
;; box, row, column will have the possibles set to:
;; (1 2 4 5 6 7 8 9)
;;
;; That is the basis of it.
;;
;; So the algorithm is.
;; Start out with blank squares and set all with possibles: (1 2 3 4 5 6 7 8 9)
;;
;; 1. Set the given squares first, which removes many possibles.
;;
;; 2. After this, some squares may have only 1 possible (definites), check for
;; this and set if found. (see: 'Setting a number')
;;
;; 3. Now we go through each box, column and row and for 1 to 9,
;; find any numbers where there is only 1 valid possible square
;; If so set the number in that square.
;;
;; 4. Check to see boxes to see if a number occurs only in one row or
;; column, if so can discount the row or column from other boxes.
;;
;;
;;
;;
;; eg:
;; +-------+-------+-------+
;; | | | |
;; | | | |
;; | | | |
;; +-------+-------+-------+
;; | | | |
;; | | | |
;; | | | |
;; +-------+-------+-------+
;; | | | |
;; | | 3 | 3 | ----> can discount this row for 3 in other
;; | | | | boxes with the same row
;; +-------+-------+-------+
;;
;; Go back to step 2.
;;
;; Most are solved in < 3 Iterations.
;;
;; Guessing
;; ========
;; If it cannot be solved logically then we move on to guess work:
;; The guess goes by selecting blank squares in order of least possibles.
;;
;; The first number of the first square on the list is set and the logical
;; attempts at solution are tried. If it stalls, it guesses another for
;; the next square.
;;
;; If the guessed number causes an invalid grid (an exception is thrown)
;; then we wind back and remove that possibility from the grid.
;;
;; Usually, there will be blanks with only two possibilities.
;; So this greatly reduces the amount of guesswork needed.
;; If a square has possibles of (1,3) say, that's only two guesses
;; (it MUST be 1 or 3 otherwise it's an invalid puzzle)
;; One guess usually re-starts the puzzle enough to solve it.
;;
;; Guessing does not produce multiple solutions, only the first one found.
;; As this program was designed primarily as a logical rather than random
;; solution, producing multiple solutions is not of considered.
;;
Hi bigearsbilly, allow me to correct your spelling :
"I LOOKED at some solutions on sourceforge.com"
have + past participial means that you continue to look at it hitherto.
Yours.
Originally posted by sundialsvcs Prolog can do it. See google.
Having failed in previous attempts to write a program that will solve all sudoku puzzles, I was inspired to try again and so this time I decided to do it properly in prolog...so I dredged up the memories of my university AI lectures and the program's almost finished. At the moment it will solve basic puzzles - as long as there's always at least one cell with only one valid possibility. In theory , it should be trivial to extend this to any puzzle, but for some reason what I've tried for this so far just seems to make it sit in an endless loop - which it really shouldn't as there are only 729 different puzzles.
When I've finished it, I'll publish it under and open-source license of some description on my website.
Hi bigearsbilly, allow me to correct your spelling
actually ewty what you are referring to here is grammar, not spelling
Quote:
"I LOOKED at some solutions on sourceforge.com"
have + past participial means that you continue to look at it hitherto.
I'm sorry to say, that is not correct:
I have looked is correct. I have looked, I have finished looking.
I have been looking could possibly imply I continue to do so or intend to continue.
I am looking would definitely mean I am in the process of up to the present.
consider:
I am eating eating my dinner.
I have been eating my dinner.
I have eaten my dinner.
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.