Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (777) Games in Android Showcase (231) games submitted by our members Games in WIP (856) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Sudoku solver  (Read 8402 times) 0 Members and 1 Guest are viewing this topic.
ricardo

Senior Devvie

Medals: 2
Projects: 3

 « Posted 2014-03-14 01:34:19 »

I know... Another contest?? Well, not exactly. This is not a *real* contest.
I am researching about Sudoku algorithms to generate and solve 9x9 boards.
This is not so easy as it seems. Some "hard" Sudokus can take more than 180 seconds to be solved by a computer!

So, my idea: Lets see who can create the best algorithm to solve 1000 (example) Sudokus more efficiently.
Sudoku format: 4.....5.8.3..........7......2.....6.....5.8......1.......6.3.7.5..2.....1.8......
Rules:
-Track how much time it takes in milliseconds to solve all the Sudokus (better in different computers).
-Track how many loops, tries and errors were needed to solve them.

Good or bad idea? I will need to make one anyways for my next game. Would be fun some competition.
BurntPizza

« JGO Bitwise Duke »

Medals: 486
Exp: 7 years

 « Reply #1 - Posted 2014-03-14 01:42:28 »

Did this on Hackerrank a while ago, used a nifty little recursive depth-first search as it is a code-length challenge. I had to remove some heuristics for the challenge, but it still ran real fast. I'm curious to see what people do.

This is roughly the algorithm I started from: http://www.sysexpand.com/?path=exercises/sudoku-solver

Will post code after I make it comprehensible. (if that's possible :\ )
Riven

« JGO Overlord »

Medals: 1357
Projects: 4
Exp: 16 years

 « Reply #2 - Posted 2014-03-14 17:01:16 »

I wrote a solver which calculates tough sudoku's in about 1/3rd of a second. It doesn't have any techniques or fancy strategies: for solving 1 puzzle it's fast enough. It just fills in the next empty cell, unless it can't, then it tries to increase the value of the previous cell, unless it can't, etc etc. Worst case would be that it arrives at the last cells and has to backtrack all the way back to the first cells, repeatedly.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113 `import java.util.Arrays;public class Sudoku{   public static void main(String[] args)   {      int[] grid = {//            0, 0, 3, 6, 0, 0, 8, 0, 0,//            0, 0, 9, 0, 0, 0, 0, 0, 3,//            0, 7, 0, 0, 0, 0, 0, 2, 0,//            0, 0, 1, 0, 0, 0, 7, 0, 4,//            0, 0, 7, 0, 0, 2, 0, 0, 0,//            9, 5, 0, 0, 0, 0, 0, 6, 0,//            0, 0, 0, 0, 0, 1, 2, 0, 0,//            8, 0, 0, 3, 0, 0, 6, 0, 0,//            0, 0, 0, 7, 4, 0, 9, 0, 0 };      print(grid);      int[] work = grid.clone();      if(solve(work, 0))         print(work);      for(int i = 0; i < 4; i++)      {         long t1 = System.currentTimeMillis();         solve(grid.clone(), 0);         long t2 = System.currentTimeMillis();         System.out.println("solving took: " + (t2 - t1) + "ms");      }   }   public static void print(int[] grid)   {      for(int i = 0; i < 81; i += 9)         System.out.println(Arrays.toString(Arrays.copyOfRange(grid, i, i + 9)));      System.out.println();   }   public static boolean solve(int[] grid, int cell)   {      while (cell < 81 && grid[cell] > 0)         cell++;      if(cell == 81)         return true;      for(int i = 1; i <= 9; i++)      {         grid[cell] = i;+         if(isColumnValid(grid, cell % 9))+            if(isRowValid(grid, cell / 9))+               if(isBlockValid(grid, cell % 3 * 3, cell / 9 % 3 * 3))                  if(isValid(grid) && solve(grid, cell + 1))                     return true;      }      grid[cell] = 0;      return false;   }   private static final int[] freqs = new int[10];   public static boolean isValid(int[] grid)   {      for(int i = 0; i < 9; i++)      {         if(!isRowValid(grid, i))            return false;         if(!isColumnValid(grid, i))            return false;         if(!isBlockValid(grid, i % 3 * 3, i / 3 * 3))            return false;      }      return true;   }   public static boolean isRowValid(int[] grid, int row)   {      Arrays.fill(freqs, 0);      for(int i = 0; i < 9; i++)      {         int cell = grid[row * 9 + i];         if(cell > 0 && ++freqs[cell] > 1)            return false;      }      return true;   }   public static boolean isColumnValid(int[] grid, int col)   {      Arrays.fill(freqs, 0);      for(int i = 0; i < 9; i++)      {         int cell = grid[i * 9 + col];         if(cell > 0 && ++freqs[cell] > 1)            return false;      }      return true;   }   public static boolean isBlockValid(int[] grid, int x, int y)   {      Arrays.fill(freqs, 0);      for(int i = 0; i < 9; i++)      {         int cell = grid[(y + i / 3) * 9 + (x + i % 3)];         if(cell > 0 && ++freqs[cell] > 1)            return false;      }      return true;   }}`

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 `[0, 0, 3, 6, 0, 0, 8, 0, 0][0, 0, 9, 0, 0, 0, 0, 0, 3][0, 7, 0, 0, 0, 0, 0, 2, 0][0, 0, 1, 0, 0, 0, 7, 0, 4][0, 0, 7, 0, 0, 2, 0, 0, 0][9, 5, 0, 0, 0, 0, 0, 6, 0][0, 0, 0, 0, 0, 1, 2, 0, 0][8, 0, 0, 3, 0, 0, 6, 0, 0][0, 0, 0, 7, 4, 0, 9, 0, 0][2, 4, 3, 6, 5, 7, 8, 9, 1][6, 8, 9, 2, 1, 4, 5, 7, 3][1, 7, 5, 9, 3, 8, 4, 2, 6][3, 2, 1, 5, 6, 9, 7, 8, 4][4, 6, 7, 1, 8, 2, 3, 5, 9][9, 5, 8, 4, 7, 3, 1, 6, 2][7, 3, 6, 8, 9, 1, 2, 4, 5][8, 9, 4, 3, 2, 5, 6, 1, 7][5, 1, 2, 7, 4, 6, 9, 3, 8]-solving took: 1027ms-solving took: 1026ms-solving took: 1023ms-solving took: 1027ms+solving took: 390ms+solving took: 389ms+solving took: 387ms+solving took: 387ms`

World's hardest sudoku for mere mortals:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24 `[8, 0, 0, 0, 0, 0, 0, 0, 0][0, 0, 3, 6, 0, 0, 0, 0, 0][0, 7, 0, 0, 9, 0, 2, 0, 0][0, 5, 0, 0, 0, 7, 0, 0, 0][0, 0, 0, 0, 4, 5, 7, 0, 0][0, 0, 0, 1, 0, 0, 0, 3, 0][0, 0, 1, 0, 0, 0, 0, 6, 8][0, 0, 8, 5, 0, 0, 0, 1, 0][0, 9, 0, 0, 0, 0, 4, 0, 0][8, 1, 2, 7, 5, 3, 6, 4, 9][9, 4, 3, 6, 8, 2, 1, 7, 5][6, 7, 5, 4, 9, 1, 2, 8, 3][1, 5, 4, 2, 3, 7, 8, 9, 6][3, 6, 9, 8, 4, 5, 7, 2, 1][2, 8, 7, 1, 6, 9, 5, 3, 4][5, 2, 1, 9, 7, 4, 3, 6, 8][4, 3, 8, 5, 2, 6, 9, 1, 7][7, 9, 6, 3, 1, 8, 4, 5, 2]solving took: 75mssolving took: 76mssolving took: 76mssolving took: 75ms`

Hi, appreciate more people! Î£ â™¥ = Â¾
Learn how to award medals... and work your way up the social rankings!
ricardo

Senior Devvie

Medals: 2
Projects: 3

 « Reply #3 - Posted 2014-03-14 18:06:07 »

I still need to wrote mine. First I am trying to generate a Sudoku, but this is hard because I need a smart way to create difficulty (easy, normal, hard, hardest) and every generated boards can only have 1 final solution.
Riven

« JGO Overlord »

Medals: 1357
Projects: 4
Exp: 16 years

 « Reply #4 - Posted 2014-03-14 20:18:19 »

Having a solver is a key piece of creating a generator. You can basically fill a grid with random values (checking isValid after each insertion) and stop after you filled the grid for a certain percentage and clone it. Then you solve it, and if there is a solution, you start solving the sparse grid in randomized order (instead of sequentially) using permutations of [0,1,2,3,...]. After solving it a dozen times and getting the same answer, the chance of there being multiple solutions rapidly approaches zero.

As for how hard it is to solve... I'm not sure I have a solution for that yet.

Hi, appreciate more people! Î£ â™¥ = Â¾
Learn how to award medals... and work your way up the social rankings!
BurntPizza

« JGO Bitwise Duke »

Medals: 486
Exp: 7 years

 « Reply #5 - Posted 2014-03-14 20:45:11 »

Alright, here's mine, expanded a bit from the HR challenge, solving the same grid as Riven's:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40 `class Sudoku {   static int[] grid;      static boolean solve() {      for (int cell = 0, number, i; cell < 81; cell++)         if (grid[cell] < 1) {            check: for (number = 0; number++ < 9;) {               for (i = 0; i < 9; i++)                  if (grid[cell / 9 * 9 + i] == number | grid[cell % 9 + 9 * i] == number | grid[(cell - cell % 3) % 9 + cell / 27 * 27 + i % 3 + i / 3 * 9] == number) continue check;               grid[cell] = number;               if (solve()) return true;               grid[cell] = 0;            }            return false;         }      return true;   }      public static void main(String[] args) {      grid = new int[] {//            0, 0, 3, 6, 0, 0, 8, 0, 0,//            0, 0, 9, 0, 0, 0, 0, 0, 3,//            0, 7, 0, 0, 0, 0, 0, 2, 0,//            0, 0, 1, 0, 0, 0, 7, 0, 4,//            0, 0, 7, 0, 0, 2, 0, 0, 0,//            9, 5, 0, 0, 0, 0, 0, 6, 0,//            0, 0, 0, 0, 0, 1, 2, 0, 0,//            8, 0, 0, 3, 0, 0, 6, 0, 0,//            0, 0, 0, 7, 4, 0, 9, 0, 0 };      for (int j = 0; j < 81;)         System.out.print(grid[j++] + (j % 9 == 0 ? "\n" : " "));      System.out.println();      long time = System.nanoTime();      solve();      time = System.nanoTime() - time;      for (int j = 0; j < 81;)         System.out.print(grid[j++] + (j % 9 == 0 ? "\n" : " "));      System.out.println("Time: " + time / 1000000 + " ms");   }}`

Quote
0 0 3 6 0 0 8 0 0
0 0 9 0 0 0 0 0 3
0 7 0 0 0 0 0 2 0
0 0 1 0 0 0 7 0 4
0 0 7 0 0 2 0 0 0
9 5 0 0 0 0 0 6 0
0 0 0 0 0 1 2 0 0
8 0 0 3 0 0 6 0 0
0 0 0 7 4 0 9 0 0

2 4 3 6 5 7 8 9 1
6 8 9 2 1 4 5 7 3
1 7 5 9 3 8 4 2 6
3 2 1 5 6 9 7 8 4
4 6 7 1 8 2 3 5 9
9 5 8 4 7 3 1 6 2
7 3 6 8 9 1 2 4 5
8 9 4 3 2 5 6 1 7
5 1 2 7 4 6 9 3 8
Time: 91 ms

Same basic approach, although it lacks a heuristic that would speed it up a lot, instead of starting the recursive search on the first blank square, start on the cell with the most constraints. Still quite effective though.
ricardo

Senior Devvie

Medals: 2
Projects: 3

 « Reply #6 - Posted 2014-03-14 21:14:29 »

@Riven I need a fast sudoku generator and this is not so simple. The last digits most of the times will not fit and it needs to try over and over again. When the board is full, I need to remove some digits and check every time for all the possible combinations. If more than one combination is possible, I need to redo the last digit and start again. At least 17 default digits are needed to have a Sudoku than can be solved. To test difficulty, I need to check how "humans" can reveal the numbers. In this site they explain the rules to solve the board. For the Easy levels I could leave easy hints and for the hardest levels don't.
But this is hard to do. I guess I am over thinking again (this happens a lot with me). Maybe I will just grab some Sudoku generator and create some predefined levels for my game. Then, I just need to create one Sudoku solver algorithm to check for wrong digits.
Regenuluz
 « Reply #7 - Posted 2014-03-15 12:22:00 »

Heh, looks like this is the same same as http://projecteuler.net/problem=96 For which I never finished my own solver, because I wanted to implement all sorts of clever methods.

Maybe today is the day I get my act together and finish it.
pjt33

« JGO Spiffy Duke »

Medals: 40
Projects: 4
Exp: 7 years

 « Reply #8 - Posted 2014-03-15 12:44:02 »

As for how hard it is to solve... I'm not sure I have a solution for that yet.
My approach to that is to solve it using human-like reasoning rules (this is only value which isn't prohibited from being in this cell, this is the only cell in this group of 9 which isn't prohibited from having this value, etc), assigning a difficulty weight to each one, and then calculating the minimal total weight to solve the grid.

A better way of calculating the difficulty would be to define it inductively over the entire graph of partial solutions whose edges are defined by these reasoning rules, using something like a harmonic mean to take into account that it's easier to solve if the number of possible next steps is consistently high, but that becomes very computationally expensive.
Pages: [1]
 ignore  |  Print

 hadezbladez (274 views) 2018-11-16 13:46:03 hadezbladez (152 views) 2018-11-16 13:41:33 hadezbladez (284 views) 2018-11-16 13:35:35 hadezbladez (67 views) 2018-11-16 13:32:03 EgonOlsen (2122 views) 2018-06-10 19:43:48 EgonOlsen (2145 views) 2018-06-10 19:43:44 EgonOlsen (1358 views) 2018-06-10 19:43:20 DesertCoockie (1954 views) 2018-05-13 18:23:11 nelsongames (1597 views) 2018-04-24 18:15:36 nelsongames (2244 views) 2018-04-24 18:14:32
 Deployment and Packagingby mudlee2018-08-22 18:09:50Java Gaming Resourcesby gouessej2018-08-22 08:19:41Deployment and Packagingby gouessej2018-08-22 08:04:08Deployment and Packagingby gouessej2018-08-22 08:03:45Deployment and Packagingby philfrei2018-08-20 02:33:38Deployment and Packagingby philfrei2018-08-20 02:29:55Deployment and Packagingby philfrei2018-08-19 23:56:20Deployment and Packagingby philfrei2018-08-19 23:54:46
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org