Sudoku Generator Woes

[CodeMaster Rapture]

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

[Uten]

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..

[CodeMaster Rapture]

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

[martin]

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 December 24, 2006 by martin

[martin]

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)??

[CodeMaster Rapture]

Let me rephrase.

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

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

[martin]

Let me rephrase.

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

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?

[The Kandie Man]

You could also look at these for ideas:

http://www.autoitscript.com/forum/index.ph...5&hl=sudoku

http://www.autoitscript.com/forum/index.ph...5&hl=sudoku

http://www.autoitscript.com/forum/index.ph...4&hl=sudoku

There are more, just search the Example Scripts forum for "sudoku".

[CodeMaster Rapture]

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

[martin]

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!

expandcollapse popup

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;