Graham Dearsley Posted April 30, 2020 Share Posted April 30, 2020 With the current virus lockdown in place the government has been sending me tips on how to use up my spare time and they said that doing puzzles like Sudoku is a good idea. Well I had a better idea, write a program to solve the puzzles ! Below is my first go at it. I am quite proud of the GUI but then I decided to make the logic just WORK . The worst offender is that the column routine is just a copy and paste of the rows and called with a GOTO. Not finished by a long way but here it is. Will solve about 85% of puzzles you will find in newspapers. SUDOKU.BAS SUDOKU.TXT 3 Quote Link to comment Share on other sites More sharing options...
Preppie Posted April 30, 2020 Share Posted April 30, 2020 Nice work Given that you say it's not near completion I'm not gonna start pointing out problems now Just that there's no point starting a solve on boards with <17 clues as these are unsolvable (you probably knew that). Quote Link to comment Share on other sites More sharing options...
Graham Dearsley Posted April 30, 2020 Author Share Posted April 30, 2020 Yep and no back tracking either ? . The thing so far is to take the slog out of doing the row and column compare for yourself. If the routine can't finish on its own then you can help it and hit solve again ? Quote Link to comment Share on other sites More sharing options...
Rybags Posted April 30, 2020 Share Posted April 30, 2020 Nice. I've never actually played the game but gave this a shot using the example in the Wikipedia article. There used to be a word game in a newspaper I bought each day back in the 90s. I can't remember exactly how it worked but I think it was where you started with a 5 or 6 letter word then had to change a letter at a time to get to the target word at the bottom. Feeling "lazy" I wrote a SAS program on the mainframe that produced every possible combination then displayed it so you could choose your own solution. Quote Link to comment Share on other sites More sharing options...
Graham Dearsley Posted April 30, 2020 Author Share Posted April 30, 2020 Did it solve it ? Quote Link to comment Share on other sites More sharing options...
Graham Dearsley Posted April 30, 2020 Author Share Posted April 30, 2020 I mean the sudoku ? There is a similar puzzle to yours in the Sun's weekend puzzel section. Quote Link to comment Share on other sites More sharing options...
zzip Posted April 30, 2020 Share Posted April 30, 2020 (edited) 1 hour ago, Graham Dearsley said: With the current virus lockdown in place the government has been sending me tips on how to use up my spare time and they said that doing puzzles like Sudoku is a good idea. Well I had a better idea, write a program to solve the puzzles ! Below is my first go at it. I am quite proud of the GUI but then I decided to make the logic just WORK . The worst offender is that the column routine is just a copy and paste of the rows and called with a GOTO. Not finished by a long way but here it is. Will solve about 85% of puzzles you will find in newspapers. SUDOKU.BAS 6.29 kB · 5 downloads SUDOKU.TXT 7.21 kB · 6 downloads Cool I wrote a sudoku solver in C a few years back when I was bored. Like you it solves maybe 85% of puzzles I throw at it. The ones it can't solve always require a technique by the person that seems rather tedious to turn into code. I've always wanted to code a "Crypto Quote Solver". Those puzzles where they change every letter to another? I once wrote something that could aid you, but I always wanted to see if I could make one that could solve it on it's own. I already have a dictionary of words in data form that it can use. Edited April 30, 2020 by zzip spelling Quote Link to comment Share on other sites More sharing options...
Rybags Posted April 30, 2020 Share Posted April 30, 2020 The puzzle I presented it was solved - https://en.wikipedia.org/wiki/Sudoku Top right, with solution below it. I replicated the puzzle then used turbo mode at various points to get to the solution quicker. Quote Link to comment Share on other sites More sharing options...
Graham Dearsley Posted April 30, 2020 Author Share Posted April 30, 2020 Nice to know ? Quote Link to comment Share on other sites More sharing options...
Preppie Posted April 30, 2020 Share Posted April 30, 2020 Given that you can write code to solve the puzzle could you also code it to create new puzzles and turn it into a game as well as an aid? Quote Link to comment Share on other sites More sharing options...
Graham Dearsley Posted April 30, 2020 Author Share Posted April 30, 2020 Ah. Yes and No not really ?. All the methods I thought of were of the very slow try it and see kind. Don't let me stop you though ? Quote Link to comment Share on other sites More sharing options...
Graham Dearsley Posted April 30, 2020 Author Share Posted April 30, 2020 And not surprising looking at the wiki article. Wayne Gould spent 6 years devising a program to create Sudoku puzzles and it says he became one of the worlds most influential people ! Seeing as the papers charge good money for a same day solution I wonder if I am wasting another day of not being seriously rich (A quote from the Young ones TV series, the Oil episode) ? Quote Link to comment Share on other sites More sharing options...
Rybags Posted May 1, 2020 Share Posted May 1, 2020 In theory couldn't you just populate a few cells with random numbers, ensuring they don't invalidate the solution. Then run the remainder of the program. Once finished you create your puzzle by deleting everything except a small subset of what's there. I'm guessing any valid Sudoku problem starts with at least one number in every row/column so that only one result is possible? Quote Link to comment Share on other sites More sharing options...
Graham Dearsley Posted May 1, 2020 Author Share Posted May 1, 2020 Really not that simple. Try entering a valid puzzle but putting one of the numbers in the wrong square, without breaking the rules. Try pressing Solve and I think you will find that the program gets to a point where a solution isn't possible ? Quote Link to comment Share on other sites More sharing options...
Rybags Posted May 1, 2020 Share Posted May 1, 2020 OK... I guess you could seed a puzzle and make it unsolvable pretty easily. Is there some method they use to generate the ones you see in newspapers/books? Or would they likely be brute-force computer generated with invalid ones just thrown out? Quote Link to comment Share on other sites More sharing options...
zzip Posted May 1, 2020 Share Posted May 1, 2020 10 hours ago, Rybags said: In theory couldn't you just populate a few cells with random numbers, ensuring they don't invalidate the solution. Then run the remainder of the program. Once finished you create your puzzle by deleting everything except a small subset of what's there. I'm guessing any valid Sudoku problem starts with at least one number in every row/column so that only one result is possible? Yes, You could use recursion where if it picks a wrong number that leads to an invalid solution, it simply backtracks and tries the next number. Repeat until you come up with a minimum set of numbers that lead to a solution. Not sure how well this would work on an 8-bit though using recursion, you'd probably want to do it on something with more power. Quote Link to comment Share on other sites More sharing options...
dmsc Posted May 1, 2020 Share Posted May 1, 2020 Hi! On 4/30/2020 at 10:39 AM, Graham Dearsley said: With the current virus lockdown in place the government has been sending me tips on how to use up my spare time and they said that doing puzzles like Sudoku is a good idea. Well I had a better idea, write a program to solve the puzzles ! Below is my first go at it. I am quite proud of the GUI but then I decided to make the logic just WORK . The worst offender is that the column routine is just a copy and paste of the rows and called with a GOTO. Not finished by a long way but here it is. Will solve about 85% of puzzles you will find in newspapers. SUDOKU.BAS 6.29 kB · 11 downloads SUDOKU.TXT 7.21 kB · 13 downloads Great program. Long time ago I programmed a sudoku solver in C using the "dancing links" algorithm, then tried porting it to Atari using CC65, but uses too much RAM so it is not possible to implement directly - the algorithm uses a matrix with the cells in two linked lists, for sudoku the matrix is 729x324 = 236196 cells in size! So, I programmed an approximation to the algorithm using bits for the cells, so the full matrix is only 29889 bytes. Today I ported the program to FastBasic and added an interface similar to your program. This program can solve any solvable sudoku, and even generate a new sudoku if you specify too few filled numbers at the start. To make the program faster, I implemented four routines in machine-language, included are FastBasic sources and assembly. Sadly, you need current development version to compile it. Have Fun! sudoku-accel.asm sudoku-scr.fb sudoku-scr.xex 3 Quote Link to comment Share on other sites More sharing options...
Graham Dearsley Posted May 2, 2020 Author Share Posted May 2, 2020 I am working my way through the book "Programming Principles and Practice using C++" by Bjarne Stroustrup. This is partly to update me from C to modern C++ but mostly to improve my practice ?. I tried to make the GUI in my Sudoku program follow best practice by calling subroutines like functions (given local variables are still global) and then gave up on that with the logic ? Has anyone been able to make the full tick graphics routines in that book work ? Quote Link to comment Share on other sites More sharing options...
dmsc Posted May 3, 2020 Share Posted May 3, 2020 Hi! 12 hours ago, Graham Dearsley said: I am working my way through the book "Programming Principles and Practice using C++" by Bjarne Stroustrup. This is partly to update me from C to modern C++ but mostly to improve my practice ?. I tried to make the GUI in my Sudoku program follow best practice by calling subroutines like functions (given local variables are still global) and then gave up on that with the logic ? Has anyone been able to make the full tick graphics routines in that book work ? I haven't read that book, but I see that it uses the "fltk" (Fast Light Took Kit) library for the graphics examples. Perhaps you have to install FLTK separately before compiling the examples? It seems an odd choice to use that library in the book, as it is very old and not pretty, but it is simple indeed. Have Fun! Quote Link to comment Share on other sites More sharing options...
+MrFish Posted May 3, 2020 Share Posted May 3, 2020 On 5/1/2020 at 6:21 PM, dmsc said: Sadly, you need current development version to compile it. Is there a list somewhere of planned features for the next release version? Quote Link to comment Share on other sites More sharing options...
dmsc Posted May 3, 2020 Share Posted May 3, 2020 Hi! 13 hours ago, MrFish said: Is there a list somewhere of planned features for the next release version? You can list issues assigned to a milestones on github: - Already implemented: https://github.com/dmsc/fastbasic/milestone/2?closed=1 - Planed: https://github.com/dmsc/fastbasic/milestone/2 Also, there are a few minor bug-fixes already, and the change to allow accessing DATA from assembly code. Have Fun! 1 Quote Link to comment Share on other sites More sharing options...
+MrFish Posted May 3, 2020 Share Posted May 3, 2020 Some nice additions coming up. Quote Link to comment Share on other sites More sharing options...
Like us on Facebook
Follow us on Twitter
AtariAge on Instagram
Watch us on YouTube
Chat on Discord
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.