Explain sudoku brute force algorithm

This is a discussion on Explain sudoku brute force algorithm within the C Programming forums, part of the General Programming Boards category; can you explain the sudoku brute force algorithm in detail please ( Not Code). I read the algorithm in wikipedia ...

  1. #1
    Registered User
    Join Date
    Jan 2011
    Posts
    113

    Question Explain sudoku brute force algorithm

    can you explain the sudoku brute force algorithm in detail please ( Not Code).

    I read the algorithm in wikipedia : Sudoku algorithms - Wikipedia, the free encyclopedia
    but still missing something.

    In wikipedia, they said that :

    " Briefly, a brute force program would solve a puzzle by placing the digit "1" in the first cell and checking if it is allowed to be there. If there are no violations (checking row, column, and box constraints) then the algorithm advances to the next cell, and places a "1" in that cell. When checking for violations, it is discovered that the "1" is not allowed, so the value is advanced to a "2". If a cell is discovered where none of the 9 digits is allowed, then the algorithm leaves that cell blank and moves back to the previous cell."

    this specific part I'm not clear about..

    can you please explain . .

    Also if you could, please try to explain backtracking algorithm...

    and finally which one best brute force or backtracking

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,484
    Get a pencil and some paper, draw a 3x3 grid and randomly place say 2,4,6,8,3,5 (leaving 1,7,9) in the boxes.

    Now run through the description above.


    Have you actually tried to solve any sudoku puzzles, or is it just an abstract concept to you?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Jan 2011
    Posts
    113
    Mr. Salem,
    I think you mis understood..
    To be specific about where I am little bit confused ...
    look here..
    If a cell is discovered where none of the 9 digits is allowed, then the algorithm leaves that cell blank and moves back to the previous cell."

    Take a random sudoku and Imagine you placed a number 3 there.. and went to next empty cell where none of 9 digits is allowed...
    according to the above line, it goes back to 3 and is incremented by 1. how could I possibly do that without checking the rules to increment it..

    I might definitely wrong in understanding that.. can you clear that..
    Last edited by suryak; 08-07-2011 at 02:18 AM. Reason: spelling mistake

  4. #4
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    Quote Originally Posted by suryak View Post
    Take a random sudoku and Imagine you placed a number 3 there.. and went to next empty cell where none of 9 digits is allowed...
    according to the above line, it goes back to 3 and is incremented by 1. how could I possibly do that without checking the rules to increment it..
    You have to check the rules when incrementing it. Then if you find that no other number is allowed you move back one more step and start incrementing again.

  5. #5
    Registered User
    Join Date
    Jan 2011
    Posts
    113
    Do you mean.. I should check the other possible value in the cell that can be placed when I get back to previous cell or I should add (+1 to the number )..
    ex: is 3 is present.. ( I should place 3 + 1 = 4 or next possible number.. )

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Your program could have a list of possibles, for every unsolved square, and only consider those. Or you could go "whole hog" with brute force, and just increment and check, increment and check, increment and check.

    It's quite surprising how few lines of code you need, for a very simple brute force solver. Sudoku is full of subtle clues for human solvers, but a brute force solver can be a real simpleton.

    Sudoku solving with a program is a lot of fun. There are SO many little tricks you can use to speed up your solver, once you get to know the puzzle (and programming better).

    And then there is Knuth's "Dancing Links"/"Algorithm X", which is such a beauty, but mind-blowing, as well.

    Working with a 4 X 4 mini board, is a great way to start. Big thumbs up on that!

  7. #7
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    Quote Originally Posted by suryak View Post
    Do you mean.. I should check the other possible value in the cell that can be placed when I get back to previous cell or I should add (+1 to the number )..
    ex: is 3 is present.. ( I should place 3 + 1 = 4 or next possible number.. )
    Example assuming 3 is the only currently allowed number for that cell:
    You check what number is there currently. You find 3. You check if 4..9 is allowed, none are.. Clear the cell and move back a step.
    You find a 4. You check if 5 is allowed. It is. You move forward one cell.
    You are back at the problem cell. You check 1..9 if any are allowed. Now you find that 4 is allowed. Move forward one step. Repeat..
    If you ever get to the starting position and find that you have to increment a 9 then either the board is badly constructed or you made a mistake in your algorithm.

    Edit/Update:

    Not having tried anything similar before I decided to try writing a solver..

    First attempt)
    After looking over the code and thinking it was okey I ran it against an empty board..
    "No solution possible"
    Simple beginner's mistake. I was doing an assignment where I meant to do a comparison

    Second attempt)
    Empty board works fine. And so did some other simple boards I tried, so I decided to let my solver loose against wikipedia's "worst case" scenario.
    Wikipedia claims it should take 30-45 minutes with their algorithm on a 3ghz cpu so I was estimating maybe 2 times longer than that, because of a 1.7ghz laptop and unoptimized code.
    After about an hour running I discovered that my simple sudoku solver was in fact a very complex endless loop.
    It was another typo in a comparison. '<' instead of '>'. It only triggered the bug in very specific cases so I never spotted it in my previous testing.

    Third attempt)
    Success! 62 seconds!
    Either the evolution of optimizing compilers has made huge leaps since that wikipedia article was written, or it isn't a worst case scenario at all.
    It's quite amazing the feeling of bliss you get when you manage to complete a project and get very unexpected positive results
    Now to try and make it multi-threaded..
    Last edited by _Mike; 08-07-2011 at 06:32 AM.

  8. #8
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Now to try and make it multi-threaded..
    Nice idea.
    Would having them follow totally different (never crossing) paths be sufficient to ensure that the solution is correct?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by _Mike View Post
    Now to try and make it multi-threaded..
    I wouldn't bother. A good backtracking solver can solve a 9x9 board in about 4 milliseconds or less as it is. Surely that's fast enough.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    Quote Originally Posted by iMalc View Post
    I wouldn't bother. A good backtracking solver can solve a 9x9 board in about 4 milliseconds or less as it is. Surely that's fast enough.
    I know. But it might be a good learning experience. I've never done any multi threading programming before.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sudoku brute force
    By snare91 in forum C++ Programming
    Replies: 8
    Last Post: 02-14-2011, 06:20 AM
  2. Sudoku Brute Force Algorithm Help (recursion?)
    By ridilla in forum C Programming
    Replies: 22
    Last Post: 05-07-2010, 03:31 PM
  3. Brute Force
    By swgh in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 08-16-2007, 01:41 AM
  4. Brute Force
    By Wiz_Nil in forum C++ Programming
    Replies: 13
    Last Post: 02-15-2002, 12:28 PM
  5. Brute-Force
    By red11514 in forum C Programming
    Replies: 1
    Last Post: 11-12-2001, 11:53 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21