Thread: Sudoku Puzzle Solver?

  1. #1
    Registered User
    Join Date
    Jul 2002
    Posts
    11

    Sudoku Puzzle Solver?

    I've been working on this for a while now, and I've got it to the point where it almost works, but not quite. It's really frustrating and I can't figure out where my logic is going wrong.

    http://uranther.pastebin.com/584302 <-- the code

    Here's sudoku.txt:
    Code:
    98___63__
    ___3_752_
    _23_5_4_9
    162__49_5
    8__6_5__3
    5_42__671
    3_1_6_89_
    _498_3___
    __89___32
    Line 94 is just to check the progress of the solve() function for debugging purposes. I think I have all the structure in place but somewhere my logic has gone wrong, hopefully. Can someone help me with this program? I'd greatly appreciate it.

  2. #2
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    First off, beside checking incolumn and inrow, you need to check if the number is in the 3x3 sub-grid it belongs.

    We just had a discussion on sudoku techniques here along with some code

  3. #3
    Registered User
    Join Date
    Jul 2002
    Posts
    11
    Quote Originally Posted by Darryl
    First off, beside checking incolumn and inrow, you need to check if the number is in the 3x3 sub-grid it belongs.

    We just had a discussion on sudoku techniques here along with some code
    I assumed ultimately that that wouldn't be needed because that's more of a sanity check, but I will look through this thread, thanks

  4. #4
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,079
    Quote Originally Posted by Apocalypse
    I assumed ultimately that that wouldn't be needed because that's more of a sanity check, but I will look through this thread, thanks
    It's not a sanity check at all... it's a rule.

    Code:
    1 2 3 | 4 5 6 | 7 8 9
    2 3 4 | 5 6 7 | 8 9 1
    3 4 5 | 6 7 8 | 9 1 2
    ---------------------
    4 5 6 | 7 8 9 | 1 2 3
    5 6 7 | 8 9 1 | 2 3 4
    6 7 8 | 9 1 2 | 3 4 5
    ---------------------
    7 8 9 | 1 2 3 | 4 5 6
    8 9 1 | 2 3 4 | 5 6 7
    9 1 2 | 3 4 5 | 6 7 8
    By your standards, this is a legal soduku solution. But it's not.

    Anyway, here is an old post on a soduku solver, but it may be below you. It speaks in consideration of how to handle your 3x3 boxes.

    If you're looking to make a soduku solver, you should consider writing the already known logic algorithms to your program. There a many of them already discovered. You can find most of them here and another great site here.
    Last edited by SlyMaelstrom; 03-04-2006 at 08:08 PM.
    Sent from my iPadŽ

  5. #5
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    also, it looks as if the logic never changes in the solve function.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  6. #6
    Registered User
    Join Date
    Jul 2002
    Posts
    11
    Here's my improved program -- it actually solves some sudoku puzzles. It doesn't, however, solve harder puzzles like some medium difficulty, and all hard and very hard puzzles I've tried. I don't see why it would solve an easy puzzle and not a hard one?

    http://uranther.pastebin.com/596765

    Solves:
    Code:
    98___63__
    ___3_752_
    _23_5_4_9
    162__49_5
    8__6_5__3
    5_42__671
    3_1_6_89_
    _498_3___
    Doesn't solve:
    Code:
    _98__3__7
    __18_7_3_
    4___5____
    9____8_7_
    __6___5__
    _4_2____6
    ____3___2
    _8_4_97__
    5__7__36_

  7. #7
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    because easy puzzle "moves" are forced and therefore don't have "dead-ends". Harder puzzles require you to "guess" some positions, but later you may find those guesses where wrong so you need to reverse all numbers entered after the guess and then guess a different number.

  8. #8
    Registered User
    Join Date
    Feb 2006
    Posts
    20
    if you want to know how algoritms work on how to solve/generate i consider you to go look on http://www.setbb.com/phpbb/

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 8 Puzzle game solver with the Best-First algoritm
    By LordMX in forum C Programming
    Replies: 17
    Last Post: 08-11-2008, 10:00 AM
  2. 8 puzzle game solver in C
    By LordMX in forum Game Programming
    Replies: 2
    Last Post: 08-06-2008, 10:24 AM
  3. Replies: 12
    Last Post: 06-06-2008, 05:26 PM
  4. Help for a sudoku Solver
    By axilleask in forum C Programming
    Replies: 3
    Last Post: 11-26-2007, 04:28 PM
  5. sudoku puzzle
    By Dr Spud in forum C Programming
    Replies: 4
    Last Post: 11-26-2005, 04:41 AM