Seuls les membres ayant 30 points peuvent parler sur le chat.

Forum Casio - Projets de programmation


Index du Forum » Projets de programmation » Playable Sudoku with Generator and Sovler
RedcmdHors ligneMembrePoints: 134 Défis: 2 Message

Playable Sudoku with Generator and Sovler

Posté le 05/09/2019 10:02

Hello allo

I am currently devopling a Sudoku generator complete with solver
and later, a player Sudoku game

It starts with a 9x9 matrix and fills it with random numbers
Sorts the matrix, so its a full valid sudoku grid with every row, column and 3x3 square containing the numbers 1-9
Removes random numbers from the grid
Then tries to solve it, it if does, it removes more numbers and tries again until it fails
Undoes the last removed numbers then repeats

.SD1~9*9 : .Sudoku ~ Generate 9x9 grid
Cliquer pour enrouler
Cls : BG-None
{9, 9 -> Dim Mat A
Seq(X, X, 1, 9, 1 -> List 1

For 1 -> Y To 9 Step 3
    For 1 -> X To 9 Step 3
        For 1 -> N To 9
            RanInt#(1, 9 -> R
            List 1[R
            List 1[N -> List 1[R
            Ans -> List 1[N
        Next
        0 -> N
        For Y -> W To Y + 2
            For X -> V To X + 2
                Isz N
                List 1[N
                Ans -> Mat A[W, V
                Text 6W, 6V, Ans
            Next
        Next
    Next
Next

Creates a 9x9 matrix and 9 long list filled with numbers 1 to 9
Scrambles the list
Starts at top corner
Writes the list to the 3x3 square at the cords XY
Then draws the number to screen

.SD2~SRT : .Sudoku ~ Sort valid Sudoku
Cliquez pour recouvrir
For 1 -> S To 8
    S = 3 Or S = 6 => Isz S
    3 + 3Int S⌟3 -> Q
    9 -> Dim List 1
    For 1 -> X To 9
        Mat A[S, X -> N
        List 1[N -> U
        
        If U :Then
            If S > X :Then
                X -> V : X -> R
            Else
                1 + 3Int X⌟3.5 -> R
                If S > R :Then
                    S -> V
                Else
                    R -> V
                IfEnd
                Isz R : Isz R
            IfEnd
            
            For V -> V To R
                For S + 1 -> W To Q
                    Mat A[W, V
                    If 0 = List 1[Ans :Then
                        N -> Mat A[W, V
                        Text 6W, 6V, N
                        Ans -> Mat A[S, X
                        Text 6S, 6X, Ans
                        X -> List 1[Ans
                        Goto 1
                    IfEnd
                Next
            Next
            
            X -> List 1[N
            Do
                U -> V : S -> W : Isz W
                Mat A[W, V
                If Q != W And List 1[Ans :Then
                    Isz W
                    Mat A[W, V
                IfEnd
                Ans -> Mat A[S, V
                Text 6S, 6V, Ans
                N -> Mat A[W, V
                Text 6W, 6V, N
                List 1[Ans -> U
                V -> List 1[Ans
                Ans -> N
            LpWhile U
        Else
            X -> List 1[N
        IfEnd
        Lbl 1
    Next
    
    9 -> Dim List 1
    For 1 -> Y To 9
        Mat A[Y, S -> N
        List 1[N -> U
        
        If U :Then
            If S >= Y :Then
                Y -> W : Y -> R
            Else
                3Int Y⌟3.5 -> R
                Isz R
                If S >= R :Then
                    S -> W : Isz W
                Else
                    R -> W
                IfEnd
                Isz R : Isz R
            IfEnd
            
            For W -> W To R
                For S + 1 -> V To Q
                    Mat A[W, V
                    If 0 = List 1[Ans :Then
                        N -> Mat A[W, V
                        Text 6W, 6V, N
                        Ans -> Mat A[Y, S
                        Text 6Y, 6S, Ans
                        Y -> List 1[Ans
                        Goto 2
                    IfEnd
                Next
            Next
            
            N -> T
            Y -> List 1[N
            Do
                U -> W : S -> V : Isz V
                Mat A[W, V
                If (Y != W Or N != T) And Q != V And List 1[Ans :Then
                    Isz V
                    Mat A[W, V
                IfEnd
                Ans -> Mat A[W, S
                Text 6W, 6S, Ans
                N -> Mat A[W, V
                Text 6W, 6V, N
                List 1[Ans -> U
                W -> List 1[Ans
                Ans -> N
            LpWhile U
        Else
            Y -> List 1[N
        IfEnd
        Lbl 2
    Next
Next

This sorts the 9x9 matrix so its a valid sudoku grid (numbers 1-9 in every row, column and 3x3 square)
Starts at the top left corner and starts sorting the top row, left to right
Then does the 1st column, 2nd row etc
It goes across the row, making a list of all the numbers
If it finds a duplicate, it tries to swap it with a non-duplicate number within the same 3x3 square
If it cant, it goes back to the previous location of the duplicate number and force swaps it with the number below it
If that number is a duplicate, it will go to the location of that number
It will keep going back until it finds a non-duplicate number
Here is a video and doc explaining it a bit better
https://youtu.be/LHCHH5siBCg
Download doc

.SD3~CLS : .Sudoku ~ Clear Random Numbers
Cliquez pour recouvrir
For 1 -> N To 20
    Do
        RanInt#(1, 9 -> X
        RanInt#(1, 9 -> Y
    LpWhile 0 = Mat A[Y, X
    0 -> Mat A[Y, X
    Text 6Y, 6X, " "
    10 - X -> X : 10 - Y -> Y
    0 -> Mat A[Y, X
    Text 6Y, 6X, " "
Next

Chooses random XY cord
Checks to see if the spot is already cleared
If not Then clears that space and the space 180 degrees around the Sudoku from it
Repeats N times

.SD4~STR : .Sudoku ~ Saves Matrix to Strings
Cliquez pour recouvrir
"0123456789" -> Str 9
"" -> Str 1 : "" -> Str 2
For 1 -> Y To 9
    For 1 -> X To 9
        Str 1 + StrMid(Str 9, Mat A[Y, X] + 1, 1) -> Str 1
        Str 2 + StrMid(Str 9, Mat A[X, Y] + 1, 1) -> Str 2
Next : Next

"" -> Str 3
For 1 -> Y To 9 Step 3
    For 1 -> X To 9 Step 3
        For Y -> W To Y + 2
            For X -> V To X + 2
                Str 3 + StrMid(Str 9, Mat A[W, V] + 1, 1) -> Str 3
Next : Next : Next : Next

"" -> Str 4
For 1 -> T To 27
Str 4 + "+-------+" -> Str 4 : Next
Str 4 -> Str 5
Str 4 -> Str 6
"123456789" -> Str 9

Saves the 9x9 matrix to strings 1, 2, 3, 4, 5 and 6
Saves "123456789" to string 9

Valid 9x9 Sudoku in the Matrix
Cliquez pour recouvrir
194  572  836
8 6  4    725
25   3 9  194

783  9 5   4
4 2  836  5 9
6   7 1  283

945  6 7   12
671    3  4 8
328  154  967

Str 1 saves the entire maxtrix, from left to right, top to bottom
194572836806400725250309194783905040402836509060701283945600012671003408328154967
Str 2 saves the entire maxtrix, from top to bottom, left to right
182740963905806472460320518...
Str 3 saves the entire maxtrix, each 3x3 square from left to right, top to bottom
194806250572400309836725194...

Fills Str 4, 5 and 6 with 243 0's

.SD5~SLV : .Sudoku ~ Solves the Sudoku, Single Candidate
Cliquez pour recouvrir
For 1 -> W To 7 Step 3
    For W -> Y To W + 2
        0 -> X
        StrMid(Str 1, 9Y - 8, 9) -> Str 11
        Lbl 0
        "" -> Str 10
        StrSrc(Str 11, "0", X + 1) -> X
        If X : Then
            0 -> T
            3Int X⌟3.5 -> V
            StrMid(Str 1, 9Y - 8, 9) + StrMid(Str 2, 9X - 8, 9) + StrMid(Str 3, 3V + 9W - 8, 9) -> Str 8
            For 1 -> N To 9
                StrMid(Str 9, N, 1) -> Str 7
                If StrSrc(Str 8, Str 7) :Then
                    Str 10 + "0" -> Str 10
                Else
                    Isz T : N
                    Str 10 + Str 7 -> Str 10
                IfEnd
            Next
            If T = 1 : Then 1 -> θ
                Text 6Y, 6X, Ans
                StrLeft(Str 1, 9Y + X - 10) + StrMid(Str 9, Ans, 1) + StrRight(Str 1, 90 - 9Y - X) -> Str 1
                StrLeft(Str 2, 9X + Y - 10) + StrMid(Str 9, Ans, 1) + StrRight(Str 2, 90 - 9X - Y) -> Str 2
                X + 2V + 3Y + 6W - 10 -> T
                StrLeft(Str 3, T) + StrMid(Str 9, Ans, 1) + StrRight(Str 3, 80 - T) -> Str 3 : "*-------*" -> Str 10
            IfEnd
            W = 1 => StrLeft(Str 4, 9X + 81Y - 90) + Str 10 + StrRight(Str 4, 324 - 9X - 81Y) -> Str 4
            W = 4 => StrLeft(Str 5, 9X + 81Y - 333) + Str 10 + StrRight(Str 5, 567 - 9X - 81Y) -> Str 5
            W = 7 => StrLeft(Str 6, 9X + 81Y - 576) + Str 10 + StrRight(Str 6, 810 - 9X - 81Y) -> Str 6
            Goto 0
        IfEnd
    Next
Next

Starts in the top corner, goes from left to right, top to bottom
Checks if theres a number
If not Then checks the numbers in the same row, column and 3x3 square, to see if theres only one number that could go in that spot
If so, then writes that number to Str 1, 2, 3, 4, 5 and 6
https://www.sudokuoftheday.com/techniques/single-candidate/

.SD6~SLV : .Sudoku ~ Sloves the Sudoku, Single Position
Cliquez pour recouvrir
For 1 -> Y To 7 Step 3
    Y = 1 => Str 4 -> Str 11
    Y = 4 => Str 5 -> Str 11
    Y = 7 => Str 6 -> Str 11
    
    For 1 -> X To 7 Step 3
        StrMid(Str 11, 9X - 8, 27) + StrMid(Str 11, 9X + 73, 27) + StrMid(Str 11, 9X + 154, 27) -> Str 8
        
        For 1 -> N To 9
            StrMid(Str 9, N, 1) -> Str 7
            StrSrc(Str 8, Str 7)
            If Ans :Then
                If StrSrc(Str 8, Str 7, Ans + 1) = 0 :Then
                    Ans - 1
                    X + MOD(Int Ans⌟9, 3 -> V
                    Y + Int Ans⌟27 -> W
                    Text 6W, 6V, N
                    StrLeft(Str 1, 9W + V - 10) + StrMid(Str 9, N, 1) + StrRight(Str 1, 90 - 9W - V) -> Str 1
                    StrLeft(Str 2, 9V + W - 10) + StrMid(Str 9, N, 1) + StrRight(Str 2, 90 - 9V - W) -> Str 2
                    V + 6Int V⌟3.5 + 3W + 18Int W⌟3.5 - 4
                    StrLeft(Str 3, Ans) + StrMid(Str 9, N, 1) + StrRight(Str 3, 80 - Ans) -> Str 3
                    Y = 1 => StrLeft(Str 4, 9V + 81W - 90) + "/-------/" + StrRight(Str 4, 324 - 9V - 81W) -> Str 4
                    Y = 4 => StrLeft(Str 5, 9V + 81W - 333) + "/-------/" + StrRight(Str 5, 567 - 9V - 81W) -> Str 5
                    Y = 7 => StrLeft(Str 6, 9V + 81W - 576) + "/-------/" + StrRight(Str 6, 810 - 9V - 81W) -> Str 6
                    1 -> θ : 1 -> Z
                IfEnd
            IfEnd
        Next
    Next
Next

Checks each number to see if it only has one place left to go
If so, writes the number to str 1, 2, 3, 4, 5 and 6
Each number in the matrix leads to 9 numbers in each str 81 * 9 = 729, 729 / 4 = 243 numbers per string
Str4 saves the top 27 numbers of the matrix, from left to right, top to bottom
Str 4
Cliquer pour enrouler
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000030000000000000000000000001000000000000000000000000000000000000000000000000000000000007000000000000006080000000000000000000000000000

Str 5 saves the middle 27 numbers of the matrix, from left to right, top to bottom
Str 5
Cliquer pour enrouler
000000000000000000000000000000000000020000000000000000000006000000000000100000000000000000000000000000000000000000000000000000100000700000000000000050009000000000000050009000000000020400000000000000000000000000000000000000000

Str 6 saves the bottom 27 numbers of the matrix, from left to right, top to bottom
Too many numbers :p...

https://www.sudokuoftheday.com/techniques/single-position/


Any help with the algorithms and optimizations is very welcome
This website explains a lot of what Im doing - https://www.sudokuoftheday.com/about/difficulty/
I will be constantly updating this, making it faster and smaller
It is highly recommended to run this on C.BASIC
as displaying the numbers to the screen is very slow
When this is all finished, it will be able to generate a sudoku in the background as you are playing a game of sudoku!

Sudoku.g1m

Fichier joint


MassenaHors ligneRédacteurPoints: 840 Défis: 3 Message

Citer : Posté le 05/09/2019 13:23 | #


Enverything in Basic Casio ? Wow dude, you are a genius ! But it's not fast to make an engine to move the cursor, it isn't ?
Now, Luke. A true gentleman suscribe to Planet Casio. This reminds me of a puzzle...
RedcmdHors ligneMembrePoints: 134 Défis: 2 Message

Citer : Posté le 05/09/2019 21:07 | #


Currently theres only a generator and solver
The slow part is drawing to the screen, but ofc I wont do that when its fininshed as it would show the player the solved sudoku
The generator and solver can still be speed up, it doesn't take the best path is solving it right now

When playing a sudoku
The user will have higher prioity, but only when they are not doing anything, the generator/solver program will have a small amount of time to calculate part of the sudoku
It will give time back to the player, if the player isn't doing anything it will go back to the solver
As long as the time that the solver uses is small enough (but not too small), the game shouldn't be too slow :P
RedCMD#4299 - Discord
Mandelbrot SNKEmini Minesweeper Sudoku
Sentaro21Hors ligneMembrePoints: 564 Défis: 0 Message

Citer : Posté le 06/09/2019 02:40 | #


@Redcmd
It ’s a great program.
It works well in C.Basic.
To work in the 90+E high resolution screen,
Since the width of the space is small, it works well by adding one more space. .
Je continue à développer C.Basic. (Il est compatible avec Basic Casio.)
Overclocking utilitaire Ftune/Ptune2/Ptune3 est également disponible.
Si vous avez des questions ou un rapport de bogue, n'hésitez pas à me le faire savoir.
RedcmdHors ligneMembrePoints: 134 Défis: 2 Message

Citer : Posté le 06/09/2019 02:41 | #


Still got a long way to go
Its currently massivey unoptimized, but I will slowly get there :P
Would take soo long to test without C.Basic
RedCMD#4299 - Discord
Mandelbrot SNKEmini Minesweeper Sudoku
HackcellHors ligneMembrePoints: 1115 Défis: 6 Message

Citer : Posté le 06/09/2019 09:59 | #


Can we get some information about the time spend by each function in order to generate/solve a grid ?
I usually spend meow time cosplaying as a diligent student...
So it can get pretty stressful.
That's exactly why PC is such a happy place for meow to be ⭐
RedcmdHors ligneMembrePoints: 134 Défis: 2 Message

Citer : Posté le 08/09/2019 05:40 | #


Thats a tricky question
Generatoring then solving a grid takes about a minute
if you dont draw anything to the screen, apart from the final grid (because draw commands are super slow)
But the final outcome might not be a genuine grid, only because theres not a 100% chance that the grid has only one solution
So it could take multiple goes, before getting a genuine grid
Then theres the problem of grading the grid: easy, medium and hard

After a grid is solved, more places a removed, then its resolved to test if its still possiblt to solve via human techniques
This will take the longest
up to a max of 30min!
but Im expecting less than 10min
RedCMD#4299 - Discord
Mandelbrot SNKEmini Minesweeper Sudoku
HackcellHors ligneMembrePoints: 1115 Défis: 6 Message

Citer : Posté le 08/09/2019 09:51 | #


That a great algorithm then
I've used one on a PC with python that used brute force (kinda) to solve grids and it always tooks hours
I usually spend meow time cosplaying as a diligent student...
So it can get pretty stressful.
That's exactly why PC is such a happy place for meow to be ⭐
LephenixnoirHors ligneAdministrateurPoints: 15483 Défis: 136 Message

Citer : Posté le 08/09/2019 09:56 | #


On of the best algorithms (to the extent of my knowledge) to solve this kind of combinatorial problems is the dancing links. It's absurdly elegant and can be used whenever the problem looks like set covering and backtracking

I guess it is not very suitable for calculators though, except in its array form. xD
RedcmdHors ligneMembrePoints: 134 Défis: 2 Message

Citer : Posté le 08/09/2019 10:56 | #


Im also wondering on how to grade the grids
The most common way is to play the sudoku like a human player and give different amounts of points towards different techniques used: Single Candidate, Single Position etc

no algorithm is go for a calculator :P
they all take thousands of iterations to finish

RedCMD#4299 - Discord
Mandelbrot SNKEmini Minesweeper Sudoku

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2019 | Il y a 49 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd