Thread: sudoku solver

  1. #1
    Banned
    Join Date
    Nov 2007
    Posts
    678

    sudoku solver

    can anybody here post a simplest example of console based su-do-ku solver?
    no. it's not needed for home work. neither for work.
    please post well commented source. thanks

    PS: the code should be C/C++ please.

  2. #2
    pwns nooblars
    Join Date
    Oct 2005
    Location
    Portland, Or
    Posts
    1,094
    You need a well commented source of a sudoku solver for what purpose?

  3. #3
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    here's a well documented algorithm .

    http://www.eddaardvark.co.uk/sudokusolver.html

  4. #4
    Banned
    Join Date
    Nov 2007
    Posts
    678
    thanks indigo0086!
    But that's just algorithm! And source is in Python
    I think I am a bit too lazy to do it from algorithm and python source

    Wraithan I just wanted to see how it works. Nothing special.
    I have two versions of it already.
    1) In assembly. Too hard to follow!
    2) In C. Deliberately made too hard to follow

    Now my questions:
    If it was my home work. You would not post it, right?
    If it was needed for work. You would ask for something in reward?

    Since it is just for the purpose of learning (I am just curious), will you post the code?
    I hope somebody must have written it already! :|

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    All you can learn from a Sudoku solver is algorithms. So the algorithmic description ought to be perfect.

    Here's one of my solvers.
    Code:
    module Main where
    
    import List
    
    ----------------- GENERIC HELPER FUNCTIONS ---------------------
    
    -- Apply a list of functions to some data, one after the other,
    -- from head to tail.
    chainl :: [(a -> a)] -> a -> a
    chainl [] x = x
    chainl (f:fs) x = chainl fs (f x)
    
    -- Repeat a function a number of times on a data item.
    rp :: (a -> a) -> a -> Int -> a
    rp _ x 0 = x
    rp fn x n = rp fn (fn x) (n - 1)
    
    -- Repeat a function a number of times on a data item, passing the counter.
    rpn :: (a -> Int -> a) -> a -> Int -> a
    rpn _ x 0 = x
    rpn fn x n = rpn fn (fn x n) (n - 1)
    
    -- Pad an array to a minimum length with the given item.
    rpad :: a -> Int -> [a] -> [a]
    rpad p len ls = ls ++ replicate (len - length ls) p
    
    
    
    -------------------- TYPE DECLARATIONS -------------------------
    
    -- The type of a row index
    type RowIndex = Int
    -- The type of a column index
    type ColIndex = Int
    -- The type of an area identifier
    type AreaId = (Int, Int)
    -- The type of a value collection
    type PossibleValues = [Int]
    -- The general value/values type of a field.
    type FieldContent = Either Int [Int]
    
    -- A Sudoku board: a collection of 81 fields.
    data SudokuBoard =
            SudokuBrd [SudokuField]
    
    -- A Sudoku field: a pair of coordinates on the board and either a single
    -- known value, or a list of possibilities.
    data SudokuField =
            SudokuUnsure RowIndex ColIndex PossibleValues |
            SudokuSure RowIndex ColIndex Int
    
    -- A group of fields: can be a row, a column or an area. Each group, when
    -- applied to a board, yields 9 fields.
    data SudokuGroup =
            SudokuRow RowIndex |
            SudokuCol ColIndex |
            SudokuArea AreaId
    
    -- The type of the dataset passed to init.
    type InitData = [(RowIndex, ColIndex, Int)]
    
    
    ---------------- BASIC TYPE OPERATIONS ---------------------
    
    ----- FIELDS ------
    
    -- Determine the ordering of two fields. Ordering works in reading order,
    -- first across and then down.
    fieldOrder :: SudokuField -> SudokuField -> Ordering
    fieldOrder a b =
            if ar < br then LT
            else if ar > br then GT
            else if ac < bc then LT
            else if ac > bc then GT
            else EQ
            where
                    ac = col a
                    ar = row a
                    bc = col b
                    br = row b
    
    -- Two fields are equal if their coordinates are the same; values are ignored.
    instance Eq SudokuField where
            (==) a b = fieldOrder a b == EQ
    
    -- Fields can be ordered.
    instance Ord SudokuField where
            compare = fieldOrder
    
    -- Fields can be displayed. Format is (row,column) -> values, where values
    -- is either a list of possibilities, or the fixed value with a '!'.
    instance Show SudokuField where
            show (SudokuUnsure r c vals) = "(" ++ show r ++ "," ++ show c ++
                    ") -> " ++ show vals
            show (SudokuSure r c val) = "(" ++ show r ++ "," ++ show c ++
                    ") -> " ++ show val ++ "!"
    
    -- Get the row of a field.
    row :: SudokuField -> RowIndex
    row (SudokuUnsure r _ _) = r
    row (SudokuSure r _ _) = r
    
    -- Get the row group of a field.
    rowOf :: SudokuField -> SudokuGroup
    rowOf = SudokuRow . row
    
    -- Get the column of a field.
    col :: SudokuField -> ColIndex
    col (SudokuUnsure _ c _) = c
    col (SudokuSure _ c _) = c
    
    -- Get the column group of a field.
    colOf :: SudokuField -> SudokuGroup
    colOf = SudokuCol . col
    
    -- Create an area ID from a pair of field coordinates.
    mkarea :: RowIndex -> ColIndex -> AreaId
    mkarea r c = (r `div` 3, c `div` 3)
    
    -- Get the area ID of a field.
    area :: SudokuField -> AreaId
    area (SudokuUnsure r c _) = mkarea r c
    area (SudokuSure r c _) = mkarea r c
    
    -- Get the area group of a field.
    areaOf :: SudokuField -> SudokuGroup
    areaOf = SudokuArea . area
    
    -- Get the value/values of a field.
    values :: SudokuField -> FieldContent
    values (SudokuSure _ _ v) = Left v
    values (SudokuUnsure _ _ vs) = Right vs
    
    -- Create a field from coordinates and a value/values.
    mkfield :: RowIndex -> ColIndex -> FieldContent -> SudokuField
    mkfield r c (Left i) = SudokuSure r c i
    mkfield r c (Right is) = SudokuUnsure r c is
    
    isSure :: SudokuField -> Bool
    isSure (SudokuUnsure _ _ _) = False
    isSure (SudokuSure _ _ _) = True
    
    -- Tells whether two fields share any group. Each field is related to 20 others.
    related :: SudokuField -> SudokuField -> Bool
    related f g = isIn g (rowOf f) ||
                  isIn g (colOf f) ||
                  isIn g (areaOf f)
    
    ------- BOARD -------
    
    -- The board can be displayed. Each field is given a width of 12.
    instance Show SudokuBoard where
            show (SudokuBrd flds) = "Board:\n" ++ showBrd flds
                    where showBrd [] = "\n"
                          showBrd cs = showFlds (take 9 cs) ++ "\n"
                                       ++ showBrd (drop 9 cs)
                          showFlds [] = ""
                          showFlds ((SudokuSure _ _ v):cs) =
                            padF (show v) ++ showFlds cs
                          showFlds ((SudokuUnsure _ _ v):cs) =
                            padF (show v) ++ showFlds cs
                          padF = rpad ' ' 12
    
    
    -- Get the empty board, where everything's possible.
    emptyBoard :: SudokuBoard
    emptyBoard = SudokuBrd [ SudokuUnsure x y [1..9] | x <- [0..8], y <- [0..8] ]
    
    
    ------ GROUPS -------
    
    -- Get the fields on a board within a group.
    fieldsIn :: SudokuBoard -> SudokuGroup -> [SudokuField]
    fieldsIn (SudokuBrd flds) g = filter (\x -> isIn x g) flds
    
    -- Get the fields on a board NOT within a group.
    fieldsNotIn :: SudokuBoard -> SudokuGroup -> [SudokuField]
    fieldsNotIn (SudokuBrd flds) g = filter (\x -> not (isIn x g)) flds
    
    -- Whether a field is in a group.
    isIn :: SudokuField -> SudokuGroup -> Bool
    isIn f (SudokuRow r) = row f == r
    isIn f (SudokuCol c) = col f == c
    isIn f (SudokuArea a) = area f == a
    
    -- Get all 27 groups of a board.
    allGroups :: [SudokuGroup]
    allGroups = allRows ++ allCols ++ allAreas
    
    -- Get all row groups of a aboard.
    allRows :: [SudokuGroup]
    allRows = [SudokuRow x | x <- [0..8]]
    
    -- Get all column groups of a board.
    allCols :: [SudokuGroup]
    allCols = [SudokuCol x | x <- [0..8]]
    
    -- Get all area groups of a board.
    allAreas :: [SudokuGroup]
    allAreas = [SudokuArea (x, y) | x <- [0..2], y <- [0..2]]
    
    
    
    ---------------- GENERAL BOARD OPERATIONS --------------------
    
    -- Sort a board so that the fields come in reading order.
    sortBoard :: SudokuBoard -> SudokuBoard
    sortBoard (SudokuBrd flds) = SudokuBrd (sort flds)
    
    -- Create an irregular (could be less than 81 fields) board of only the known
    -- fields.
    solvedBoard :: SudokuBoard -> SudokuBoard
    solvedBoard (SudokuBrd flds) = SudokuBrd (filter isSure flds)
    
    -- Test whether a board has been completely solved, i.e. consists only of
    -- certain fields.
    isSolved :: SudokuBoard -> Bool
    isSolved (SudokuBrd flds) = all isSure flds
    
    
    --------------------- BOARD SETUP ----------------------------
    
    -- Take a bunch of initialization data and prime a new board with it.
    init :: InitData -> SudokuBoard
    init = initInner emptyBoard
    
    -- Apply the given initialization data to a board.
    initInner :: SudokuBoard -> InitData -> SudokuBoard
    initInner brd [] = brd
    initInner brd (v:vs) = initInner (fixC brd v) vs
            where fixC b (r, c, val) = fix b (r-1) (c-1) val
    
    -- Fix a field to a specific value.
    fix :: SudokuBoard -> RowIndex -> ColIndex -> Int -> SudokuBoard
    fix (SudokuBrd flds) r c v =
            SudokuBrd ((SudokuSure r c v) : (delete (SudokuSure r c 0) flds))
    
    
    -------------------- BOARD SOLVING ----------------------------
    
    -- Attempt to solve a board. WARNING: Current implementation will go into
    -- infinite loop if it can't solve the board.
    solve :: InitData -> SudokuBoard
    solve = sortBoard . (until isSolved (chainl strategies)) . Main.init
    
    -- List the solution strategies used in a single iteration.
    -- strikeKnown is listed several times because it kind of performs cleanup
    -- duty.
    strategies :: [(SudokuBoard -> SudokuBoard)]
    strategies =
            [ strikeKnown   -- Strike out numbers that belong to fixed values.
            , strikePairs   -- Strike values x, y where group contains exactly
                            -- two fields [x, y].
            , strikeKnown   -- This is more likely to catch something.
            , fixLonely     -- Find possibilities that occur only in one field
            , strikeKnown   -- This is more likely to catch something.
            ]
    
    
    ------------- SOLUTION STRATEGY I: STRIKE KNOWN -----------------
    {-
    This is the simplest of all strategies. It scans the board for known fields.
    Then it strikes their values from the possibilities of all uncertain fields in
    the three associated groups.
    -}
    
    -- Perform the Strike Known step.
    strikeKnown :: SudokuBoard -> SudokuBoard
    strikeKnown brd = let (SudokuBrd flds) = brd
                      in strikeKnownFields brd flds
    
    -- The main controller of Strike Known. Iterates over all fields of a board
    -- to strike the known values.
    strikeKnownFields :: SudokuBoard -> [SudokuField] -> SudokuBoard
    strikeKnownFields brd [] = brd
    strikeKnownFields brd ((SudokuSure r c v):flds) =
            strikeKnownFields newbrd flds
            where newbrd = strikeFromGroup rowcolbrd (SudokuArea (mkarea r c)) v
                  rowcolbrd = strikeFromGroup rowbrd (SudokuCol c) v
                  rowbrd = strikeFromGroup brd (SudokuRow r) v
    strikeKnownFields brd ((SudokuUnsure _ _ _):flds) =
            strikeKnownFields brd flds
    
    {-strikeKnownFields :: [SudokuField] -> [SudokuField]
    strikeKnownFields -}
    
    -- The workhorse of Strike Known. Given a board, a group and a value, this
    -- function gives a new board where, in the given group, all unsure fields
    -- have the value stricken from their possibilities.
    strikeFromGroup :: SudokuBoard -> SudokuGroup -> Int -> SudokuBoard
    strikeFromGroup brd grp val =
            SudokuBrd (strikeFromFields (fieldsIn brd grp) val ++
                    fieldsNotIn brd grp)
    
    strikeFromFields :: [SudokuField] -> Int -> [SudokuField]
    strikeFromFields flds val = map (\f -> strikeFromField f val) flds
    
    strikeFromField :: SudokuField -> Int -> SudokuField
    strikeFromField (SudokuUnsure r c (a : b : [])) v
            | a == v = SudokuSure r c b
            | b == v = SudokuSure r c a
            | otherwise = SudokuUnsure r c [a, b]
    strikeFromField (SudokuUnsure r c vals) v = SudokuUnsure r c (delete v vals)
    strikeFromField (SudokuSure r c v) _ = SudokuSure r c v
    
    
    strikePairs :: SudokuBoard -> SudokuBoard
    strikePairs brd = strikePairsInGroups brd allGroups
    
    strikePairsInGroups :: SudokuBoard -> [SudokuGroup] -> SudokuBoard
    strikePairsInGroups = foldl strikePairsInGroup
    
    strikePairsInGroup :: SudokuBoard -> SudokuGroup -> SudokuBoard
    strikePairsInGroup brd g = SudokuBrd (fieldsNotIn brd g ++
            strikePairsInFieldList (fieldsIn brd g))
    
    strikePairsInFieldList :: [SudokuField] -> [SudokuField]
    strikePairsInFieldList flds = foldl strikePair flds pairs
            where pairs = findPairs flds
    
    findPairs :: [SudokuField] -> [(SudokuField, SudokuField)]
    findPairs [] = []
    findPairs (f:fs) = pairl ++ findPairs fs
            where pair = findMatchFor f fs
                  pairl = maybe [] (\e -> [e]) pair
    
    findMatchFor :: SudokuField -> [SudokuField] -> Maybe (SudokuField, SudokuField)
    findMatchFor (SudokuSure _ _ _) _ = Nothing
    findMatchFor f [] = Nothing
    findMatchFor f ((SudokuUnsure x y [v1,v2]):fs) =
            let (SudokuUnsure _ _ vals) = f
            in if [v1,v2] == vals then Just (f, (SudokuUnsure x y [v1,v2]))
                                else findMatchFor f fs
    findMatchFor f (_:fs) = findMatchFor f fs
    
    strikePair :: [SudokuField] -> (SudokuField, SudokuField) -> [SudokuField]
    strikePair [] _ = []
    strikePair (g:gs) (f1, f2) = f : strikePair gs (f1, f2)
            where f = if g == f1 || g == f2
                      then g
                      else strikeValuesOf f1 g
    
    strikeValuesOf :: SudokuField -> SudokuField -> SudokuField
    strikeValuesOf (SudokuUnsure _ _ svals) f = foldl strikeFromField f svals
    
    
    
    fixLonely :: SudokuBoard -> SudokuBoard
    fixLonely brd = fixLonelyInGroups brd allGroups
    
    fixLonelyInGroups :: SudokuBoard -> [SudokuGroup] -> SudokuBoard
    fixLonelyInGroups = foldl fixLonelyInGroup
    
    fixLonelyInGroup :: SudokuBoard -> SudokuGroup -> SudokuBoard
    fixLonelyInGroup brd g = SudokuBrd (fieldsNotIn brd g ++
            fixLonelyInFieldList (fieldsIn brd g))
    
    fixLonelyInFieldList :: [SudokuField] -> [SudokuField]
    fixLonelyInFieldList fs = fixLonelyInFieldListInner fs fs
    
    fixLonelyInFieldListInner :: [SudokuField] -> [SudokuField] -> [SudokuField]
    fixLonelyInFieldListInner [] _ = []
    fixLonelyInFieldListInner ((SudokuSure x y v):fs) ts =
            (SudokuSure x y v) : fixLonelyInFieldListInner fs ts
    fixLonelyInFieldListInner ((SudokuUnsure x y vs):fs) ts =
            maybe (SudokuUnsure x y vs) (SudokuSure x y) fv :
                    fixLonelyInFieldListInner fs ts
            where fv = findLonely vs mts mts
                  mts = (delete (SudokuUnsure x y vs) ts)
    
    findLonely :: [Int] -> [SudokuField] -> [SudokuField] -> Maybe Int
    findLonely [] _ _ = Nothing
    findLonely (c:cs) [] mts = Just c
    findLonely (c:cs) ((SudokuSure _ _ v):ts) mts =
            if c == v then findLonely cs mts mts
                      else findLonely (c:cs) ts mts
    findLonely (c:cs) ((SudokuUnsure _ _ vs):ts) mts =
            if elem c vs then findLonely cs mts mts
                         else findLonely (c:cs) ts mts
    
    
    nr119a :: InitData
    nr119a = [
            (1,6,8),
            (2,5,5),
            (2,6,4),
            (2,8,2),
            (2,9,8),
            (3,3,3),
            (3,5,1),
            (3,8,5),
            (3,9,7),
            (4,5,3),
            (4,7,9),
            (5,2,9),
            (5,3,7),
            (5,4,1),
            (5,8,8),
            (6,1,3),
            (6,2,8),
            (6,6,9),
            (6,8,4),
            (7,4,5),
            (7,9,9),
            (8,2,5),
            (8,3,4),
            (8,5,7),
            (8,6,3),
            (8,9,1),
            (9,2,7),
            (9,3,8),
            (9,7,5),
            (9,8,3)
            ]
    
    
    nr119b :: InitData
    nr119b = [
            (1,6,9),
            (1,9,8),
            (2,3,4),
            (2,4,8),
            (2,6,1),
            (2,7,7),
            (3,1,2),
            (3,3,1),
            (3,8,5),
            (4,3,7),
            (4,5,4),
            (4,6,8),
            (4,7,6),
            (5,7,1),
            (6,2,6),
            (6,3,3),
            (6,5,7),
            (6,9,9),
            (7,1,7),
            (7,4,2),
            (7,5,3),
            (7,8,9),
            (8,2,2),
            (8,7,5),
            (9,2,1),
            (9,3,9),
            (9,6,6),
            (9,8,7)
            ]
    
    nr119c :: InitData
    nr119c = [
            (1,6,5),
            (1,8,9),
            (1,9,2),
            (2,1,5),
            (2,2,4),
            (2,5,6),
            (2,6,9),
            (2,7,8),
            (3,3,2),
            (3,5,7),
            (3,9,4),
            (4,2,8),
            (4,6,4),
            (4,7,2),
            (5,4,3),
            (5,6,2),
            (6,3,4),
            (6,4,7),
            (6,8,8),
            (7,1,4),
            (7,5,2),
            (7,7,1),
            (8,3,3),
            (8,4,9),
            (8,5,1),
            (8,8,6),
            (8,9,8),
            (9,1,1),
            (9,2,6),
            (9,4,5)
            ]
    
    mad :: InitData
    mad = [
    	(1,1,4),
    	(1,8,2),
    	(2,3,6),
    	(2,4,7),
    	(2,7,9),
    	(3,2,8),
    	(3,6,3),
    	(4,3,1),
    	(4,5,5),
    	(4,9,6),
    	(5,2,3),
    	(5,8,4),
    	(6,1,2),
    	(6,4,9),
    	(6,7,7),
    	(7,4,8),
    	(7,8,1),
    	(8,3,5),
    	(8,6,6),
    	(8,7,2),
    	(9,2,7),
    	(9,9,3)
    	]
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  6. #6
    Banned
    Join Date
    Nov 2007
    Posts
    678
    Well ... that was HUGE act of kindly help! I am obliged sire! Hail you!
    Just tell me ... which programming lingo is this!

  7. #7
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    I believe it's Haskell, but I'm not certain about that.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  8. #8
    Banned
    Join Date
    Nov 2007
    Posts
    678
    Thanks!
    I thought it was C -= BASIC * Asm + Java / Python ^ Ruby - Perl language!

  9. #9
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    Haskell does that to you.

  10. #10
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    And if you havent cought the drift by now, ill spill the beans....nobody will do your work just because your lazy. You have python-source....stop being lazy and stop wasting our time because of it.
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by Shakti View Post
    And if you havent cought the drift by now, ill spill the beans....nobody will do your work just because your lazy. You have python-source....stop being lazy and stop wasting our time because of it.
    Oh Shakti, you spoilsport!!

    Manav, I don't know your experience, but I wrote a Sudoku solver last year, and it was quite tricky. Perhaps because I had not played Sudoku before I started the program, and am a hobby programmer, not a pro.

    In any case, the code is LONG*, and the algorithm is tricky, e.g. it repeatedly uses a 2D to 1D array manipulation - very unexpected.

    My thought is that if you had the code, you wouldn't understand it, unless you had enough skill to code it yourself. If you had that skill, you wouldn't need the code.

    Beyond the obvious solitary "must be this number, here", and "can't include this possibility on this square over here", you need to read up on "the rule of pairs" (either inside, or outside, or both), and how to switch to guessing for the toughest Sudoku puzzles, when all other techniques are exhausted, and the puzzle is still unsolved.

    *my solver uses a fast technique, or a very slow "odometer" technique. The latter is a tribute to a friend who died most unexpectedly. (An odometer was the first bit of code he asked me to write for him.)

    You'll like this challenge of writing a Sudoku program, Manav. You don't want to underestimate it.

  12. #12
    Banned
    Join Date
    Nov 2007
    Posts
    678
    What Shakti said, I already knew it by CornedBee's post
    Thanks Adak for your suggestion. I know and this is proven by my own experience (time and again)
    that I can never ever understand an algorithm in code form unless I know about the algorithm
    itself in a very descriptive way (from book etc.)

    Since I am spending life 40% sleeping, 40% in office, 15% daily chores, 5% entertainment.

    I was acting a bit lazy and thought I will get some already written code in C. Stupid idea!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sudoku solver...
    By matsp in forum C++ Programming
    Replies: 24
    Last Post: 02-14-2011, 08:30 PM
  2. Help for a sudoku Solver
    By axilleask in forum C Programming
    Replies: 3
    Last Post: 11-26-2007, 04:28 PM
  3. Sudoku Puzzle Solver?
    By Apocalypse in forum C Programming
    Replies: 7
    Last Post: 03-12-2006, 02:10 PM
  4. Newbie with a Sudoku Solver program
    By TylerBill in forum C Programming
    Replies: 13
    Last Post: 03-08-2006, 07:27 PM
  5. Sudoku - the new addiction
    By axon in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 11-07-2005, 11:39 PM