Joined: 01 Jan 2001
Posts: 3232
Location: Reading, UK
Posted: Mon Aug 08, 2005 1:46 pm
Post subject: Sudoku Solver
At lunch today people were chatting about Sudoku puzzles. I was struck by how simple they would be (at least from an application development point of view) to solve with an Evolutionary Algorithm - especially using my snazzy little framework...
Basically you'd need a population of individuals, each of which is made up of a 9x9 grid of digits. There must be nine each of the digits 0 to 9 (so nine ones, nine twos etc). Some of these digits are given to us by the puzzle designer and must be "fixed", the others must be arranged in such a way that no single digit is repeated in any column, row or in any of the nine 3x3 "sub-boxes".
Some fitness function must be used to see how good each solution is - for example by giving a count of the number of repeated digits in the solution. The EA kills off the worst solutions and breeds replacements from the remaining population.
Breeding new solutions is done using crossover of the two parents genetic material and mutation of the child. Crossover is dead easy; we simply take chunks of each parent's solution to make the child (so the child could be made of the top half of Mum and the bottom half of Dad). To do mutation we just randomly swap two digits in the child solution (so we might take the digit from square [2,4] and swap it with square [7,8]).
Not hard in the slightest - but how well would it do? Perhaps I shall code it and see
Joined: 01 Jan 2001
Posts: 3232
Location: Reading, UK
Posted: Mon Aug 08, 2005 11:05 pm
Post subject:
Well, a very simple Sudoku Solver is now complete...
In the picture above, the grey squares are the fixed digits of the original puzzle, while the white squares are the squares that can be changed - either by the user or the genetic algorithm. Red numbers are numbers which clash in some way.
I have to say that I've never come across an EA Application more prone to local minima than this one. It's easy to get the first few numbers in, but after that, the probability of swapping the correct numbers is so low that solution speed really drops off. This is made worse by over fitting to not-quite-perfect solutions which mean that, in order to get to the optimum solution, we have to go via a series of solutions which are far less good that the current one (In English: we have to shake it up and start again!).
So, though it's been very easy to get this far, I'm not so sure that an Evolutionary Algorithm is the best tool for solving a "pure logic" puzzle like this one.
The first of these stupid puzzles that I came across stated that it required 2 hours to solve, so I spent 2 hours implementing a depth-first search solver. I haven't bothered to put a graphical interface on it, but I can let you have the code if you are interested. It implements the optimisation that it guesses squares in the most complete constraint-group first (line, column or square). This reduces the branching factor of the search tree. I can't think of any particularly good heuristics, although there probably are some.
I find it hard to understand why people like doing these puzzles manually. Most people probably do an approximately depth-first search, so once they have figured out the algorithm, the only thing they are fighting against it their own capacity to make errors.
P.S. Jo and I had a nice holiday on the canal boat, thank you, and will be coming to your bar-be-que.
On the subject of generating puzzles, I think you can do this with DFS too. You just start searching for solutions on an empty grid. Or you could seed the grid with a few starting numbers. At some level of the search tree you say, 'OK, those are my starting numbers' you then keep searching to verify that there is a unique solution (not sure if this is always feasible, as you have to search the complete space, although given the size of the puzzle and the constraints of the starting numbers this will not always be huge).
The difficulty of the puzzle is some function of the branching factor in the first few layers of search below the starting numbers, because this factor indicates how many 'mis-steps' it is possible to make early on.
Does the "Sudoku Solver" just solve the Sudoku puzzles you're stuck on or can it be used as a computer version to generate new puzzles for me to complete?
At the moment it only solves puzzles, but what I'm saying is that it could possibly be adapted to create them. Possibly. By someone who could be bothered. And that may not be me.
/*
* Created on 22-Apr-2005
*/
package com.skenepages.sudoku;
import java.io.PrintStream;
/**
* @author James
*/
public class Sudoku {
private static class Board {
private int [][] board; // rows x columns
public Board() {
board = new int[9][9];
}
public Board(int [][] board) {
if(board == null || board.length != 9)
throw new IllegalArgumentException("Board must be 9 x 9");
for(int y = 0; y < 9; y++)
if(board[y] == null || board[y].length != 9)
throw new IllegalArgumentException("Board must be 9 x 9");
this.board = board;
}
int count = 0;
boolean [] found = new boolean[9];
for(int x = 0; x < 9; x++)
if(board[y][x] > 0) {
found[board[y][x] - 1] = true;
count++;
}
int [] res = new int[9 - count];
int p = 0;
for(int x = 0; x < 9; x++)
if(!found[x]) res[p++] = x + 1;
return res;
}
public int [] getColumnFreedoms(int x) {
int count = 0;
boolean [] found = new boolean[9];
for(int y = 0; y < 9; y++)
if(board[y][x] > 0) {
found[board[y][x] - 1] = true;
count++;
}
int [] res = new int[9 - count];
int p = 0;
for(int y = 0; y < 9; y++)
if(!found[y]) res[p++] = y + 1;
return res;
}
public int [] getBlockFreedoms(int bx, int by) {
int count = 0;
boolean [] found = new boolean[9];
for(int y = 0; y < 3; y++)
for(int x = 0; x < 3; x++)
if(board[y + by * 3][x + bx * 3] > 0) {
found[board[y + by * 3][x + bx * 3] - 1] = true;
count++;
}
int [] res = new int[9 - count];
int p = 0;
for(int x = 0; x < 9; x++)
if(!found[x]) res[p++] = x + 1;
return res;
}
}
/**
*
* @param board
* @return true if solved, false otherwise.
*/
public static boolean solve(Board board) {
// Find the row, column or block with the least freedoms (but still
// some work to do)
int [][] freedoms = new int[27][];
for(int y = 0; y < 9; y++) freedoms[y] = board.getRowFreedoms(y);
for(int x = 0; x < 9; x++) freedoms[9 + x] = board.getColumnFreedoms(x);
for(int by = 0; by < 3; by++)
for(int bx = 0; bx < 3; bx++)
freedoms[18 + (by * 3) + bx] =
board.getBlockFreedoms(bx, by);
int count = 9;
int best = 0;
boolean solved = true;
for(int n = 1; n < 27; n++)
if(freedoms[n].length > 0) {
solved = false;
if(freedoms[n].length < count) {
best = n;
count = freedoms[n].length;
}
}
if(solved) return true;
// For the first free position in the row column or block, assign the
// first freedom that is acceptable to all intersecting rows, columns
// and blocks. If no freedom is acceptable, return.
if(best < 9) { // It's a row!
int [] choices = freedoms[best];
int y = best;
for(int x = 0; x < 9; x++) {
if(board.get(x, y) == 0) {
for(int c = 0; c < choices.length; c++) {
// Check that choice is acceptable to both column and
// block
int [] column = freedoms[9 + x];
boolean found = false;
for(int p = 0; p < column.length && !found; p++)
found |= column[p] == choices[c];
if(found) {
found = false;
int bx = x / 3;
int by = y / 3;
int [] block = freedoms[18 + by * 3 + bx];
for(int p = 0; p < block.length && !found; p++)
found |= block[p] == choices[c];
if(found) {
int [] choices = freedoms[best];
int x = best - 9;
for(int y = 0; y < 9; y++) {
if(board.get(x, y) == 0) {
for(int c = 0; c < choices.length; c++) {
// Check that choice is acceptable to both row and
// block
int [] row = freedoms[y];
boolean found = false;
for(int p = 0; p < row.length && !found; p++)
found |= row[p] == choices[c];
if(found) {
found = false;
int bx = x / 3;
int by = y / 3;
int [] block = freedoms[18 + by * 3 + bx];
for(int p = 0; p < block.length && !found; p++)
found |= block[p] == choices[c];
if(found) {
int [] choices = freedoms[best];
best = best - 18;
int by = best / 3;
int bx = best % 3;
for(int y = 0; y < 3; y++) {
for(int x = 0; x < 3; x++) {
if(board.get(bx * 3 + x, by * 3 + y) == 0) {
for(int c = 0; c < choices.length; c++) {
// Check that choice is acceptable to both row and
// column
int [] row = freedoms[by * 3 + y];
boolean found = false;
for(int p = 0; p < row.length && !found; p++)
found |= row[p] == choices[c];
if(found) {
found = false;
int [] column = freedoms[9 + bx * 3 + x];
for(int p = 0; p < column.length && !found; p++)
found |= column[p] == choices[c];
if(found) {
board.set(bx * 3 + x, by * 3 + y, choices[c]);
/*try {
Joined: 01 Jan 2001
Posts: 3232
Location: Reading, UK
Posted: Tue Aug 09, 2005 9:47 am
Post subject:
Posts deleted. Dunno what happened there...
These traditional logic approaches are obviously the best for these sorts of puzzles. In fact this is one of the only puzzles I've come across where the algorithm used by people is almost identical to the one used by programmers (who may or may not be people ). Now I've proved (to myself at least) that Evolutionary Algorithms are not a great way to do Sudoku, I can use them as a test bed for algorithms to avoid local minima.
I may also shamelessly steal your code to use as a comparison
Joined: 01 Jan 2001
Posts: 3232
Location: Reading, UK
Posted: Tue Aug 09, 2005 10:26 am
Post subject:
For what it's worth, here's my code and the application itself. The GUI does make a reasonable paper replacement for playing Sudoku as it removes the need for rubbing out and gives you feedback when you're wrong!
Enter the fixed numbers on the "Problem" tab and then play around with your solution on the "Solution" tab. Errors are shown in red. Click the "Solve" button to start the Evolutionary Algorithm and watch it almost find the solution
Here's the code - it's not as portable as Skene's, since you need Delphi and upmteen different libraries (all free).
Please do steal my code, and add it to your GUI. I'd like to see a graphical view of it working, but can't be bothered to do it myself. Although if I did it in Java I could turn it into an applet. Hmm. One day maybe.
Joined: 01 Jan 2001
Posts: 3232
Location: Reading, UK
Posted: Fri Aug 19, 2005 12:05 pm
Post subject:
So very close!
Made some changes to the Evolutionary Training setup and I think I've almost cracked it. In the picture below the system is trying to solve a sudoku problem with no fixed numbers. That should be easier, because there are far more solutions available than when some cells are fixed. It's not hard to see that it's pretty damned close to having completed the puzzle...
In fact, if it were to swap the two pairs of numbers I've highlighted in the next image, then it'd have done it. The probability of it making those swaps is very low, however, so I guess I just have to wait!
To make the EA work better I took some simple steps to lower the chances of overfitting and premature convergance and also made some problem specific alterations to the fitness function.
To lower the chances of premature convergence I added an age factor into the fitness function - old networks are punished for being old, so regardless of how good they are, all networks will die. Watching the evolution process it was clear that this allowed for the concurrent existance of several distinct solutions in the population.
I also altered the fitness function to give a very large reward to solutions which had one or more "correct" rows, columns or blocks.
DT
PS: As I wrote this post, the solver solved the problem
Last edited by genious on Fri Aug 19, 2005 2:34 pm; edited 1 time in total
Joined: 01 Jan 2001
Posts: 3232
Location: Reading, UK
Posted: Fri Aug 19, 2005 2:17 pm
Post subject:
So here where the problem lies...
Over lunch I set the EA solver a simple Sudoku problem from the front page of a popular sudoku site. It's supposed to be an easy problem for "Sudoku Virgins" to solve (I wouldn't know, I consider it below me to solve them in my head ) and the EA solver has done a fairly good job...
And that's the point about EAs: They do a fairly good job. If you look at what the solver's come up with, you might think it looks pretty damned close to correct and you'd be right, because it is, but because with sudoku we want to reach the optimum solution, not just a fairly good one, there's still a lot to be done. There is no obvious set of "swaps" which would allow us to reach the solution, without first messing the board up quite a lot. In order to reach the optimum solution we need to backtrack through several solutions which are less good than the one we have at the moment - either that or wait until a new solution is created having had the exact correct values swapped in the exact correct order; something which is astronomically unlikely.
EA's don't like backtracking. There's only a small chance that an individual which is less fit than the rest of the population will live long enough to breed. If it does manage to breed then there's a similarly low chance that it's offspring will survive, because they will probably have inherited some of the less-good traits of their parent.
So, even though the changes I have made to the EA system have encouraged diversity, they only really allow for the continued existance of diverse sub-populations if the fitness of each of these subpopulations is comperable to the fitness of all other subpopulations.
The next step in making a universal evolutionary Sudoku solver is to work out how to maintain a number of diverse sub-populations and avoid wiping out potentially good solutions just because they aren't good yet.
Joined: 01 Jan 2001
Posts: 3232
Location: Reading, UK
Posted: Thu Nov 02, 2006 12:08 pm
Post subject:
Wrote a very simple depth-first search version of the Sudoku solver for the upcoming Developer's group meeting. It's not as fast as Skene's version, since it doesn't use any heuristics, it just puts symbols in squares using a recursive backtracking approach.
Download the EXE here (set up the problem on the first tab, then watch the solution being found on the second tab).
Starting in the top left, the solver attempts to insert a symbol, then recursively checks subsequent squares, backtracking as appropriate. Like I said, not as clever as Skene's version, which uses a similar algorithm, but speeds up the search by attempting to fill squares with fewer options first (like a human would).
This simple version is a nice demonstration of a standard depth first search, which is the key to my planned talk
Posted: Fri Jan 09, 2009 6:21 am
Post subject: Please....
Can you email your program to my email(phoenix_13eauty@yahoo.com)...
i need very much for my task in school about using
EA to solve the sudoku problem...
I need in Visual .NET
can you ?
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
Profile
FAQ
Calendar
Log in
Register
Calendar
