Pages: [1]   Go Down
Author Topic: arduinosudoku  (Read 1174 times)
0 Members and 1 Guest are viewing this topic.
Australia
Offline Offline
Full Member
***
Karma: 7
Posts: 210
AVR Microcontrollers
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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 3*3*3*3*3*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:


Quote
//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

« Last Edit: October 17, 2010, 09:16:57 pm by carl47 » Logged

Australia
Offline Offline
Full Member
***
Karma: 7
Posts: 210
AVR Microcontrollers
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

The second part is:

Quote
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 == smiley-cool && (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

« Last Edit: October 17, 2010, 09:02:06 pm by carl47 » Logged

Australia
Offline Offline
Full Member
***
Karma: 7
Posts: 210
AVR Microcontrollers
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

And one last function:

Quote
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



« Last Edit: October 17, 2010, 09:11:59 pm by carl47 » Logged

UK
Offline Offline
God Member
*****
Karma: 13
Posts: 903
Twitter: @simonmonk2
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Why? Because you can of course!
Excellent.
smiley
Logged

--
My New Arduino Book: http://www.arduinobook.com

Australia
Offline Offline
Full Member
***
Karma: 7
Posts: 210
AVR Microcontrollers
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Australia
Offline Offline
Full Member
***
Karma: 7
Posts: 210
AVR Microcontrollers
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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/
« Last Edit: November 22, 2010, 02:44:21 am by carl47 » Logged

Pages: [1]   Go Up
Jump to: