Forumite Members › General Topics › Tech › Makers & Builders › Programming/Code tips › Sudoku Solver
- This topic has 11 replies, 4 voices, and was last updated 6 years ago by
Tippon.
-
AuthorPosts
-
October 9, 2019 at 9:43 pm #37280
I am writing a Sudoku solving program in Atari Basic (I may convert it to a C++ console program later but it will not have a graphical UI).
The joystick driven UI is finished so I am now moving on to the logic. I thought there would be any number of example algorithms online but they all seem to rely on brute force back tracking. If anyone knows of a better method then please let me know but if not I am going to write my own code based on forced moves just like I do with pen and paper.
The code will first determine the numbers that are still needed in a row by subtracting the ones that are already entered and then try to fit them into empty squares from left to right. If a number will fit because it is still required in the row and it is not in the column or 3×3 grid of the empty square then the position will be tagged but not filled in and the program will try to fit the same number in the next empty square along. If a second possible fit is found in the row then the program will abandon that number and move on to the next required number. A number will only be filled in if it has only one possible location in the row. Once all the required numbers have been tried the program will do the same with the next row and then the columns. The process will repeat until the grid is complete or there are no more forced moves in which case it will then look for forced moves in the 3×3 grids before running through the rows and columns again and so on.
October 10, 2019 at 7:24 am #37286Wiki it – I’m afraid I cannot be bothered to write the pseudo-code of how I quickly solve them, but it is something like the constraint programming method in the wiki. The only ones I now find difficult are the ‘degenerate’ ones where there are multiple possible answers. (The so-called impossible ones that require back tracking)
February 5, 2020 at 10:40 pm #40393At last !
Finally found the bug in my program that was causing odd results.
I have a variable that counts the rows in a 3×3 square called SQROW but in one of the loops I spelt it SQRUW. As Atari BASIC takes notice of all the letters in a variable name SQRUW became a new variable with a default value of zero every time the program was run 🙄
The program only checks through all the rows repeatedly to find numbers that are unique in their row and in their 3×3 square so far.
To my surprise it has solved all the “Sun teaser” puzzles I have thrown at it 😀
I will post the code when I have tidied it up.
February 5, 2020 at 10:51 pm #40394Should have said numbers that are unique in their row, column and 3×3 square.
February 15, 2020 at 10:35 pm #40672I said I was going to tidy up my code and post it, and I will, but in the mean time I have updated it to process columns as well as rows. Below is the solution to the machine tricky problem in the Wiki link above. There is still some debug info in the shot that will be gone in the finished version !
I admit I gave it a little help with this one.
February 18, 2020 at 12:05 pm #40745Come to think of it, I may as well post the scrappy code. There are some comments so it should be worth a look.
If you fancy running the code in an Atari 800 emulator then you need to download it, copy it into your emulated hard drive folder from Windows, and then load it into Atari BASIC using ENTER “H6:SUDOKU.TXT”. Then type RUN obviously 🙂
The program is joystick driven and it will work with a gamepad if you configure your emulator to use one but if not you will need to use the numpad arrow keys and right control to select/deselect numbers (at least that’s the default on my emulator).
February 18, 2020 at 12:13 pm #40748Or maybe not !
File type .TXT not permitted for security reasons ?
February 18, 2020 at 12:59 pm #40749February 19, 2020 at 11:42 am #40786Did anyone manage to download the .TXT file from the link ?
Even if no one looked at the file I would like to know if it works 😀
February 19, 2020 at 12:13 pm #40788I was able to view the code on my phone, not tried it on anything else yet
February 19, 2020 at 12:21 pm #40789Thank you PM.
February 19, 2020 at 10:30 pm #40814I just tried it on the laptop. It opens the OneDrive site, then opens the file automatically, as a text file.
-
AuthorPosts
- You must be logged in to reply to this topic.
