Sudoku: src/de/uapcore/sudoku/Solver.java@ed931970b4ac

     1 /*

     2  * Copyright 2013 Mike Becker. All rights reserved.

     3  *

     4  * Redistribution and use in source and binary forms, with or without

     5  * modification, are permitted provided that the following conditions are met:

     6  *

     7  * 1. Redistributions of source code must retain the above copyright

     8  *    notice, this list of conditions and the following disclaimer.

     9  *

    10  * 2. Redistributions in binary form must reproduce the above copyright

    11  *    notice, this list of conditions and the following disclaimer in the

    12  *    documentation and/or other materials provided with the distribution.

    13  *

    14  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

    15  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

    17  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE

    18  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

    19  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

    20  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

    21  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

    22  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

    23  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

    24  * POSSIBILITY OF SUCH DAMAGE.

    25  */

    27 package de.uapcore.sudoku;

    29 /**

    30  *

    31  * @author mike

    32  */

    33 public final class Solver {

    35     public Solver() {

    36     }

    38     public boolean check(Field f) {

    39         int line[];

    40         for (int i = 0 ; i < 9 ; i++) {

    41             line = getRow(f, i);

    42             if (!valid(line)) {

    43                 return false;

    44             }

    45             line = getColumn(f, i);

    46             if (!valid(line)) {

    47                 return false;

    48             }

    49         }

    51         int square[][];

    52         for (int x = 0 ; x < 3 ; x++) {

    53             for (int y = 0 ; y < 3 ; y++) {

    54                 square = getSquare(f, x, y);

    55                 if (!valid(square)) {

    56                     return false;

    57                 }

    58             }

    59         }

    61         return true;

    62     }

    64     private boolean complete(int[][] square) {

    65         for (int x = 0 ; x < 3 ; x++) {

    66             for (int y = 0 ; y < 3 ; y++) {

    67                 if (square[x][y] == 0) {

    68                     return false;

    69                 }

    70             }

    71         }

    72         return true;

    73     }

    75     private boolean complete(int[] line) {

    76         for (int i = 0 ; i < 9 ; i++) {

    77             if (line[i] == 0) {

    78                 return false;

    79             }

    80         }

    81         return true;

    82     }

    84     private boolean valid(int[] line) {

    85         int numbers[] = new int[9];

    86         for (int i = 0 ; i < 9 ; i++) {

    87             int l = line[i]-1;

    88             if (l >= 0) {

    89                 if (++numbers[l] > 1) {

    90                     return false;

    91                 }

    92             }

    93         }

    95         return true;

    96     }

    98     private boolean valid(int[][] square) {

    99         int[] line = new int[9];

   100         for (int x = 0 ; x < 3 ; x++) {

   101             for (int y = 0 ; y < 3 ; y++) {

   102                 line[3*x+y] = square[x][y];

   103             }

   104         }

   105         return valid(line);

   106     }

   108     private int[][] getSquare(Field f, int x, int y) {

   109         if (x < 0 || x > 2 || y < 0 || y > 2) {

   110             throw new IllegalArgumentException("Invalid square coordinates");

   111         }

   112         int[][] square = new int[3][3];

   114         for (int u = 0 ; u < 3 ; u++) {

   115             for (int v = 0 ; v < 3 ; v++) {

   116                 square[u][v] = f.getCellValue(3*x+u, 3*y+v);

   117             }

   118         }

   120         return square;

   121     }

   123     private int[] getRow(Field f, int y) {

   124         if (y < 0 || y > 8) {

   125             throw new IllegalArgumentException("Invalid row number");

   126         }

   127         int row[] = new int[9];

   129         for (int x = 0 ; x < 9 ; x++) {

   130             row[x] = f.getCellValue(x, y);

   131         }

   133         return row;

   134     }

   136     private int[] getColumn(Field f, int x) {

   137         if (x < 0 || x > 8) {

   138             throw new IllegalArgumentException("Invalid column number");

   139         }

   140         int column[] = new int[9];

   142         for (int y = 0 ; y < 9 ; y++) {

   143             column[y] = f.getCellValue(x, y);

   144         }

   146         return column;

   147     }

   148 }

Mercurial > hg > Sudoku / file revision