arduinosudoku

Forum 2005-2010 (read only) General Exhibition
#1

I have always been a fan of sudoku.

The first program I wrote for sudoku used visual basic.

I then rewrote it in C to run on linux.
I expanded it to C++ and incorporated all the functions in a .dll
I used this .dll in a VB program to run on windows.

http://sourceforge.net/projects/mysudoku/files/

I wanted a break from my weather station project.

http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1283073954

It is not possible to have the whole sudoku solution in memory.
This would take 81 * what I have used.
My sudokuarray uses 33333*3 = 729 bytes.

It could be done with external memory.

The program prints out a random completed sudoku each time its run.

A LCD display and a joystick would be able to display the full sudoku as I have done in the linux/windows program.

The program uses brute force. Random numbers are selected until we have a complete solution. No attempt has been made to use the finer rules of sudoku construction.

It’s runs in fractions of a second on a PC.
It takes 1 to 20 seconds on the arduino.

The code is in three parts the first part is:

//sketch for Arduino 2009 (with 328)
//each time the sketch runs it prints out a random completed sudoku

char sudokuarray[3][3][3][3][3][3];
char arraynumber = 0;

void setup()
{
Serial.begin(9600); // initialize serial communications at 9600
randomSeed(analogRead(0));
}//end of setup

void loop()
{
generatesudoku();
if(arraynumber > 80)
{
printout(); //solved sodoku
while ( 0 == 0)
asm volatile(“nop”); //sit here after printed one sudoku
}//end of print out

}//end of loop

void generatesudoku(void) //generate a sudoku
{
construct(); //start with new array
arraynumber = 0;
boolean noblanks = true;

while((arraynumber < 80) && noblanks)
{
char x = random(9);
char y = random(9);
char number = random(9);
setnumber(x,y,number);
checkselection();

for(char xl = 0; xl <3; xl++)
{
for(char yl = 0; yl <3; yl++)
{
for(char xs = 0; xs <3; xs++)
{
for(char ys = 0; ys <3; ys++)
{

char numberselected = 0; //find how many zero’s in this box
for(char yn = 0; yn <3; yn++)
{
for(char xn = 0; xn <3; xn++)
{
if( sudokuarray[xl][yl][xs][ys][xn][yn] == 0)
numberselected += 1; //count number in this box
}//next xn
}//next yn
if(numberselected == 9)
noblanks = false;
}//next ys
}//next xs
}//next yl
}//next xl…checked all for any blanks

}//end of get random sudoku

}//end of generate sudoku

#2

The second part is:

void checkselection(void) //see if one or two numbers can be selected
{
while(findsingle() == 0) //find if one can be selected
asm volatile(“nop”);
}// end of check selection

char findsingle(void) //select standalone number and return if found
{
char bignumber = 0; //holds the selected number
char nonselect = 1; //flag for standalone number = 0 for true

for(char xl = 0; xl <3; xl++)
{
for(char yl = 0 ; yl <3; yl++)
{
for(char xs = 0; xs <3 ;xs++)
{
for(char ys = 0; ys <3; ys++)
{
char numberselected = 0; //find how many zero’s in this box

for(char yn = 0; yn <3; yn++)
{
for(char xn = 0; xn <3; xn++)
{
if( sudokuarray[xl][yl][xs][ys][xn][yn] == 0)
numberselected += 1; //count number in this box
else
bignumber = sudokuarray[xl][yl][xs][ys][xn][yn];
}//next xn
}//next yn
if((numberselected == 8) && (bignumber < 0x40))
{
setnumber(xl *3 + xs,yl *3 + ys,bignumber - 0x31); //select the stadalone
nonselect = 0; //we have found a stand alone number
}//end of number selected if
}//next ys
}//next xs
}//next yl
}//next xl…all done
return nonselect;
}//end of select standalone number

void setnumber(char x, char y, char number)
{//values 0 t0 8
boolean selected = false; //check to see if number already selected
boolean nopossible = false; //check to see if no possibilities to select exist
boolean crossedout = false; //check to see if the number has been crossed out
if(sudokuarray[x/3][y/3][x%3][y%3][number%3][number/3] == 0)
crossedout = true; //the number has been crossed out

for(int yn = 0; yn <3; yn++) // in this number box
{
for(int xn = 0; xn <3; xn++)
{
if (sudokuarray[x/3][y/3][x%3][y%3][xn][yn] > 0x40)
selected = true; //this number already selected
if (sudokuarray[x/3][y/3][x%3][y%3][xn][yn] > 0)
nopossible = true; //at least one possible number exists
}//next xn
}//next yn
if(( ! selected) && (nopossible) && (! crossedout)) //number not selected
{//select if a its a possible and its not crossed out
sudokuarray[x/3][y/3][x%3][y%3][number%3][number/3] += 0x10;
arraynumber += 1; //we have a number selected
char j = 0;
char i = 0;
for (j = 0; j <3; j++) //set all to zero except selected number in box
{
for (i = 0; i <3; i++)
{
if(sudokuarray[x/3][y/3][x%3][y%3][j] < 0x40)
_ sudokuarray[x/3][y/3][x%3][y%3][j] = 0;_
* }//end of i for*
}// end of j for
for (j = 0; j <3; j++) //horizontal line cannot have this number
{
* for (i = 0; i <3; i++)*
* {*
_ if(sudokuarray[j][y/3][y%3][number%3][number/3] < 0x40)
sudokuarray[j][y/3][y%3][number%3][number/3] = 0;
* }//end of i for*
}// end of j for
for (j = 0; j <3; j++) //vertical line cannot have this number
{
* for ( i = 0; i <3; i++)
{
if(sudokuarray[x/3][j][x%3][number%3][number/3] < 0x40)
sudokuarray[x/3][j][x%3][number%3][number/3] = 0;
}//end of i for*
}// end of j for
for (j = 0; j <3; j++) //box of 9 numbers cannot have this number
{
* for ( i = 0; i <3; i++)
{
if(sudokuarray[x/3][y/3][j][number%3][number/3] < 0x40)
sudokuarray[x/3][y/3][j][number%3][number/3] = 0;
}//end of i for*
}// end of j for
* }//end of select number*
}//end of set a number
void printout()
{
* for(char yl = 0; yl < 3; yl++)
{
for(char ys = 0; ys < 3; ys++)
{
for(char i = 0; i < 81; i++)*
Serial.print(byte(0xaf));
Serial.println("");_

* for(char yn = 0; yn < 3; yn++)*
*{ *
* for(char xl = 0;xl<=2;xl++)*
{
_ Serial.print(byte(0x7c));
* for(char xs = 0; xs < 3; xs++)
{
Serial.print(" ");
Serial.print(byte(0x7c));
for(char xn = 0; xn < 3; xn++)
{
Serial.print(" ");
char n = 0;
n = sudokuarray[xl][yl][xs][ys][xn][yn]; //the solved sudoku*
* if(n > 0x40)
n -= 0x10; //number is selected so show as 1 to 9*
* if(n == 0)
n = 0xad; //crossout sign*
Serial.print(n);
* }//next xn*
* }//next xs*
Serial.print(" “);
}//next xl
Serial.print(byte(0x7c));
Serial.print(” “);
Serial.print(byte(0x7c));
Serial.println(”");
}//next yn
}//next ys
* for(char i = 0; i < 81; i++)
Serial.print(byte(0xaf));
Serial.println("");
}//next yl*
}//end of printout the sudoku
[/quote]_

#3

And one last function:

void construct(void)
{
//fill the arrray with pencil 1-9 in all the small squares -81 of them
char number =0x31; //start with “1” and move on to “9”
for(char xl = 0;xl<=2;xl++)
{
for(char yl = 0;yl<=2;yl++)
{
for(char xs = 0;xs<=2;xs++)
{
for(char ys = 0;ys<=2;ys++)
{
for(char yn = 0;yn<=2;yn++)
{
for(char xn = 0;xn<=2;xn++)
{
sudokuarray[xl][yl][xs][ys][xn][yn] = number;//fill the first step
number = number + 1; //put in 1 to 9
}//next xn
}//next yn
number=0x31; //1 to 9 in box now do next
}//next ys
}//next xs
}//next yl
}//next xl…all done
}//end of construct

#4

Why? Because you can of course! Excellent. :)

#5

Simon thanks.

Yes I do it because its there to be done. And of course it keeps me entertained.

I dont want to construct a full arduino sudoku myself because my priority is to finish my weather station.

I would really like to see someone construct one.

All or part of the code is completely free to reuse.

#6

I have added to the basic sudoku program by the addition of 32k byte ram.

http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1290379685

This now allows tracking of the sudoku solution steps.

In the sketch sudokuram.pde the arduino now prints out the random sudoku followed by the start position for this solution.

You can set how hard the solution will be by setting a constant.

Copy the printout to a .txt file with a font 8 size and both the start and solution will print on 1 A4 sheet.

Download sudokuram.pde from:

http://sourceforge.net/projects/mysudoku/files/

#7