Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (491)
Games in Android Showcase (112)
games submitted by our members
Games in WIP (556)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Sudoku solver  (Read 1202 times)
0 Members and 1 Guest are viewing this topic.
Offline ricardo

Senior Member


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!
There are some techniques, check this Wikipedia page.

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. Grin
Offline BurntPizza
« 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 :\ )
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« 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: 75ms
solving took: 76ms
solving took: 76ms
solving took: 75ms

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ricardo

Senior Member


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.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Offline BurntPizza
« 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.
Offline ricardo

Senior Member


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.
Offline Regenuluz
« Reply #7 - Posted 2014-03-15 12:22:00 »

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

Maybe today is the day I get my act together and finish it.
Offline pjt33
« 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  
 
 

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Nickropheliac (15 views)
2014-08-31 22:59:12

TehJavaDev (23 views)
2014-08-28 18:26:30

CopyableCougar4 (29 views)
2014-08-22 19:31:30

atombrot (41 views)
2014-08-19 09:29:53

Tekkerue (38 views)
2014-08-16 06:45:27

Tekkerue (35 views)
2014-08-16 06:22:17

Tekkerue (25 views)
2014-08-16 06:20:21

Tekkerue (35 views)
2014-08-16 06:12:11

Rayexar (72 views)
2014-08-11 02:49:23

BurntPizza (48 views)
2014-08-09 21:09:32
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!