LinuxQuestions.org
View the Most Wanted LQ Wiki articles.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
LinkBack Search this Thread
Old 08-21-2005, 10:31 PM   #1
ewt3y
Member
 
Registered: May 2005
Location: hanoi vietnam
Distribution: mandriva
Posts: 106

Rep: Reputation: 15
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 !
 
Old 08-22-2005, 04:02 AM   #2
cdhgee
Member
 
Registered: Oct 2003
Location: St Paul, MN
Distribution: Fedora 8, Fedora 9
Posts: 513

Rep: Reputation: 30
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.

My web-based Sudoku solver: http://www.allpowerfuldave.com/games/sudoku

Last edited by cdhgee; 08-22-2005 at 04:04 AM.
 
Old 08-22-2005, 04:16 AM   #3
bigearsbilly
Senior Member
 
Registered: Mar 2004
Location: england
Distribution: FreeBSD, Puppy
Posts: 3,048

Rep: Reputation: 95
I did my solver in
lisp

now that is a proper language for AI.
I would hate to do it in C++.

 
Old 08-22-2005, 05:04 AM   #4
cdhgee
Member
 
Registered: Oct 2003
Location: St Paul, MN
Distribution: Fedora 8, Fedora 9
Posts: 513

Rep: Reputation: 30
Or another good language to do it in would be prolog - that language is good for searching trees for solutions.
 
Old 08-22-2005, 05:14 AM   #5
bigearsbilly
Senior Member
 
Registered: Mar 2004
Location: england
Distribution: FreeBSD, Puppy
Posts: 3,048

Rep: Reputation: 95
Quote:
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.
 
Old 08-22-2005, 04:40 PM   #6
archtoad6
Senior Member
 
Registered: Oct 2004
Location: Houston, TX (usa)
Distribution: MEPIS, Debian, Knoppix,
Posts: 4,727
Blog Entries: 15

Rep: Reputation: 229Reputation: 229Reputation: 229
I was going to use a spreadsheet to automate finding the obvious & showing the contradictions implied by guesses. Haven't done it yet.
 
Old 08-22-2005, 08:32 PM   #7
sundialsvcs
Senior Member
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 3,685

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
Prolog can do it. See google.
 
Old 08-22-2005, 10:32 PM   #8
ewt3y
Member
 
Registered: May 2005
Location: hanoi vietnam
Distribution: mandriva
Posts: 106

Original Poster
Rep: Reputation: 15
Let me introduce the way that the program will follow to resolve any Sudoku problem :
If you can improve : my heartfelt gratitude .

1. read the problem.

2. putting number into a cell :
-determine the possible numbers by examining the cell's row, column, folk (3x3).
 
Old 08-23-2005, 02:54 AM   #9
bigearsbilly
Senior Member
 
Registered: Mar 2004
Location: england
Distribution: FreeBSD, Puppy
Posts: 3,048

Rep: Reputation: 95
I can tell you how I did it if you're interested?
mine's very simple and works without guessing for most puzzles
 
Old 08-23-2005, 03:03 AM   #10
cdhgee
Member
 
Registered: Oct 2003
Location: St Paul, MN
Distribution: Fedora 8, Fedora 9
Posts: 513

Rep: Reputation: 30
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.
 
Old 08-23-2005, 03:32 AM   #11
bigearsbilly
Senior Member
 
Registered: Mar 2004
Location: england
Distribution: FreeBSD, Puppy
Posts: 3,048

Rep: Reputation: 95
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.
;;
 
Old 08-28-2005, 09:07 AM   #12
ewt3y
Member
 
Registered: May 2005
Location: hanoi vietnam
Distribution: mandriva
Posts: 106

Original Poster
Rep: Reputation: 15
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.
 
Old 08-28-2005, 10:13 AM   #13
cdhgee
Member
 
Registered: Oct 2003
Location: St Paul, MN
Distribution: Fedora 8, Fedora 9
Posts: 513

Rep: Reputation: 30
Quote:
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.
 
Old 08-30-2005, 04:27 AM   #14
bigearsbilly
Senior Member
 
Registered: Mar 2004
Location: england
Distribution: FreeBSD, Puppy
Posts: 3,048

Rep: Reputation: 95
Quote:
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.

I have finished my puzzle.

I am a native speaker y'know
 
Old 08-30-2005, 04:29 AM   #15
bigearsbilly
Senior Member
 
Registered: Mar 2004
Location: england
Distribution: FreeBSD, Puppy
Posts: 3,048

Rep: Reputation: 95
Quote:
as there are only 729 different puzzles.
Is this true?

Sounds a bit low.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
mysql - back to square one bshearer *BSD 3 05-29-2005 10:32 AM
Wondering if I should use JAVA or UNIX scripts to develop a program pedrosan Programming 4 05-22-2004 07:35 AM
howto use kdevelop to develop and debug a console program vasanthraghavan Programming 5 05-15-2004 12:23 AM
square one - how do I make it go? linuxceptic Linux - Wireless Networking 3 02-04-2004 07:23 PM
How can I develop the audio program in linux? fliny Programming 3 10-03-2003 07:17 PM


All times are GMT -5. The time now is 04:50 AM.

Main Menu
 
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: @linuxquestions
Open Source Consulting | Domain Registration