Sign in to follow this  
Followers 0
CodeMaster Rapture

Sudoku Generator Woes

10 posts in this topic

Greetings everyone,

My wife loves Sudoku puzzles and wants an X-Mas gift of "Sudoku's Galore". So, I sat down last night and pumped out some code to create a pre-solved Sudoku puzzle (then I can hide random parts based on difficulty). I went over 5 or 6 methods of doing this. I don't think my final product is very efficient, but I do know it works!

So, for those unsure of how a Sudoku board looks:

;     0 1 2  3 4 5  6 7 8  <-- Column
;Row +======+======+=======+
; 0  | 0|1|2| 0|1|2| 0|1|2 |
; 1  | 3|4|5| 3|4|5| 3|4|5 |
; 2  | 6|7|8| 6|7|8| 6|7|8 |
;   +======+======+=======+
; 3  | 0|1|2| 0|1|2| 0|1|2 |
; 4  | 3|4|5| 3|4|5| 3|4|5 |
; 5  | 6|7|8| 6|7|8| 6|7|8 |
;   +======+======+=======+
; 6  | 0|1|2| 0|1|2| 0|1|2 |
; 7  | 3|4|5| 3|4|5| 3|4|5 |
; 8  | 6|7|8| 6|7|8| 6|7|8 |
;   +======+======+=======+

There are nine 3x3 squares, numbered 0-8 above. I'm trying to figure out an equation for spit out the Row(num,pos) and Column(num,pos) if given the Square(num,pos). For example:

Square(4,7) == Row(5,4) == Column(4,5)

Any idea how to calculate this? Right now I have 2 nested switch statements with these values hard-coded, but it looks ugly as sin and I think it might be slowing my code down a hair (81 comparisions per call, and about 9 calls per Square == 729 comparisions). I also am having some trouble with my non-duplicate logic, but I can better handle this when the above problem is solved.

Thanx,

-CMR

Share this post


Link to post
Share on other sites



It will take you about 1 search to find implementations in Java/perl/Tcl/Tk with google. There are even som sites dealing with the the theory of solving Suduko. Search for +gametree +sudoku. hmm, guess your a tad late if your suposed to have it finishied by tomorow..:P

Share this post


Link to post
Share on other sites

I've searched google for quite some time and have come up with numerous sources, but it still doesn't answer my question. I guess I'll have to keep looking...

There has to be a simple equation out there I just don't know where to look.

Thanx,

CMR

Share this post


Link to post
Share on other sites

#4 ·  Posted (edited)

I've searched google for quite some time and have come up with numerous sources, but it still doesn't answer my question. I guess I'll have to keep looking...

There has to be a simple equation out there I just don't know where to look.

Thanx,

CMR

I have written a Sudoku solver/teacher but not in Autoit. But despite that I don't understand your question-

Square(4,7) == Row(5,4) == Column(4,5) doesn't make sense to me.

There are 9 squares of 9 but what is Square(4,7)??

There are 9 Columns so what is Column(4,5)??

Edited by martin

Serial port communications UDF Includes functions for binary transmission and reception.printing UDF Useful for graphs, forms, labels, reports etc.Add User Call Tips to SciTE for functions in UDFs not included with AutoIt and for your own scripts.Functions with parameters in OnEvent mode and for Hot Keys One function replaces GuiSetOnEvent, GuiCtrlSetOnEvent and HotKeySet.UDF IsConnected2 for notification of status of connected state of many urls or IPs, without slowing the script.

Share this post


Link to post
Share on other sites

I've searched google for quite some time and have come up with numerous sources, but it still doesn't answer my question. I guess I'll have to keep looking...

There has to be a simple equation out there I just don't know where to look.

Thanx,

CMR

I have written a Soduku solver/teacher but not in Autoit. But despite that I don't understand your question-

Square(4,7) == Row(5,4) == Column(4,5) doesn't make sense to me.

There are 9 squares of 9 but what is Square(4,7)??

There are 9 Columns so what is Column(4,5)??


Serial port communications UDF Includes functions for binary transmission and reception.printing UDF Useful for graphs, forms, labels, reports etc.Add User Call Tips to SciTE for functions in UDFs not included with AutoIt and for your own scripts.Functions with parameters in OnEvent mode and for Hot Keys One function replaces GuiSetOnEvent, GuiCtrlSetOnEvent and HotKeySet.UDF IsConnected2 for notification of status of connected state of many urls or IPs, without slowing the script.

Share this post


Link to post
Share on other sites

Let me rephrase.

Given the image below, I can easily calculate the Row(X,Y) and Column(X,Y) for any board position.

Posted Image

This is accomplished with the following code:

Global $Board   [82]
Global $Row     [10][10]
Global $Column  [10][10]
Global $Square  [10][10]

Func _GetRowXY($i_Board_Pos)
    Local $Coord[2] = [-1,-1]
    
    $Coord[0] = Int(($i_Board_Pos/9)) + 1
    $Coord[1] = Mod($i_Board_Pos,9)
    
    If ($Coord[1] == 0) Then
        $Coord[0] -= 1
        $Coord[1] = 9
    EndIf
    
    Return $Coord
EndFunc

;Same as _GetRowXY() except X and Y are switched
Func _GetColumnXY($i_Board_Pos)
    Local $Coord[2] = [-1,-1]
    
    $Coord[0] = Mod($i_Board_Pos,9)
    $Coord[1] = Int(($i_Board_Pos/9)) + 1
    
    If ($Coord[0] == 0) Then
        $Coord[1] -= 1
        $Coord[0] = 9
    EndIf
    
    Return $Coord
EndFunc

So, now I can easily add one value to 3 arrays at the same time ($Board, $Row, and $Column). Now, the problem is that I cannot figure out an equation to figure out the Square(X,Y) of any board position or even which board elements belong in a specific square.

Am I making any sense? I know I confused the heck out of my Father-in-Law when I tried to explain it to him.

-CMR

Share this post


Link to post
Share on other sites

Let me rephrase.

Given the image below, I can easily calculate the Row(X,Y) and Column(X,Y) for any board position.

Posted Image

This is accomplished with the following code:

Global $Board   [82]
Global $Row     [10][10]
Global $Column  [10][10]
Global $Square  [10][10]

Func _GetRowXY($i_Board_Pos)
    Local $Coord[2] = [-1,-1]
    
    $Coord[0] = Int(($i_Board_Pos/9)) + 1
    $Coord[1] = Mod($i_Board_Pos,9)
    
    If ($Coord[1] == 0) Then
        $Coord[0] -= 1
        $Coord[1] = 9
    EndIf
    
    Return $Coord
EndFunc

;Same as _GetRowXY() except X and Y are switched
Func _GetColumnXY($i_Board_Pos)
    Local $Coord[2] = [-1,-1]
    
    $Coord[0] = Mod($i_Board_Pos,9)
    $Coord[1] = Int(($i_Board_Pos/9)) + 1
    
    If ($Coord[0] == 0) Then
        $Coord[1] -= 1
        $Coord[0] = 9
    EndIf
    
    Return $Coord
EndFunc

So, now I can easily add one value to 3 arrays at the same time ($Board, $Row, and $Column). Now, the problem is that I cannot figure out an equation to figure out the Square(X,Y) of any board position or even which board elements belong in a specific square.

Am I making any sense? I know I confused the heck out of my Father-in-Law when I tried to explain it to him.

-CMR

I can see why you need to know the X,Y coords of a square, So that small square No. 12 is 2,3. I don't see why you want to have another function to tell you it's 3,2. But that's beside the point.

Your functions would be slightly simpler if you said

Func _GetRowXY($i_Board_Pos)

Local $Coord[2] = [-1,-1]

$Coord[0] = Mod($i_Board_Pos - 1,9) + 1

$Coord[1] = Int(($i_Board_Pos - 1)/9) + 1

Return $Coord

EndFunc

Assuming $i_Board_Pos is >= 1.

Do you mean given a small square number 25 say, how do you work out it is in big square 3?


Serial port communications UDF Includes functions for binary transmission and reception.printing UDF Useful for graphs, forms, labels, reports etc.Add User Call Tips to SciTE for functions in UDFs not included with AutoIt and for your own scripts.Functions with parameters in OnEvent mode and for Hot Keys One function replaces GuiSetOnEvent, GuiCtrlSetOnEvent and HotKeySet.UDF IsConnected2 for notification of status of connected state of many urls or IPs, without slowing the script.

Share this post


Link to post
Share on other sites

"So man has sown the wind and reaped the world. Perhaps in the next few hours there will no remembrance of the past and no hope for the future that might have been." & _"All the works of man will be consumed in the great fire after which he was created." & _"And if there is a future for man, insensitive as he is, proud and defiant in his pursuit of power, let him resolve to live it lovingly, for he knows well how to do so." & _"Then he may say once more, 'Truly the light is sweet, and what a pleasant thing it is for the eyes to see the sun.'" - The Day the Earth Caught Fire

Share this post


Link to post
Share on other sites

Yes Martin,

Thank you for the optimization idea. I just threw the function together without much thought. I do need to figure out how to calculate what cells are part of the 3x3 squares and also how to get thier X,Y positions.

-CMR

Share this post


Link to post
Share on other sites

Yes Martin,

Thank you for the optimization idea. I just threw the function together without much thought. I do need to figure out how to calculate what cells are part of the 3x3 squares and also how to get thier X,Y positions.

-CMR

Maybe this will be of use. But it's just an idea- I haven't checked it!

Global Dim $sn[10][2]

WhatBlock(17,$sn);to get the info on the block which square number 17 is in


;Function WhatBlock
;input $psq a number from 1 to 81
;        $ssnn a 10 x 2 integer array to be filled
;
;Returns sets array $sn giving coords of all squares in the same big square as the small square $psq
;           $sn[0][0],$sn[0][1] = XY of large square in 3 x 3 matrix
;           $sn[1][0], $sn[1][1] = XY coord of first square in this big Sqare in 9 x 9 matrix
;.
;.
;.
;            $sn[9][0], $sn[9][1] = XY coord of ninth square in this big Sqare
Func Whatblock($psq,ByRef $ssnn)
local $col,$row,$rr,$cc,$btop,$bleft

 $col = Mod(($psq - 1),9) + 1;
 $row = Int(($psq - 1)/9) + 1;
 $btop = 0;
 while $btop < $row 
   $btop += 3
  wend;
 $btop = $btop - 2;//the top of the block;

 $bleft = 0;
  while $bleft < $col
   $bleft += 3
  Wend;
 $bleft = $bleft - 2;the left side of the block

 $ssnn[0][0] = 1 + Int($bleft/3);the number of big squares across
 $ssnn[0][1] = 1 + Int($btop/3); the number down .

$q = 1
 for $rr = $btop to $btop + 2 
  for $cc = $bleft to $bleft + 2
        $ssnn[$q][0] = $rr
    $ssnn[$q][1] = $cc
    $q += 1
   Next
  Next

EndFunc;

Serial port communications UDF Includes functions for binary transmission and reception.printing UDF Useful for graphs, forms, labels, reports etc.Add User Call Tips to SciTE for functions in UDFs not included with AutoIt and for your own scripts.Functions with parameters in OnEvent mode and for Hot Keys One function replaces GuiSetOnEvent, GuiCtrlSetOnEvent and HotKeySet.UDF IsConnected2 for notification of status of connected state of many urls or IPs, without slowing the script.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0