Thread: 25x25 sudoku

  1. #1
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229

    25x25 sudoku

    We have already established that 9x9 sudoku is too easy for computers (hardest ones solved in milliseconds) -
    Sudoku solution generator algorithm

    An easy way to increase difficulty is to make the board bigger. Like 25x25.

    This is one I found on a random website (of "extreme" difficulty). I transcribed it into this computer-parseable format -
    Code:
    0 0 12 6 0 0 7 0 18 0 5 24 0 10 1 0 0 4 0 0 0 0 0 0 0 
    2 0 19 0 13 0 0 0 10 0 0 0 0 0 0 0 0 18 5 0 0 0 0 0 1 
    0 0 0 0 0 0 0 22 0 0 0 0 3 0 2 0 0 14 12 0 16 8 25 0 0 
    0 16 0 0 0 2 23 0 0 13 12 22 0 0 0 21 15 19 3 0 0 0 0 14 0 
    23 0 24 0 0 0 0 0 25 8 4 0 16 19 21 0 0 7 0 0 0 3 12 0 9 
    0 4 0 2 0 0 0 0 0 0 0 10 0 24 12 17 16 0 0 0 5 0 0 0 0 
    0 0 9 0 0 6 25 0 0 0 8 0 5 3 0 0 0 0 0 0 20 0 0 18 19 
    15 0 10 11 0 0 0 18 12 19 0 0 0 0 0 0 0 23 0 0 7 0 0 4 0 
    0 0 0 0 0 0 0 14 0 22 0 0 18 16 20 0 6 11 13 0 0 0 0 0 0 
    0 22 0 25 0 0 1 17 5 4 7 0 0 14 0 8 3 21 0 0 11 0 0 0 6 
    0 20 13 15 0 0 0 0 0 0 9 0 0 2 0 25 0 1 8 0 0 5 0 21 0 
    0 1 0 0 0 0 16 10 0 7 0 0 4 20 0 0 9 0 0 14 0 24 0 17 0 
    25 2 5 0 0 0 0 0 13 0 0 0 0 0 22 0 0 0 0 0 19 1 8 0 0 
    0 0 7 21 0 0 12 0 2 17 0 0 0 18 6 16 0 0 15 0 0 13 0 10 0 
    8 10 18 12 16 9 0 0 0 5 0 0 0 0 19 0 0 17 0 21 0 15 0 0 22 
    0 8 0 0 15 0 3 0 6 0 21 0 0 7 0 18 14 5 0 1 0 0 0 0 0 
    0 0 0 19 0 1 0 16 11 0 0 0 10 22 25 15 0 0 0 0 0 0 21 0 0 
    0 3 1 0 21 0 0 4 0 0 0 0 2 0 13 0 24 25 0 0 14 0 0 6 0 
    0 0 0 0 0 0 0 15 0 12 14 0 6 17 24 0 0 0 0 0 0 0 13 0 0 
    0 5 23 16 4 0 13 24 7 2 0 9 0 0 15 3 0 22 0 0 0 0 0 0 8 
    0 0 25 20 2 0 19 0 0 0 0 1 0 0 0 0 21 3 0 0 12 0 0 0 0 
    16 12 0 5 0 11 21 0 23 0 0 15 0 0 0 0 19 9 0 0 0 0 0 25 10 
    0 0 0 0 9 20 22 7 4 0 3 0 14 25 18 0 11 0 0 0 0 0 1 0 15 
    24 0 6 0 22 8 0 25 14 0 10 11 0 9 0 20 1 16 0 7 0 23 0 0 13 
    14 13 21 1 0 0 5 0 0 0 6 0 22 0 23 10 0 0 0 2 0 0 18 7 11
    0 means blank, filled in values are 1-25.

    Or, in another format -
    Code:
    ..LF..G.R.EX.JA..D.......
    B.S.M...J........RE.....A
    .......V....C.B..NL.PHY..
    .P...BW..MLV...UOSC....N.
    W.X.....YHD.PSU..G...CL.I
    .D.B.......J.XLQP...E....
    ..I..FY...H.EC......T..RS
    O.JK...RLS.......W..G..D.
    .......N.V..RPT.FKM......
    .V.Y..AQEDG..N.HCU..K...F
    .TMO......I..B.Y.AH..E.U.
    .A....PJ.G..DT..I..N.X.Q.
    YBE.....M.....V.....SAH..
    ..GU..L.BQ...RFP..O..M.J.
    HJRLPI...E....S..Q.U.O..V
    .H..O.C.F.U..G.RNE.A.....
    ...S.A.PK...JVYO......U..
    .CA.U..D....B.M.XY..N..F.
    .......O.LN.FQX.......M..
    .EWPD.MXGB.I..OC.V......H
    ..YTB.S....A....UC..L....
    PL.E.KU.W..O....SI.....YJ
    ....ITVGD.C.NYR.K.....A.O
    X.F.VH.YN.JK.I.TAP.G.W..M
    NMUA..E...F.V.WJ...B..RGK
    Me and my friend have double checked it, so it should be correct. The "numbers" version is generated from the "letters" version with a simple program.

    I changed my "blazingly fast" 9x9 solution to work with 25x25 board, and, well, it has been running for half an hour now. No solution yet .

    Anyone else want to take a stab at it?

    It HAS to be possible, since the puzzle is meant to be solved by a human...

    Bragging only in this thread, please (for now) , don't spoil it for me, yet.

  2. #2
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    For a 9x9 board, there are 9 ^ 9 ^ 9 = 96627050475552913618075908526912116283103450944214 766927315415537966391196809 possibilities, from which exactly one should be right. For a 25x25 board, there are 25 ^ 25 ^ 25 = 88817841970012523233890533447265625 ^ 25 of them. That is about 875 digits. Good luck in calculating that. You gotta have a huge amount of chance for doing this.
    Last edited by Brafil; 06-20-2009 at 06:27 AM.

  3. #3
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Yes, that's why we don't dumb brute-force it.

    A lot of the possibilities can be eliminated if you try them in a certain order, for example.

    My 9x9 solver solves any puzzle you throw at it in milliseconds. It only tries about 100000 configurations/s.

  4. #4
    Registered User
    Join Date
    May 2009
    Posts
    39
    Well I have a sudoku solver- in C++ that finds one, many, or no solutions...bad thing is the input I would have to type in by hand...unless I read it in a text file....

  5. #5
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    Oh. Maybe I should take a look at the algorithm. But It will need some time. Anyway, what I meant is that either the program is buggy (probably not) or it always takes much time. The complexity increases greatly. But I think you'll do it. Great work, your solver.

  6. #6
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    When I do a sudoku on paper, I fill the blank spaces (in pencil so I can erase it later) with all the possible values that could go in there and usually do that to all the blank squares in a row or column. Then I see which numbers only appear once in that row, column or big square and that HAS to be the right number, so I erase the possible numbers in that square and fill in the real number. I also remove that number from all the other possible numbers in the large square... Rinse, Lather, Repeat until it's done.

    Maybe you can use this "caching" technique in your algorithm?
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  7. #7
    Banned ಠ_ಠ's Avatar
    Join Date
    Mar 2009
    Posts
    687
    Quote Originally Posted by cpjust View Post
    When I do a sudoku on paper, I fill the blank spaces (in pencil so I can erase it later) with all the possible values that could go in there and usually do that to all the blank squares in a row or column. Then I see which numbers only appear once in that row, column or big square and that HAS to be the right number, so I erase the possible numbers in that square and fill in the real number. I also remove that number from all the other possible numbers in the large square... Rinse, Lather, Repeat until it's done.

    Maybe you can use this "caching" technique in your algorithm?
    I tried to make my sudoku program do that but it always ran into trouble when it encountered something along the line of
    Code:
    | 1 | 2 | 3 ||   |   |   ||   |   |   |
    |   |   |   || 1 | 2 | 3 ||   |   |   |
    |   |   |   ||   |   |   || 4 | 5 | 6 |
    Last edited by ಠ_ಠ; 06-20-2009 at 12:15 PM.
    ╔╗╔══╦╗
    ║║║╔╗║║
    ║╚╣╚╝║╚╗
    ╚═╩══╩═╝

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I made the necessary modifications to mine also, and it is taking a long time as well. I think it has been around 15 minutes so far.
    Not sure I want to burn my processor at 100% for that much longer.

    Any idea how long 16x16 ones take to solve?
    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"

  9. #9
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Well I have a sudoku solver- in C++ that finds one, many, or no solutions...bad thing is the input I would have to type in by hand...unless I read it in a text file....
    Just use redirection.
    Code:
    ./solver < input.txt
    Your code will get the input as if it was typed (from stdin).

    When I do a sudoku on paper, I fill the blank spaces (in pencil so I can erase it later) with all the possible values that could go in there and usually do that to all the blank squares in a row or column. Then I see which numbers only appear once in that row, column or big square and that HAS to be the right number, so I erase the possible numbers in that square and fill in the real number. I also remove that number from all the other possible numbers in the large square... Rinse, Lather, Repeat until it's done.

    Maybe you can use this "caching" technique in your algorithm?
    That is what I do with my program. It always tries the square with least possible fillers first, so if a puzzle (at any stage in the search) has a square with just one possible filler, the branching factor will be 1.

  10. #10
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    I made the necessary modifications to mine also, and it is taking a long time as well. I think it has been around 15 minutes so far.
    Not sure I want to burn my processor at 100% for that much longer.
    That surprised me, too, especially since this puzzle is meant to be solved by humans, and I THOUGHT my algorithm is pretty close to the one used by humans. Maybe we should go visit a human sudoku master and see how s/he does it .

    Code:
    real	688m38.768s
    user	685m27.038s
    sys	0m13.289s
    I SIGTERM'ed it.

  11. #11
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Here is a puzzle my friend sent me (for 9x9)
    Code:
    3 6 2 0 0 0 0 0 7
    0 0 0 0 3 0 0 0 6
    0 0 0 5 0 0 0 0 0
    0 0 0 8 0 0 4 0 1
    0 1 0 6 0 3 0 7 0
    2 0 3 0 0 9 0 0 0
    0 0 0 0 0 7 0 0 0
    9 0 0 0 8 0 0 0 0
    4 0 0 0 0 0 1 5 9
    I'm not sure what's so special about it, but it takes my code 0.102s to solve it, by far the longest I have seen (everything else I found could be solved in milliseconds).

    [edit]uh, nvm. There was a bug in my code. 15ms now.[/edit]
    Last edited by cyberfish; 06-20-2009 at 06:36 PM.

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    There is an elaborate solver written in C# by somone at Microsoft which uses all of the human solving techniques as well as the backtrack-solving I use. I wonder how well that would do.
    I think it would take so long because the cost paid when you have to backtrack is about 2^n where n is how many levels you have to backtrack by. With far more many holes compared to a 9x9 board, it's clear that it would take many more levels of magnitude longer. Even backtracking by 40 levels compared to 20 is going to take about 1 million times longer, and it's probably way more than that because I accidentally blew the stack upon my first run before optimising the amount of stack space used per call.
    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"

  13. #13
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    But that is assuming a branching factor of 2 everywhere. Meaning the square with the least amount of fillers in each stage is 2. That would be impossible for humans to solve.

    Most 9x9 puzzles have a branching factor of 1 in most if not all stages.

  14. #14
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    A difficult 16x16 puzzle -
    Code:
    0 2 14 0 0 0 16 4 0 0 0 1 0 0 5 0 
    0 0 9 0 0 10 0 1 0 0 0 0 0 4 0 0 
    0 0 0 0 13 6 0 0 0 14 0 0 15 12 0 16 
    6 5 10 0 8 2 0 0 0 12 0 0 0 1 0 7 
    9 0 5 4 1 0 0 2 0 0 0 0 12 0 7 0 
    0 0 0 0 11 0 0 13 0 3 0 0 0 0 0 1 
    0 0 0 0 16 0 0 0 13 10 15 9 14 0 4 0 
    10 0 0 11 0 4 8 15 0 0 0 0 5 0 13 0 
    0 11 0 1 0 0 0 0 10 7 4 0 3 0 0 6 
    0 7 0 2 14 16 6 10 0 0 0 11 0 0 0 0 
    16 0 0 0 0 0 1 0 12 0 0 14 0 0 0 0 
    0 4 0 10 0 0 0 0 15 0 0 2 16 5 0 11 
    11 0 12 0 0 0 14 0 0 0 13 7 0 9 6 2 
    8 0 7 9 0 0 11 0 0 0 14 10 0 0 0 0 
    0 0 4 0 0 0 0 0 11 0 2 0 0 8 0 0 
    0 6 0 0 12 0 0 0 9 8 0 0 0 14 1 0
    Takes my code ~15s on a AMD crap.

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by cyberfish View Post
    But that is assuming a branching factor of 2 everywhere. Meaning the square with the least amount of fillers in each stage is 2. That would be impossible for humans to solve.

    Most 9x9 puzzles have a branching factor of 1 in most if not all stages.
    I don't know why you're saying that. I'll define "branching factor" to mean how many numbers have not yet been eliminated for the cell with the lowest number of non-eliminated values. The minimum of this will almost certainly often be two for a medium difficulty puzzle, sometimes 3 or maybe even 4 for a hard/expert human level puzzle. Consider the XY-wing for example. There are two possibilities until you apply the rule and solve the square. If every move were of that difficulty then it is most certainly human-solveable! I know I could do it.

    Only the simplest of rules (given in the definition of the game) are required to work out the value when there is only one possibility, such as when there is only one number left in a given row. My solver fills all of such cases in without even having to recurse.

    No the branching factor wont be 2 everywhere, but for a few 1's here and there, the odd 3 may approximately balance that out. Sure that probably classifies it as a hard level puzzle, but lets not claim that hard means that no expert can solve it.
    Even the hardest Sudoku has been solved by a human, and it surely has a "branching factor" of 5 or more for some of the puzzle.
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sudoku 4 by 4 combination lister?
    By iskate4 in forum C++ Programming
    Replies: 2
    Last Post: 02-19-2009, 01:56 PM
  2. sudoku - arrays
    By rocketman50 in forum C++ Programming
    Replies: 2
    Last Post: 03-21-2008, 09:20 AM
  3. sudoku program
    By ElemenT.usha in forum C Programming
    Replies: 1
    Last Post: 02-12-2008, 12:51 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 - the new addiction
    By axon in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 11-07-2005, 11:39 PM