login  Naam:   Wachtwoord: 
Registreer je!
 Scripts:
Scripts > Overige > Java > SudokuSolver

SudokuSolver

Auteur: Maarten - 20 februari 2009 - 13:41 - Gekeurd door: Koen - Hits: 2331 - Aantal punten: 1.63 (4 stemmen)




Zoals de titel reeds zegt is dit een klasse die in staat is eenvoudige sudoku's op te lossen (= de standaard vierkante versie).

Wie de regels van sudoku niet kent kan deze gemakkelijk terugvinden op internet, maar de basisregel is als volgt: een getal, van 1 tot 9, mag slechts 1 keer in zijn rij, kolom en vierkant (3x3) voorkomen.

Bij het meegeven van een sudoku dienen de waarden die we nog niet kennen 0 te zijn. Het script loopt door de puzzel tot alle nullen weggewerkt zijn.

Er zit een kleine main-klasse bij om het gebruik ervan aan te tonen.

Code:
SimpleSudokuSolver.java
java code - Bekijk de code zonder highlighting - Klap code in 
  1. package sudokusolver;
  2.  
  3. import java.util.ArrayList;
  4.  
  5. /**
  6.  * The idea of this sudokusolver is simple.
  7.  * It loops trough every zero in the puzzle and
  8.  * tries flll in every number from 1 to 9.
  9.  * There can only be one possibility - if two ore more
  10.  * numbers are possible, it just skips that value and
  11.  * jumps to the next zero. When the first loop is complete,
  12.  * at least one number should be filled in. If that isn't
  13.  * the case, it is not solvable.
  14.  * The solver will then keep looping trough the puzzle until
  15.  * all answers are found. If it loops once trough the puzzle
  16.  * without filling in at least one number, it's also unsolvable.
  17.  *
  18.  * @author Maarten Ureel
  19.  * @version 1.0
  20.  */
  21. public class SimpleSudokuSolver {
  22.  
  23.     public static int[][] solve(int[][] sudoku) throws UnsolvableSudokuException {
  24.         boolean solvedSomething = false;
  25.  
  26.         // As long as there is a zero present, keep trying
  27.         while (!solved(sudoku)) {
  28.             for (int row = 0; row < sudoku.length; row++) {
  29.                 // Loop trough all rows
  30.                 for (int col = 0; col < sudoku[row].length; col++) {
  31.                     // Loop trough the columns in the row
  32.                     if (sudoku[row][col] == 0) {
  33.                         ArrayList<Integer> possibilities = new ArrayList<Integer>();
  34.  
  35.                         // Loop trough all possibilitis, eliminate those
  36.                         // that aren't possible
  37.                         for (int i = 1; i <= 9; i++) {
  38.                             // Check 1: see if the number is already in this row
  39.                             if (!getRow(sudoku, row).contains(i) &&
  40.                                     !getColumn(sudoku, col).contains(i) &&
  41.                                     !getSquare(sudoku, row, col).contains(i)) {
  42.                                 possibilities.add(i);
  43.                             }
  44.                         }
  45.  
  46.                         if (possibilities.size() == 1) {
  47.                             // There is only one possibility - so it's a good one :)
  48.                             sudoku[row][col] = possibilities.get(0);
  49.                             solvedSomething = true;
  50.                         }
  51.                     }
  52.                 }
  53.             }
  54.  
  55.             if(!solvedSomething) {
  56.                 throw new UnsolvableSudokuException();
  57.             }
  58.             solvedSomething = false;
  59.         }
  60.  
  61.         return sudoku;
  62.     }
  63.  
  64.     public static void print(int[][] sudoku) {
  65.         for (int row = 0; row < sudoku.length; row++) {
  66.             // Divide in blocks
  67.             if (row % 3 == 0 && row != 0) {
  68.                 System.out.println();
  69.             }
  70.  
  71.             for (int col = 0; col < sudoku[row].length; col++) {
  72.                 // Divide in blocks
  73.                 if (col % 3 == 0 && col != 0) {
  74.                     System.out.print(" ");
  75.                 }
  76.  
  77.                 System.out.print(sudoku[col][row] + " ");
  78.             }
  79.             System.out.println();
  80.         }
  81.     }
  82.  
  83.     private static boolean solved(int[][] sudoku) {
  84.         for (int row = 0; row < sudoku.length; row++) {
  85.             // Loop trough all rows
  86.             for (int col = 0; col < sudoku[row].length; col++) {
  87.                 // Loop trough the columns in the row
  88.                 if (sudoku[row][col] == 0) {
  89.                     // Not yet solved - stop finding out
  90.                     return false;
  91.                 }
  92.             }
  93.         }
  94.  
  95.         // There was no false returned (zero present), so it's solved!
  96.         return true;
  97.     }
  98.  
  99.     private static ArrayList<Integer> getRow(int[][] sudoku, int rowNumber) {
  100.         ArrayList<Integer> row = new ArrayList<Integer>();
  101.         for (int i = 0; i < sudoku[rowNumber].length; i++) {
  102.             row.add(sudoku[rowNumber][i]);
  103.         }
  104.         return row;
  105.     }
  106.  
  107.     private static ArrayList<Integer> getColumn(int[][] sudoku, int columnNumber) {
  108.         ArrayList<Integer> col = new ArrayList<Integer>();
  109.  
  110.         // Loop trough all rows and add the number in the given column
  111.         for (int row = 0; row < sudoku.length; row++) {
  112.             col.add(sudoku[row][columnNumber]);
  113.         }
  114.  
  115.         return col;
  116.     }
  117.  
  118.     private static ArrayList<Integer> getSquare(int[][] sudoku, int rowNumber, int columnNumber) {
  119.         ArrayList<Integer> square = new ArrayList<Integer>();
  120.  
  121.         // Define the upperleft corner of the square
  122.         rowNumber = (int) Math.floor(rowNumber / 3) * 3;
  123.         columnNumber = (int) Math.floor(columnNumber / 3) * 3;
  124.         int rowMax = rowNumber + 3;
  125.         int colMax = columnNumber + 3;
  126.  
  127.  
  128.         // Fill
  129.         for (int row = rowNumber; row < rowMax; row++) {
  130.             for (int col = columnNumber; col < colMax; col++) {
  131.                 square.add(sudoku[row][col]);
  132.             }
  133.         }
  134.  
  135.         return square;
  136.     }
  137. }


UnsolvableSudokuException.java
java code - Bekijk de code zonder highlighting - Klap code in 
  1. package sudokusolver;
  2.  
  3. /**
  4.  *
  5.  * @author Maarten Ureel
  6.  */
  7. class UnsolvableSudokuException extends Exception {
  8.  
  9.     public UnsolvableSudokuException() {
  10.         super("The given sudoku is not solvable by this solver...");
  11.     }
  12.  
  13. }


Main.java
java code - Bekijk de code zonder highlighting - Klap code in 
  1. package sudokusolver;
  2.  
  3. /**
  4.  *
  5.  * @author Maarten Ureel
  6.  */
  7. public class Main {
  8.  
  9.     public static void main(String[] args) {
  10.         int row1[] = {0, 0, 0,  0, 0, 0,  0, 0, 0};
  11.         int row2[] = {3, 6, 7,  8, 0, 1,  0, 2, 0};
  12.         int row3[] = {9, 0, 2,  0, 0, 5,  3, 0, 1};
  13.  
  14.         int row4[] = {5, 0, 0,  0, 9, 0,  0, 0, 8};
  15.         int row5[] = {0, 0, 0,  7, 0, 4,  0, 0, 0};
  16.         int row6[] = {4, 0, 0,  0, 5, 0,  0, 0, 2};
  17.  
  18.         int row7[] = {0, 0, 5,  1, 0, 0,  9, 0, 4};
  19.         int row8[] = {0, 9, 0,  4, 0, 2,  7, 1, 5};
  20.         int row9[] = {0, 0, 0,  0, 0, 0,  0, 0, 0};
  21.  
  22.         int[] sudoku[] = {row1, row2, row3, row4, row5, row6, row7, row8, row9};
  23.  
  24.         System.out.println("Before: ");
  25.         SimpleSudokuSolver.print(sudoku);
  26.         sudoku = SimpleSudokuSolver.solve(sudoku);
  27.         System.out.println("After: ");
  28.         SimpleSudokuSolver.print(sudoku);
  29.     }
  30.  
  31. }
Download code! Download code (.txt)

 Stemmen
Niet ingelogd.

 Reacties
Post een reactie
Geen reacties (0)
© 2002-2024 Sitemasters.be - Regels - Laadtijd: 0.066s