Sudoku Solver

Post your NXJ projects, project ideas, etc here!

Moderators: 99jonathan, roger, imaqine

Sudoku Solver

Postby ChrisB01 » Thu Oct 23, 2008 8:30 pm

This program will allow you to turn your NXT in to a portable sudoku solver. The interface is quite usable for a 100*64 size screen but the algorithm is quite simple so it will fail at really hard sudoku's or ones that can't be solved by logic.

This is the source code:
Code: Select all
import javax.microedition.lcdui.Graphics;

import lejos.nxt.Button;

import lejos.nxt.Sound;



public class SodokuSolver {

   

   /*



   This program allows you to turn your NXT in to a portable sodoku solver.

   use the left and right arrows to scroll through the cells and buttons and

   press enter to click the buttons or select the cells, when you select a cell

   the cell indicator in the bottom right goes black, to deselect a cell press

   the escape button. The logic used is rather simple, the program only checks

   if there is only 1 possible number for a box or if there is only 1 possible

   space for a number in a row or column, so don't be surprised if it wont solve

   very hard sodoku's.

   

   ChrisB



   */

   static SodokuSolver program;



   int[][] squareValues = new int[9][9];



   int focus = 0;

   int selected = 0;



   float percentBar;



   Graphics g = new Graphics();



   public static void main(String[] args) {



      program = new SodokuSolver();



      program.squareValues[0][0] = 7;

      program.squareValues[0][3] = 3;

      program.squareValues[0][5] = 5;

      program.squareValues[0][8] = 8;



      program.squareValues[1][2] = 3;

      program.squareValues[1][4] = 7;

      program.squareValues[1][6] = 4;



      program.squareValues[2][1] = 8;

      program.squareValues[2][7] = 6;



      program.squareValues[3][0] = 4;

      program.squareValues[3][3] = 2;

      program.squareValues[3][5] = 8;

      program.squareValues[3][8] = 9;



      program.squareValues[4][1] = 1;

      program.squareValues[4][7] = 5;



      program.squareValues[5][0] = 3;

      program.squareValues[5][3] = 6;

      program.squareValues[5][5] = 1;

      program.squareValues[5][8] = 2;



      program.squareValues[6][1] = 9;

      program.squareValues[6][7] = 3;



      program.squareValues[7][2] = 8;

      program.squareValues[7][4] = 4;

      program.squareValues[7][6] = 7;



      program.squareValues[8][0] = 2;

      program.squareValues[8][3] = 5;

      program.squareValues[8][5] = 6;

      program.squareValues[8][8] = 4;



      program.gui();

      program.watchButtons();



   }



   void gui() {



      g.clear();

      g.autoRefresh(false);



      int cellSize = 8;

      int startX = 0;

      int startY = 0;



      int x = 0;

      int y = 0;



      if (focus > 45 && focus != 82 && focus != 83 && focus != 84) {

         startY = 0 - cellSize - 1;

      }



      while (y < 9) {

         while (x < 9) {

            if (focus == (x + 1) + (y * 9)) {

               g.fillRect(startX + (x * cellSize), startY + (y * cellSize), cellSize, cellSize);

               if (squareValues[x][y] == 0) {

                  g.drawString(" ", startX + (x * cellSize) + 2, startY + (y * cellSize) + 1, true);

               } else {

                  g.drawString(Integer.toString(squareValues[y][x]), startX + (x * cellSize) + 2, startY + (y * cellSize) + 1, true);

               }

               if (focus == selected) {

                  g.drawString(Integer.toString(squareValues[y][x]), 80, 50, true);

               } else {

                  g.drawString(Integer.toString(squareValues[y][x]), 80, 50, false);

               }

            } else {

               g.drawRect(startX + (x * cellSize), startY + (y * cellSize), cellSize, cellSize);

               if (squareValues[x][y] == 0) {

                  g.drawString(" ", startX + (x * cellSize) + 2, startY + (y * cellSize) + 1, false);

               } else {

                  g.drawString(Integer.toString(squareValues[y][x]), startX + (x * cellSize) + 2, startY + (y * cellSize) + 1, false);

               }

            }

            x++;

         }

         x = 0;

         y++;

      }



      if (focus == 82) {

         g.drawRect(70, 8, 29, 9);

         g.drawString("Solve", 71, 9, true);

      } else {

         g.drawRect(74, 8, 29, 9);

         g.drawString("Solve", 75, 9, false);

      }



      if (focus == 83) {

         g.drawRect(70, 19, 29, 9);

         g.drawString("Clear", 71, 20, true);

      } else {

         g.drawRect(74, 19, 29, 9);

         g.drawString("Clear", 75, 20, false);

      }



      g.drawRect(74, 30, 24, 9);

      if (focus == 84) {

         g.drawString("Quit", 75, 31, true);

      } else {

         g.drawString("Quit", 75, 31, false);

      }



      g.refresh();



   }



   void drawStatus(int cellsComplete) {



      g.clear();



      if (cellsComplete != 0) {



         g.drawString("Solving...", 28, 26);



         g.drawRect(9, 50, 81, 6);

         g.fillRect(9, 50, cellsComplete, 6);



         g.refresh();



      } else {

         g.drawString("Solve Failed", 25, 26);



         g.refresh();



         try {

            Thread.sleep(2000);

         } catch (InterruptedException e) {

         }

      }



   }



   void watchButtons() {



      while (true) {



         if (Button.RIGHT.isPressed()) {

            if (focus == 84) {

               focus = 0;

            } else {

               focus++;

            }

            gui();

            try {

               Thread.sleep(100);

            } catch (InterruptedException e) {

            }

         }



         if (Button.LEFT.isPressed()) {

            if (focus == 0) {

               focus = 84;

            } else {

               focus--;

            }

            gui();

            try {

               Thread.sleep(100);

            } catch (InterruptedException e) {

            }

         }



         if (Button.ENTER.isPressed()) {

            if (focus == 82 || focus == 83 || focus == 84) {

               if (focus == 82) {

                  int[][] newCells = solve(squareValues);

                  if (newCells != null) {

                     Sound.beepSequenceUp();

                     squareValues = newCells;

                     gui();

                  } else {

                     Sound.beepSequence();

                  }

               } else if (focus == 83) {

                  squareValues = new int[9][9];

                  Sound.beep();

                  gui();

               } else if (focus == 84) {

                  System.exit(0);

               }

            } else {

               while (Button.ENTER.isPressed()) {

               }

               if (focus != 0) {

                  selected = focus;

                  gui();

                  while (!Button.ESCAPE.isPressed()) {

                     if (Button.RIGHT.isPressed()) {

                        while (Button.RIGHT.isPressed()) {

                        }

                        if (squareValues[(focus - 1) % 9][(focus - 1) / 9] != 9) {

                           squareValues[(focus - 1) % 9][(focus - 1) / 9] = squareValues[(focus - 1) % 9][(focus - 1) / 9] + 1;

                        } else {

                           squareValues[(focus - 1) % 9][(focus - 1) / 9] = 0;

                        }

                        gui();

                     }



                     if (Button.LEFT.isPressed()) {

                        while (Button.LEFT.isPressed()) {

                        }

                        if (squareValues[(focus - 1) % 9][(focus - 1) / 9] != 0) {

                           squareValues[(focus - 1) % 9][(focus - 1) / 9] = squareValues[(focus - 1) % 9][(focus - 1) / 9] - 1;

                        } else {

                           squareValues[(focus - 1) % 9][(focus - 1) / 9] = 9;

                        }

                        gui();

                     }

                  }

                  while (Button.ESCAPE.isPressed()) {

                  }

                  selected = 0;

                  gui();

               }



            }

         }

      }

   }



   static boolean checkLegal(int y, int x, int val, int[][] cells) {



      if (cells[y][x] != 0)

         return false;

      return checkCol(x, val, cells) == false && checkRow(y, val, cells) == false && checkSquare(y, x, val, cells) == false;

   }



   static boolean checkCol(int x, int val, int[][] cells) {



      int y = 0;

      while (y < 9) {

         if (cells[y][x] == val) {

            return true;

         }

         y++;

      }

      return false;

   }



   static boolean checkRow(int y, int val, int[][] cells) {



      int x = 0;

      while (x < 9) {

         if (cells[y][x] == val)

            return true;

         x++;

      }

      return false;

   }



   static boolean checkSquare(int y, int x, int val, int[][] cells) {



      int boxRowOffset = (x / 3) * 3;

      int boxColOffset = (y / 3) * 3;

      for (int k = 0; k < 3; ++k) {

         for (int m = 0; m < 3; ++m) {

            if (val == cells[boxColOffset + m][boxRowOffset + k]) {

               return true;



            }

         }

      }

      return false;

   }



   static int[][] solve(int[][] cells) {



      int[][] newCells = cells;



      int x = 0;

      int y = 0;



      int cellsComplete = 0;



      while (x < 9) {

         while (y < 9) {

            if (newCells[y][x] != 0) {

               cellsComplete++;

            }

            y++;

         }

         x++;

         y = 0;

      }



      if (cellsComplete == 0)

         return new int[9][9];



      program.drawStatus(cellsComplete);



      int onlyPossibilty = 0;

      boolean finished = false;

      boolean changedSomething = true;



      while (finished == false && changedSomething == true) {



         x = 0;

         y = 0;



         finished = true;

         changedSomething = false;

         while (x < 9) {

            while (y < 9) {

               if (newCells[y][x] == 0) {

                  onlyPossibilty = 0;

                  finished = false;

                  int values = 1;

                  while (values < 10) {

                     // System.out.println(values);

                     if (checkLegal(y, x, values, newCells) == true) {

                        if (onlyPossibilty == 0) {

                           onlyPossibilty = values;

                        } else {

                           values = 10;

                           onlyPossibilty = 0;

                        }

                     }

                     values++;

                  }

                  if (onlyPossibilty != 0) {

                     // writeMatrix(cells);

                     // System.out.println("Changed:" + y + " " + x +

                     // " to " + onlyPossibilty + " Legal:" +

                     // checkLegal(y, x, onlyPossibilty, newCells));

                     newCells[y][x] = onlyPossibilty;

                     changedSomething = true;

                     cellsComplete++;

                     program.drawStatus(cellsComplete);

                  }

               }

               y++;

            }

            x++;

            y = 0;

         }



         if (finished == false) {



            int x2;

            int y2;



            onlyPossibilty = 0;

            finished = false;

            changedSomething = true;



            while (finished == false && changedSomething == true) {



               // System.out.println("Iteration");



               x = 0;

               y = 0;



               finished = true;

               changedSomething = false;

               while (y < 9) {

                  while (x < 9) {

                     // System.out.println("X:" + x + " Y:" + y);

                     if (newCells[y][x] == 0) {

                        finished = false;

                        int values = 1;

                        while (values < 10) {

                           onlyPossibilty = 1;



                           // System.out.println("Y Checking " +

                           // values);

                           if (checkLegal(y, x, values, newCells) == true) {

                              // System.out.println(values +

                              // " can go here " + y + " " + x);

                              y2 = 0;

                              while (y2 < 9) {

                                 if (y2 != y) {

                                    if (checkLegal(y2, x, values, newCells) == true) {

                                       onlyPossibilty = 0;

                                       // System.out.println("Found another posibility "

                                       // + y2 + " " + x);

                                       y2 = 10;

                                    }

                                 }

                                 y2++;

                              }



                              if (onlyPossibilty == 1) {

                                 // System.out.println("Changed:" + y

                                 // + " " + x + " to " + values +

                                 // " Legal:" + checkLegal(y, x,

                                 // values, newCells));

                                 newCells[y][x] = values;

                                 values = 10;

                                 changedSomething = true;

                                 cellsComplete++;

                                 program.drawStatus(cellsComplete);

                              } else {

                                 // System.out.println("X Checking "

                                 // + values);



                                 onlyPossibilty = 1;



                                 x2 = 0;

                                 while (x2 < 9) {

                                    if (x2 != x) {

                                       if (checkLegal(y, x2, values, newCells) == true) {

                                          onlyPossibilty = 0;

                                          // System.out.println("Found another posibility "

                                          // + y + " " + x2);

                                          x2 = 10;

                                       }



                                    }

                                    x2++;

                                 }



                                 if (onlyPossibilty == 1) {

                                    // System.out.println("Changed:"

                                    // + y + " " + x + " to " +

                                    // values + " Legal:" +

                                    // checkLegal(y, x, values,

                                    // newCells));

                                    newCells[y][x] = values;

                                    values = 10;

                                    changedSomething = true;

                                    cellsComplete++;

                                    program.drawStatus(cellsComplete);

                                 }



                              }

                           }

                           values++;

                        }

                     }

                     x++;

                  }

                  y++;

                  x = 0;

               }

               // System.out.println("End Iteration " + changedSomething);

            }

         }

      }



      if (cellsComplete == 81) {

         return newCells;

      } else {

         program.drawStatus(0);

         return null;

      }



   }



}


Chris
ChrisB01
Advanced Member
 
Posts: 189
Joined: Sat Mar 15, 2008 12:19 pm
Location: UK

Return to NXJ Projects

Who is online

Users browsing this forum: Yahoo [Bot] and 1 guest

more stuff