fork(1) download
copy 
  1.  
  2.  
  3. /* package whatever; // don't place package name! */
  4.  
  5. import java.util.ArrayList;
  6. import java.util.Arrays;
  7. import java.util.List;
  8.  
  9. /* Name of the class has to be "Main" only if the class is public. */
  10. class Ideone {
  11.  
  12.     /**
  13.      * A class that is able to brute-force a solution for a Sudoku-like puzzle.
  14.      * <br>
  15.      * Due to the internal use of bit-shifting the largest sudoku puzzle this can solve is 25x25
  16.      * which should be more than enough. Sudoku-like puzzles are always square-number sized. 1x1, 4x4, 9x9, 16x16, 25x25, etc.
  17.      * 
  18.      * @author rolfl
  19.      *
  20.      */
  21.     private static class RecursiveBruteSolver {
  22.  
  23.         // dimension - the width of the grid
  24.         private final int dimension;
  25.         // a simple bit-mask with 1 bit set for each possible value in each square.
  26.         // for a 4-size sudoku it will look like:
  27.         // 0b0001 0b0010 0b0100 0b1000
  28.         // for a 9-size sudoku like:
  29.         // 0b000000001 0b000000010 0b000000100 .....
  30.         private final int[] bitmask;
  31.         // if we flatten the grid, this is how big it is in 1 dimension
  32.         private final int flatsize;
  33.         // the array of flattened cell available digits
  34.         private final int[][] available;
  35.         // a complicated concept - the index into the flattened array of all
  36.         // squares that are in the same row/column/block, but also have a larger
  37.         // index in the flattened array.
  38.         private final int[][] followings;
  39.         // Some squares will have just one possible value, they do not need to be
  40.         // solved.
  41.         // this unknown array is the indices of the unsolved squares in the
  42.         // flattened array
  43.         private final int[] unknown;
  44.  
  45.         // keep track of all recursive call counts
  46.         private long statistics = 0L;
  47.  
  48.         /**
  49.          * Create a Brute-force solver that will determine all the solutions (if
  50.          * any) for a Sudoku grid (when you call the solve() method).
  51.          * 
  52.          * @param dimension
  53.          *            the side-size of the sudoku grid. The digits 2D array is
  54.          *            expected to match the same dimensions.
  55.          * @param digits
  56.          *            a 3D array containing the digits that are allowed at that
  57.          *            position in the array. The actual digits available are
  58.          *            expected to be 0-based. i.e. a regular 9-size Sudoku has the
  59.          *            digits 1-9, this solver expects them to be represented as 0-8.
  60.          */
  61.         public RecursiveBruteSolver(int dimension, int[][][] digits) {
  62.             this.dimension = dimension;
  63.  
  64.             // if we flatten the array....
  65.             this.flatsize = dimension * dimension;
  66.             available = new int[flatsize][];
  67.             followings = new int[flatsize][];
  68.  
  69.             // how many digits are there...and what will the bit-mask be for each digit.
  70.             bitmask = new int[dimension];
  71.             for (int i = 0; i < dimension; i++) {
  72.                 bitmask[i] = 1 << i;
  73.             }
  74.  
  75.             // keep track of the unknown cells.
  76.             // make a generous-size array, we will trim it later.
  77.             int[] tmpunknown = new int[flatsize];
  78.             int tmpunknowncnt = 0;
  79.  
  80.             // flatten out the grid.
  81.             for (int r = 0; r < dimension; r++) {
  82.                 for (int c = 0; c < dimension; c++) {
  83.                     int flatid = r * dimension + c;
  84.                     // gets an array of digits that can be put in each square.
  85.                     // for example, if a Sudoku square can have 3,5 or 6 this will return
  86.                     //    [2,4,5]
  87.                     available[flatid] = Arrays.copyOf(digits[r][c], digits[r][c].length);
  88.                     if (available[flatid].length > 1) {
  89.                         tmpunknown[tmpunknowncnt++] = flatid;
  90.                     }
  91.                 }
  92.             }
  93.  
  94.     //        System.out.println("There are " + tmpunknowncnt + " unknown cells");
  95.  
  96.             // Special note about `followings`
  97.             // A square in a Sudoku puzzle affects all other squares in the same row, column, and block.
  98.             // Only one square in the same row/block/column can have particular value.
  99.             // For this recursion we 'flatten' the grid, and process the grid in order.
  100.             // For each unsolved cell, we set the cell value, and then move on to the next unsolved cell
  101.             // but, we need to 'remove' our value from the possible values of other cells in the same row/column/block.
  102.             // Because of the way this solver progresses along the flattened array, we only need to remove it
  103.             // from cells that come **after** us in the flattened array (values before us already have a fixed value).
  104.             // So, buildFollowing() builds an array of indexes in the flattened array that are in the same row/column/block
  105.             // but also have a higher index in the flattened array.
  106.             for (int flat = 0; flat < available.length; flat++) {
  107.                 if (available[flat] != null) {
  108.                     followings[flat] = buildFollowing(flat / dimension, flat
  109.                             % dimension);
  110.                 }
  111.             }
  112.  
  113.             // create the final copy of the unknown cells (cells which need to be solved).
  114.             unknown = Arrays.copyOf(tmpunknown, tmpunknowncnt);
  115.         }
  116.  
  117.         public int[][][] solve() {
  118.  
  119.             // following points to unknown subsequent values.....
  120.             final int[] combination = new int[flatsize];
  121.             // where to store the possible solutions we find
  122.             final List<int[][]> solutions = new ArrayList<>();
  123.  
  124.             // this freedoms is an integer for each value.
  125.             // bits in the integer are set for each of the values the
  126.             // position can be. This is essentially a record of the state
  127.             // inside the recursive routine. For example, if setting some other
  128.             // cell in the same row/column/block to 5, and our 5-bit is set,
  129.             // then we will unset it here because we no longer have the freedom
  130.             // to be 5.
  131.             final int[] freedoms = new int[flatsize]; //Arrays.copyOf(resetmask, resetmask.length);
  132.             for (int flatid = 0; flatid < flatsize; flatid++) {
  133.                 for (int b : available[flatid]) {
  134.                     // set the degrees-of-freedom mask of this...
  135.                     // what values can this cell take?
  136.                     freedoms[flatid] |= bitmask[b];
  137.                 }
  138.             }
  139.  
  140.             // Do the actual recursion.
  141.             // combination contains pointers to which actual values are being used.
  142.             // freedom contans the possible states for all subsequent cells.
  143.             recurse(solutions, 0, combination, freedoms);
  144.  
  145.             System.out.println("There were " + statistics + " recursive calls...");
  146.  
  147.             // convert the list of Solutions back to an array
  148.             return solutions.toArray(new int[solutions.size()][][]);
  149.         }
  150.  
  151.         /**
  152.          * Recursively solve the Sudoku puzzle.
  153.          * @param solutions where to store any found solutions.
  154.          * @param index The index in the 'unknown' array that points to the flat-based cell we need to solve.
  155.          * @param combination What the current combination of cell values is.
  156.          * @param freedoms The state of what potential values all cells can have.
  157.          */
  158.         private void recurse(final List<int[][]> solutions, final int index,
  159.                 final int[] combination, final int[] freedoms) {
  160.             statistics++;
  161.             if (index >= unknown.length) {
  162.                 // solution!
  163.                 solutions.add(buildSolution(combination));
  164.                 return;
  165.             }
  166.  
  167.             // The basic algorithm here is: for our unsolved square, we set it to each of it's possible values in turn.
  168.             // then, for each of the values we can be:
  169.             // 1. we also find all 'related' squares, and remove our value
  170.             //      from the degrees-of-freedom for the related squares
  171.             //      (If I am 'x' then they cannot be). See special not about 'followings'
  172.             // 3. we keep track of which other squares we actually change the freedoms for.
  173.             // 4. we recurse to the next unsolved square.
  174.             // 5. when the recursion returns, we restore the freedoms we previously 'revoked'
  175.             // 6. we move on to the next value we can be (back to 1).
  176.             // 7. when we have run out of possible values, we return.
  177.             final int flat = unknown[index];
  178.             for (int a = available[flat].length - 1; a >= 0; a--) {
  179.                 final int attempt = available[flat][a];
  180.                 if ((freedoms[flat] & bitmask[attempt]) == 0) {
  181.                     // this option excluded by previous restrictions....
  182.                     // the original unsolved puzzle says we can be 'attempt', but
  183.                     // higher levels of recursion have removed 'attempt' from our
  184.                     // degrees-of-freedom.
  185.                     continue;
  186.                 }
  187.                 // ok, is used to track whether we are still creating a valid Sudoku.
  188.                 boolean ok = true;
  189.                 // progress is used to forward, and then backtrack which following cells
  190.                 // have been impacted.
  191.                 // start at -1 because we pre-increment the progress.
  192.                 int progress = -1;
  193.                 // act has 1 bit representing each follower we act on.
  194.                 long act = 0;
  195.                 while (++progress < followings[flat].length) {
  196.                     if (freedoms[followings[flat][progress]] == bitmask[attempt]) {
  197.                         // we intend to remove the attempt from this follower's freedom's
  198.                         // but that will leave it with nothing, so this is not possible to do.
  199.                         // ok is false, so we will start a back-up
  200.                         ok = false;
  201.                         break;
  202.                     }
  203.                     // we **can** remove the value from this follower's freedoms.
  204.                     // indicate that this follower is being 'touched'.
  205.                     // act will have 1 bit available for each follower we touch.
  206.                     act <<= 1;
  207.                     // record the pre-state of the follower's freedoms.
  208.                     final int pre = freedoms[followings[flat][progress]];
  209.                     // if the follower's freedoms contained the value we are revoking, then set the bit.
  210.                     act |= (freedoms[followings[flat][progress]] &= ~bitmask[attempt]) == pre ? 0 : 1;
  211.                 }
  212.                 if (ok) {
  213.                     // we have removed our digit from all followers, and the puzzle is still valid.
  214.                     // indicate our combination digit....
  215.                     combination[flat] = a;
  216.                     // find the next unsolved.
  217.                     recurse(solutions, index + 1, combination, freedoms);
  218.                 }
  219.                 while (--progress >= 0) {
  220.                     // restore all previously revoked freedoms.
  221.                     if ((act & 0x1) == 1) {
  222.                         freedoms[followings[flat][progress]] |= bitmask[attempt]; // & resetmask[flat]);
  223.                     }
  224.                     act >>= 1;
  225.                 }
  226.             }
  227.  
  228.         }
  229.  
  230.         /**
  231.          * buildFollowing creates an array of references to other cells in the same
  232.          * row/column/block that also have an index **after** us in the flattened array system. 
  233.          *
  234.          * @param row our row index
  235.          * @param col our column index
  236.          * @return an array of flattened indices that are in the same row/column/block as us.
  237.          */
  238.         private int[] buildFollowing(int row, int col) {
  239.             int[] folls = new int[dimension * 3]; // possible rows/columns/blocks - 3 sets of values.
  240.             final int innerbound = (int)Math.sqrt(dimension); // 3 for size 9, 2 for size 4, 4 for size 16, etc.
  241.             // cnt is used to count the valid following indices.
  242.             int cnt = 0;
  243.             // column-bound - last column in the same block as us.
  244.             int cb = ((1 + col / innerbound) * innerbound);
  245.             // row-bound - last row in the same block as us.
  246.             int rb = ((1 + row / innerbound) * innerbound);
  247.             // get all (unsolved) indices that follow us in the same row
  248.             for (int c = col + 1; c < dimension; c++) {
  249.                 // rest of row.
  250.                 if (available[row * dimension + c].length > 1) {
  251.                     // only need to worry about unsolved followers.
  252.                     folls[cnt++] = row * dimension + c;
  253.                 }
  254.             }
  255.             // get all (unsolved) indices that follow us in the same column
  256.             for (int r = row + 1; r < dimension; r++) {
  257.                 if (available[r * dimension + col].length > 1) {
  258.                     // only need to worry about unsolved followers.
  259.                     folls[cnt++] = r * dimension + col;
  260.                 }
  261.                 if (r < rb) {
  262.                     // if we have not 'escaped' our block, we also find other cells in
  263.                     // the same block, but not our row/column.
  264.                     for (int c = col + 1; c < cb; c++) {
  265.                         if (available[r * dimension + c].length > 1) {
  266.                             // only need to worry about unsolved followers.
  267.                             folls[cnt++] = r * dimension + c;
  268.                         }
  269.                     }
  270.                 }
  271.             }
  272.             // return just the values that were needed as followers.
  273.             return Arrays.copyOf(folls, cnt);
  274.         }
  275.  
  276.         /**
  277.          * Convert the valid combination of values back to a simple int[] grid.
  278.          * @param combination the combination of unsolved values that is a valid puzzle.
  279.          * @return A Solution object representing the solution.
  280.          */
  281.         private int[][] buildSolution(int[] combination) {
  282.             int[][] grid = new int[dimension][dimension];
  283.             for (int f = 0; f < combination.length; f++) {
  284.                 grid[f / dimension][f % dimension] = available[f][combination[f]];
  285.             }
  286.             // double-check the validity of this solution (all sudoku basic rules are followed.
  287.             // throws exception if not.
  288.     //        SudokuRules.isValid(grid);
  289.             // mechanism for printing out a grid.
  290.     //        System.out.println("BruteForceRecursive found Solution:\n"
  291.     //                + GridToText.displayAsString(grid));
  292.             return grid;
  293.         }
  294.  
  295.     }
  296.  
  297.     public static void main(String[] args) {
  298.         int[][][] puzzle = new int[][][] {
  299.                 { { 1, 4, 5, },{ 2, 5, 6, },{ 1, 2, 4, 5, 6, },{ 7, },{ 3, },{ 2, 4, 5, 6, },{ 0, 1, 6, },{ 0, 1, 6, },{ 8, },  },
  300.                 { { 1, 3, 5, },{ 2, 3, 5, 6, 8, },{ 0, },{ 2, 5, 6, },{ 2, 5, 6, 8, },{ 2, 5, 6, 8, },{ 1, 6, 7, },{ 1, 6, 7, },{ 4, },  },
  301.                 { { 7, },{ 6, 8, },{ 4, 6, 8, },{ 4, 6, },{ 1, },{ 0, },{ 3, },{ 5, },{ 2, },  },
  302.                 { { 6, },{ 0, 2, 3, 5, },{ 7, },{ 0, 1, 2, 3, 4, 5, },{ 2, 4, 5, },{ 1, 2, 4, 5, },{ 1, 5, },{ 8, },{ 1, 3, 5, },  },
  303.                 { { 0, 1, 3, 5, },{ 0, 2, 3, 5, 8, },{ 1, 2, 5, 8, },{ 0, 1, 2, 3, 4, 5, 6, },{ 2, 4, 5, 6, 8, },{ 1, 2, 4, 5, 6, 7, 8, },{ 1, 5, 6, 7, },{ 1, 3, 4, 6, 7, },{ 1, 3, 5, 7, },  },
  304.                 { { 1, 3, 5, },{ 4, },{ 1, 5, 8, },{ 1, 3, 5, 6, },{ 5, 6, 8, },{ 1, 5, 6, 7, 8, },{ 2, },{ 1, 3, 6, 7, },{ 0, },  },
  305.                 { { 4, 5, },{ 1, },{ 3, },{ 8, },{ 0, },{ 2, 4, 5, },{ 5, 7, },{ 2, 7, },{ 6, },  },
  306.                 { { 8, },{ 0, 5, 6, 7, },{ 5, 6, },{ 1, 2, 5, 6, },{ 2, 5, 6, },{ 1, 2, 5, 6, },{ 4, },{ 0, 1, 2, 3, 7, },{ 1, 3, 5, 7, },  },
  307.                 { { 2, },{ 0, 5, 6, },{ 4, 5, 6, },{ 1, 4, 5, 6, },{ 7, },{ 3, },{ 0, 1, 5, 8, },{ 0, 1, },{ 1, 5, },  },
  308.         };
  309.  
  310.         RecursiveBruteSolver solver = new RecursiveBruteSolver(9, puzzle);
  311.         for (int[][] sol : solver.solve()) {
  312.             System.out.println("Solution:");
  313.             System.out.println(displayAsString(sol));
  314.         }
  315.     }
  316.  
  317.     private static final char[][] symbols = {
  318.         "╔═╤╦╗".toCharArray(),
  319.         "║ │║║".toCharArray(),
  320.         "╟─┼╫╢".toCharArray(),
  321.         "╠═╪╬╣".toCharArray(),
  322.         "╚═╧╩╝".toCharArray(),
  323.     };
  324.  
  325.     private static final char[] DIGITCHARS = "123456789ABCFEDGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".toCharArray();
  326.  
  327.     public static final char getSudokuDigit(final int value) {
  328.         if (value < 0) {
  329.             return ' ';
  330.         }
  331.         return DIGITCHARS[value];
  332.     }
  333.  
  334.     public static final String displayAsString(int[][]data) {
  335.         return buildStringForGrid(data.length, (int)Math.sqrt(data.length), data);
  336.     }
  337.  
  338.     private static final String buildStringForGrid(final int dimension, final int blocksize, final int[][]rows) {
  339.         final StringBuilder sb = new StringBuilder();
  340.         for (int r = 0; r < dimension; r++) {
  341.             if (r == 0) {
  342.                 sb.append(printSymbolLine(dimension, blocksize, null, symbols[0]));
  343.             } else if (r % blocksize == 0) {
  344.                 sb.append(printSymbolLine(dimension, blocksize, null, symbols[3]));
  345.             } else {
  346.                 sb.append(printSymbolLine(dimension, blocksize, null, symbols[2]));
  347.             }
  348.             sb.append(printSymbolLine(dimension, blocksize, rows[r], symbols[1]));
  349.         }
  350.         sb.append(printSymbolLine(dimension, blocksize, null, symbols[4]));
  351.         return sb.toString();
  352.     }
  353.  
  354.     private static String printSymbolLine(int dimension, int blocksize, int[] values, char[] symbols) {
  355.         StringBuilder sb = new StringBuilder();
  356.         sb.append(symbols[0]);
  357.         int vc = 0;
  358.         for (int b = 0; b < blocksize; b++) {
  359.             for (int c = 0; c < blocksize; c++) {
  360.                 if (values == null) {
  361.                     sb.append(symbols[1]).append(symbols[1]).append(symbols[1]).append(symbols[2]);
  362.                 } else {
  363.                     final int val = values[vc++];
  364.                     char ch = getSudokuDigit(val);
  365.                     sb.append(symbols[1]).append(ch).append(symbols[1]).append(symbols[2]);
  366.                 }
  367.             }
  368.             sb.setCharAt(sb.length() - 1, symbols[3]);
  369.         }
  370.         sb.setCharAt(sb.length() - 1, symbols[4]);
  371.         sb.append("\n");
  372.         return sb.toString();
  373.     }
  374. }
  375.  
Success #stdin #stdout 0.08s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
There were 55625 recursive calls...
Solution:
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
║ 6 │ 3 │ 2 ║ 8 │ 4 │ 5 ║ 1 │ 7 │ 9 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 4 │ 7 │ 1 ║ 3 │ 6 │ 9 ║ 2 │ 8 │ 5 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 8 │ 9 │ 5 ║ 7 │ 2 │ 1 ║ 4 │ 6 │ 3 ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║ 7 │ 4 │ 8 ║ 1 │ 5 │ 3 ║ 6 │ 9 │ 2 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 1 │ 6 │ 3 ║ 4 │ 9 │ 2 ║ 7 │ 5 │ 8 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 2 │ 5 │ 9 ║ 6 │ 7 │ 8 ║ 3 │ 4 │ 1 ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║ 5 │ 2 │ 4 ║ 9 │ 1 │ 6 ║ 8 │ 3 │ 7 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 9 │ 8 │ 6 ║ 2 │ 3 │ 7 ║ 5 │ 1 │ 4 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 3 │ 1 │ 7 ║ 5 │ 8 │ 4 ║ 9 │ 2 │ 6 ║
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
https://ideone.com/GUSwn2
http://c...content-available-to-author-only...e.com/questions/37425/sudoku-week-end-challenge-brute-force-recursive-solver
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!