Sudoku Algorithm

[Kickassjoe]

Does anyone have enough knowledge on how sudoku's are made to help me with this one? I have gotten it so that it makes a whole column that, most of the time, generates a random set of 1 - 9 numbers.

expandcollapse popup

;Script written by KickassJoe
#include<array.au3>
#include<GUIConstants.au3>


MakeTheBoard()



Func MakeTheBoard()
;columns
$col1 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$col2 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$col3 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$col4 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$col5 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$col6 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$col7 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$col8 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$col9 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
;rows
$row1 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$row2 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$row3 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$row4 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$row5 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$row6 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$row7 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$row8 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$row9 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)


$searchcol1 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$searchcol2 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$searchcol3 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$searchcol4 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$searchcol5 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$searchcol6 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$searchcol7 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$searchcol8 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$searchcol9 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)

$lcol1 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$lcol2 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$lcol3 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$lcol4 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$lcol5 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$lcol6 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$lcol7 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$lcol8 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
$lcol9 = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)

$pic = _ArrayCreate(1,2,3,4,5,6,7,8,9,10)
;column = up/down
;row = left/right  
    
    
For $i = 1 to 9
    $col1[$i] = Random(1,9,1);define the arrays
    $col2[$i] = Random(1,9,1)
    $col3[$i] = Random(1,9,1)
    $col4[$i] = Random(1,9,1)
    $col5[$i] = Random(1,9,1)
    $col6[$i] = Random(1,9,1)
    $col7[$i] = Random(1,9,1)
    $col8[$i] = Random(1,9,1)
    $col9[$i] = Random(1,9,1)
Next

#cs
$searchcol1[1] = _ArraySearch( $col1, $col1[1] , 2, 9)
While $searchcol1[1] <> - 1 And $searchcol1[1] <> @error
    $searchcol1[1] = _ArraySearch( $col1, $col1[1] , 2, 9)
    If $searchcol1[1] <> -1 Then
    $col1[$searchcol1[1]] = Random(1,9,1)
    EndIf
WEnd
#ce


    For $i = 1 to 9
$searchcol1[$i] = _ArraySearch( $col1, $col1[$i] , $i + 1, 9)
While $searchcol1[$i] <> - 1 And $searchcol1[$i] <> @error
    $searchcol1[$i] = _ArraySearch( $col1, $col1[$i], $i + 1, 9)
    If $searchcol1[$i] <> -1 Then
    $col1[$searchcol1[$i]] = Random(1,9,1)
    EndIf
WEnd

$searchcol2[$i] = _ArraySearch( $col2, $col2[$i] , $i + 1, 9)
While $searchcol2[$i] <> - 1 And $searchcol2[$i] <> @error
    $searchcol2[$i] = _ArraySearch( $col2, $col2[$i], $i + 1, 9)
    If $searchcol2[$i] <> -1 Then
    $col2[$searchcol2[$i]] = Random(1,9,1)
    EndIf
WEnd

$searchcol3[$i] = _ArraySearch( $col3, $col3[$i] , $i + 1, 9)
While $searchcol3[$i] <> - 1 And $searchcol3[$i] <> @error
    $searchcol3[$i] = _ArraySearch( $col3, $col3[$i], $i + 1, 9)
    If $searchcol3[$i] <> -1 Then
    $col3[$searchcol3[$i]] = Random(1,9,1)
    EndIf
WEnd


$searchcol4[$i] = _ArraySearch( $col4, $col4[$i] , $i + 1, 9)
While $searchcol4[$i] <> - 1 And $searchcol4[$i] <> @error
    $searchcol4[$i] = _ArraySearch( $col4, $col4[$i], $i + 1, 9)
    If $searchcol4[$i] <> -1 Then
    $col4[$searchcol4[$i]] = Random(1,9,1)
    EndIf
WEnd

$searchcol5[$i] = _ArraySearch( $col5, $col5[$i] , $i + 1, 9)
While $searchcol5[$i] <> - 1 And $searchcol5[$i] <> @error
    $searchcol5[$i] = _ArraySearch( $col5, $col5[$i], $i + 1, 9)
    If $searchcol5[$i] <> -1 Then
    $col5[$searchcol5[$i]] = Random(1,9,1)
    EndIf
WEnd

$searchcol6[$i] = _ArraySearch( $col6, $col6[$i] , $i + 1, 9)
While $searchcol6[$i] <> - 1 And $searchcol6[$i] <> @error
    $searchcol6[$i] = _ArraySearch( $col6, $col6[$i], $i + 1, 9)
    If $searchcol6[$i] <> -1 Then
    $col6[$searchcol6[$i]] = Random(1,9,1)
    EndIf
WEnd

$searchcol7[$i] = _ArraySearch( $col7, $col7[$i] , $i + 1, 9)
While $searchcol7[$i] <> - 1 And $searchcol7[$i] <> @error
    $searchcol7[$i] = _ArraySearch( $col7, $col7[$i], $i + 1, 9)
    If $searchcol7[$i] <> -1 Then
    $col7[$searchcol7[$i]] = Random(1,9,1)
    EndIf
WEnd

$searchcol8[$i] = _ArraySearch( $col8, $col8[$i] , $i + 1, 9)
While $searchcol8[$i] <> - 1 And $searchcol8[$i] <> @error
    $searchcol8[$i] = _ArraySearch( $col8, $col8[$i], $i + 1, 9)
    If $searchcol8[$i] <> -1 Then
    $col8[$searchcol8[$i]] = Random(1,9,1)
    EndIf
WEnd

$searchcol9[$i] = _ArraySearch( $col9, $col9[$i] , $i + 1, 9)
While $searchcol9[$i] <> - 1 And $searchcol9[$i] <> @error
    $searchcol9[$i] = _ArraySearch( $col9, $col9[$i], $i + 1, 9)
    If $searchcol9[$i] <> -1 Then
    $col9[$searchcol9[$i]] = Random(1,9,1)
    EndIf
WEnd










Next

_arraydisplay($col1, "check")

#include <GuiConstants.au3>

GuiCreate("MyGUI", 325, 265,-1, -1 , BitOR($WS_OVERLAPPEDWINDOW, $WS_CLIPSIBLINGS));316
$BakPick = GUICtrlCreatePic("data\Title.bmp",0,0,1010,650)
GuiCtrlSetState(-1,$GUI_DISABLE)
; GUI
$pic1 = GUICtrlCreatePic("data\Square.bmp", 0, 0,85,85)
$pic1 = GUICtrlCreatePic("data\Square.bmp", 0, 90,85,85)
$pic1 = GUICtrlCreatePic("data\Square.bmp", 0, 180,85,85)
$pic1 = GUICtrlCreatePic("data\Square.bmp", 120, 0,85,85)
$pic1 = GUICtrlCreatePic("data\Square.bmp", 120, 90,85,85)
$pic1 = GUICtrlCreatePic("data\Square.bmp", 120, 180,85,85)
$pic1 = GUICtrlCreatePic("data\Square.bmp", 240, 0,85,85)
$pic1 = GUICtrlCreatePic("data\Square.bmp", 240, 90,85,85)
$pic1 = GUICtrlCreatePic("data\Square.bmp", 240, 180,85,85)
GUICtrlSetState(-1,$GUI_DISABLE)
For $i = 1 to 9
    $lcol1[$i] = GUICtrlCreateLabel($col1[$i], 10, $i * 30 - 20, 10, 20)
    $lcol2[$i] = GUICtrlCreateLabel($col2[$i], 40, $i * 30 - 20, 10, 20)
    $lcol3[$i] = GUICtrlCreateLabel($col3[$i], 70, $i * 30 - 20, 10, 20)
    $lcol4[$i] = GUICtrlCreateLabel($col4[$i], 130, $i * 30 - 20, 10, 20)
    $lcol5[$i] = GUICtrlCreateLabel($col5[$i], 160, $i * 30 - 20, 10, 20)
    $lcol6[$i] = GUICtrlCreateLabel($col6[$i], 190, $i * 30 - 20, 10, 20)
    $lcol7[$i] = GUICtrlCreateLabel($col7[$i], 250, $i * 30 - 20, 10, 20)
    $lcol8[$i] = GUICtrlCreateLabel($col8[$i], 280, $i * 30 - 20, 10, 20)
    $lcol9[$i] = GUICtrlCreateLabel($col9[$i], 310, $i * 30 - 20, 10, 20)
    GUICtrlSetBkColor($lcol1[$i], $GUI_BKCOLOR_TRANSPARENT)
    GUICtrlSetBkColor($lcol2[$i], $GUI_BKCOLOR_TRANSPARENT)
    GUICtrlSetBkColor($lcol3[$i], $GUI_BKCOLOR_TRANSPARENT)
    GUICtrlSetBkColor($lcol4[$i], $GUI_BKCOLOR_TRANSPARENT)
    GUICtrlSetBkColor($lcol5[$i], $GUI_BKCOLOR_TRANSPARENT)
    GUICtrlSetBkColor($lcol6[$i], $GUI_BKCOLOR_TRANSPARENT)
    GUICtrlSetBkColor($lcol7[$i], $GUI_BKCOLOR_TRANSPARENT)
    GUICtrlSetBkColor($lcol8[$i], $GUI_BKCOLOR_TRANSPARENT)
    GUICtrlSetBkColor($lcol9[$i], $GUI_BKCOLOR_TRANSPARENT)
Next

GuiSetState()
While 1
    $msg = GuiGetMsg()
    Select
    Case $msg = $GUI_EVENT_CLOSE
        ExitLoop
    Case Else
        ;;;
    EndSelect
WEnd
Exit

EndFunc

P.S. This is a work in the making... I just started it tonight! Mainly because I was bored of runescape... and the other 4 games I have been playing lately... Just got bakc from the dance! . I was a 1337 pumpkin!

ALL help is appreciated! Oh yea, you need the Pics for it to work! ATTACHED!

Sudoku.zip

[ame1011]

For the love of jeebus and all that is holy, 2d arrays please and maybe some for loops

A full sudoku board can fit in one 2d array btw, i really suggest you read up on them.

Edited October 21, 2006 by ame1011

[Kickassjoe]

I have some for loops, and the code isn't really that long, or at least i dont think so, for what it does...

EDIT: TRUST ME, you would not want to see that same code without arrays and the for and while loops that are in there!

EDIT2: A full sudoku COULD fit into a 2d array... but who (that didn't make the code) would be able to figure that out? It would take me like 2 hours+ to figure that out! Gotta go to bed! Cya allz tomorrow! , don't be afraid to give me an answer, I will give you credit for all that you do (or, you might be able to give me credit, if you do a lot. )

Edited October 21, 2006 by Kickassjoe

[ame1011]

Heres something to show you what I'm talking about:

#include <Array.au3>

$rand_array = _ArrayCreate(1, 2, 3, 4, 5, 6, 7, 8, 9)
Dim $sudoku [9][9]
Dim $num1, $num2


;initialize board
for $a = 1 to 9
    ;swaping elements in rand array, doing this 20 times
    for $c = 1 to 20
        $num1 = Random(1, 9)
        $num2 = Random(1, 9)
        _ArraySwap($rand_array[$num1], $rand_array[$num2])
    Next
    for $b = 1 to 9
        ;placing the numbers in each row according to rand array
        $sudoku[$a][$b] = $rand_array[$b]
    Next
Next

all this does is populate a 9x9 board with numbers, this is not meant to be built upon and its untested. All it does is ensure that each row does not contain duplicates. 3x3 boxes and columns will contain duplicates using this method. Again, only use this as a means of understanding how to simplify your code.

Edited October 21, 2006 by ame1011

[theguy0000]

I have some for loops, and the code isn't really that long, or at least i dont think so, for what it does...

EDIT: TRUST ME, you would not want to see that same code without arrays and the for and while loops that are in there!

EDIT2: A full sudoku COULD fit into a 2d array... but who (that didn't make the code) would be able to figure that out? It would take me like 2 hours+ to figure that out! Gotta go to bed! Cya allz tomorrow! , don't be afraid to give me an answer, I will give you credit for all that you do (or, you might be able to give me credit, if you do a lot. )

please tell me you were being sarcastic on that edit2?

[Kickassjoe]

well... seeing as how I'm really bad with arrays, no, I wasn't being sarcastic

EDIT: Ame I already know that wouldn't work, seeing as how you didn't make the array have up to [9], because arrays start at [0]...

EDIT2: actually, I might be able to read that code, depends on how the array is set up...

Edited October 21, 2006 by Kickassjoe

[Kickassjoe]

With the use of 2d arrays... the code is now 90 lines, including whitespace. , it wasn't all from the 2d lines, I used the code that ame supplied, after i fixed a few errors, and it works great. Still need to figure out how to make it into a working sudoku though.

Edited October 21, 2006 by Kickassjoe

[Richard Robertson]

2d arrays should be more efficient than a bunch of single dimensioned arrays.

Which would you rather have?

$a = [[x,x,x],

[x,x,x],

[x,x,x]]

or

$a = [x,x,x]

$b = [x,x,x]

$c = [x,x,x]

[Kickassjoe]

Kirby, that was my point... but ame is trying to use less code while still getting the same effect.

Solving Sudoku puzzles can be expressed as a graph colouring problem. The aim of the puzzle in its standard form is to construct a proper 9-colouring of a particular graph, given a partial 9-colouring. The graph in question has 81 vertices, one vertex for each cell of the grid. The vertices can be labelled with the ordered

pairs (x,y) , where x and y are integers between 1 and 9. In this case, two distinct vertices labelled by (x,y) and (x',y') are joined by an edge if and only if:

x = x' or,

y = y' or,

x/3 = x'/3 and y/3 = y'/3

The puzzle is then completed by assigning an integer between 1 and 9 to each vertex, in such a way that vertices that are joined by an edge do not have the same integer assigned to them.

Edited: the pictures weren't showing up, so i wrote them in.

There is the algorithm for solving a sudoku, which might help in making one. . Except... I have no clue what it means! Thats new!

Edited October 21, 2006 by Kickassjoe

[Kickassjoe]

This is the C# and .NET code I found for finding the "fitness", or uniqueness of the squares. It was written by the president of "Marigold Inc." and he is said to be a "Microsoft MVP"

expandcollapse popup

/// <summary>
/// The Calculate Sudoku Fitness uses the uniqueness of columns, rows
/// and 3x3 squares in the grid to determine a fitness value
/// </summary>
/// <returns></returns>
private float CalculateSudokuFitness()
{
// set fitnesses for columns, rows, and squares initially to 0
float fitnessColumns = 0;
float fitnessRows = 0;
float fitnessSquares = 0;
// go through each column
for (int i = 0; i < 9; i++)
{
// Go through each cell in a column, add it to the ColumnMap according
// to the cell value
ColumnMap.Clear(); // clear the column map for each new column
for (int j = 0; j < 9; j++)
{
// check for uniqueness in row
if (ColumnMap[TheArray[i,j]] == null)
{
ColumnMap[TheArray[i,j]] = 0;
}
ColumnMap[TheArray[i,j]] = ((int)ColumnMap[TheArray[i,j]]) + 1;
}
// accumulate the column fitness based on the number of entries in the ColumnMap
fitnessColumns += (float)(1.0f/ (10-ColumnMap.Count))/9.0f;
//fitnessColumns += (float)Math.Exp(ColumnMap.Count*10 - 90)/9;
}
// go through each row next
for (int i = 0; i < 9; i++)
{
// Go through each cell in a row, add it to the RowMap according
// to the cell value
RowMap.Clear(); // clear the row map for each new row
for (int j = 0; j < 9; j++)
{
// check for uniqueness in row
if (RowMap[TheArray[j,i]] == null)
{
RowMap[TheArray[j,i]] = 0;
}
RowMap[TheArray[j,i]] = ((int)RowMap[TheArray[j,i]]) + 1;
}
// accumulate the row fitness based on the number of entries in the RowMap
fitnessRows += (float)(1.0f/ (10-RowMap.Count))/9.0f;
// fitnessRows += (float)Math.Exp(RowMap.Count*10 - 90)/9;
}
// go through next square
for (int l = 0; l < 3; l++)
{
for (int k = 0; k < 3; k++)
{
// Go through each cell in a 3 x 3 square, add it to the SquareMap according
// to the cell value
SquareMap.Clear(); // Clear the square map for each 3 x 3 square
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
// check for uniqueness in row
// check for uniqueness in row
if (SquareMap[TheArray[i + k*3,j + l*3]] == null)
{
SquareMap[TheArray[i+k*3,j+l*3]] = 0;
}
// accumulate the square fitness based on the number of entries in the SquareMap
SquareMap[TheArray[i + k*3,j + l*3]] = ((int)SquareMap[TheArray[i + k*3,j + l*3]]) + 1;
}
}
fitnessSquares += (float)(1.0f/ (10-SquareMap.Count))/9.0f;
}
}// The fitness of the entire Sudoku Grid is the product
// of the column fitness, row fitness and 3x3 square fitness
CurrentFitness = fitnessColumns * fitnessRows * fitnessSquares;
return CurrentFitness;
}

Could I implement this into my script in any way? Or convert it to AutoIt? (I don't know how hard that would be... but I'm guessing, pretty hard.)

[Kickassjoe]

I guess I will have to figure this one out myself... (or stop making this)

[jvanegmond]

I've posted the solution at Hackers Corp here: http://z10.invisionfree.com/HackersCorp/in...p?showtopic=107

[ame1011]

I've posted the solution at Hackers Corp here: http://z10.invisionfree.com/HackersCorp/in...p?showtopic=107

Manadar, the support forums are here for a reason, I'm sure many of us would prefer you did not promote outside sites and just post a straight solution. Especially if the link is dead....

KickAssJoe: that is easily transferrable into autoit

Edited October 22, 2006 by ame1011

[theguy0000]

Manadar, the support forums are here for a reason, I'm sure many of us would prefer you did not promote outside sites and just post a straight solution. Especially if the link is dead....

KickAssJoe: that is easily transferrable into autoit

??

I don't see any problem with what he did. If he managed to answer the question in another forum, I don't see a reason not to just put the link here...

And why shouldn't he post a straiught solution?

And the link is definitely not dead...

[jvanegmond]

Thanks for standing up for me, theguy0000.

Registering at the Hackers Corp forums are probably beyond ame1011's ability's..