|
| View previous topic :: View next topic |
| Author |
Message |
| zespri
| | Joined: 02 Dec 2007 | | Posts: 11 | | : | |
Items |
|
 Posted: Sun Dec 02, 2007 11:32 am Post subject: Brute Force Solver |
 |
|
Sorry, if this question as already answered many times, but since I was not able to find a faq or anything to this effect.
Sudoku Susser has an option of brute force Sudoko Solving. This options usually finds solution in under a second time, as opposed to "proper" heuristic solutions. This obviously less interesting to program and less useful, because it won't give a clue to a human on how to solve a puzzle.
Nevertheless, does anybody know, what algorythm lies under such a brute force implementation? I think that unoptimized excessive search wouldn't give sub-second time. So could some one please point me to a thread that already discussed a brute force solution? Thank you in advance. |
|
| Back to top |
|
 |
| wapati
| | Joined: 12 Jun 2007 | | Posts: 622 | | : | | Location: Canada |
Items |
|
|
| Back to top |
|
|
| daj95376
| | Joined: 05 Feb 2006 | | Posts: 349 | | : | |
Items |
|
| Posted: Sun Dec 02, 2007 4:49 pm Post subject: |
|
|
| gsf posted a C brute force solver in this forum a long time back. I don't have the link, but it is very fast when solving for a solution to a puzzle. If you have it search for multiple solutions, then it's slower but still very effective. |
|
| Back to top |
|
|
| garthd
| | Joined: 29 Apr 2006 | | Posts: 32 | | : | |
Items |
|
| Posted: Sun Dec 02, 2007 10:58 pm Post subject: |
|
|
This is a fast brute force algorithm for visual basic - seems to easily solve the hardest puzzles in under a second - and can be used to find the first solution or to check for multiple solutions.
http://www.setbb.com/phpbb/viewtopic.php?t=1389&mforum=sudoku |
|
| Back to top |
|
|
| zespri
| | Joined: 02 Dec 2007 | | Posts: 11 | | : | |
Items |
|
| Posted: Mon Dec 03, 2007 12:09 am Post subject: |
|
|
| daj95376 wrote: | | gsf posted a C brute force solver in this forum a long time back. I don't have the link, but it is very fast when solving for a solution to a puzzle. If you have it search for multiple solutions, then it's slower but still very effective. |
I think you are talking about "www dot research dot att dot com/~gsf/sudoku/sudoku dot html". This is gsf's web site. however I can't find any source code there...
Thank you anyway.
PS.
Completely off-topic and not directed at anyone in particular. This forum is not allowing me to post a link unless I have made 5 posts. I'm wondering, is this really impeding anybody but legitimate users? If I'm an evil spam script I can create 5 useless posts in time shorted than you need to say 'bang!'. |
|
| Back to top |
|
|
| zespri
| | Joined: 02 Dec 2007 | | Posts: 11 | | : | |
Items |
|
| Posted: Mon Dec 03, 2007 12:15 am Post subject: |
|
|
| garthd wrote: | This is a fast brute force algorithm for visual basic - seems to easily solve the hardest puzzles in under a second - and can be used to find the first solution or to check for multiple solutions.
|
Thank you very much, I'll have a look I think this is exactly what I need. |
|
| Back to top |
|
|
| zespri
| | Joined: 02 Dec 2007 | | Posts: 11 | | : | |
Items |
|
| Posted: Mon Dec 03, 2007 12:19 am Post subject: |
|
|
| wapati wrote: |
Dancing Links is a well known brute force method.
|
Thanks a lot, I've herad of DLX but I haven't realized that this was a brute force solver. The sticky has planty information on DLX and even a C++ sample implementation, which I'll make sure to look at.
Thank you again. |
|
| Back to top |
|
|
| zespri
| | Joined: 02 Dec 2007 | | Posts: 11 | | : | |
Items |
|
| Posted: Mon Dec 03, 2007 5:14 am Post subject: |
|
|
| zespri wrote: | | daj95376 wrote: | | gsf posted a C brute force solver in this forum a long time back. I don't have the link, but it is very fast when solving for a solution to a puzzle. If you have it search for multiple solutions, then it's slower but still very effective. |
I think you are talking about "www dot research dot att dot com/~gsf/sudoku/sudoku dot html". This is gsf's web site. however I can't find any source code there...
Thank you anyway.
|
Ok, I located the source code. Cheers! |
|
| Back to top |
|
|
| zespri
| | Joined: 02 Dec 2007 | | Posts: 11 | | : | |
Items |
|
| Posted: Sun Dec 16, 2007 12:18 am Post subject: |
|
|
I'd like to thank everybody again for the head ups. I think that Glenn's implementation of the brute force solver is simply amazing. Here is my port of this implementation to C#. The goal of this port for me was to prove that I understand the algorythm well enough and to try to express it in such a way that is (hopfully) slighltly easier to understand than the C counterpart. Of course we significantly lose on performance this way.
| Code: | /* Written by Andrew Savinykh [trashbin@brutsoft.com]
* This class implements a simple Sudoku brute force solver
* This code based on the Glenn Fowler's C brute force solver "sudocoo"
* http://www.research.att.com/~gsf/cgi-bin/download.cgi?action=list&name=ast-sudoku
*
* This implementation is less efficient then the C implementation, however it's
* (hopefully) easier to read, to be able to understand the algorythm behind it
*
* On my 6600 @ 2.4mHz it solves first 1000 puzzles from the 17 clues sudoku list
* http://people.csse.uwa.edu.au/gordon/sudokumin.php
* with the rate 88ms per puzzle on average. And roughly twice as fast if we look
* for the first solution only.
*
* No validation on input - the same as in the C implementation.
*/
using System;
using System.Text;
using System.Collections.Generic;
namespace SimpleSudokuBruteForceSolver
{
public class SudokuSolver
{
private Cell[,] m_grid = new Cell[9, 9];
// These give unused numbers (also called candidates) in each column, row and box respectively
// The candidates for a cell is the intersection of the candidates for the column,
// the row and the box this cell belongs to
// Each candidate is represented by a bit in the int. Bits 0-8 are used. Set bit (1) means that
// the candidate is available. Reset bit (0) means that this number already occures in an occupied
// cell in this row/column/box
private int[] m_rowCandidates = new int[9];
private int[] m_columnCandidates = new int[9];
private int[] m_boxCandidates = new int[9];
// List of unoccupied (yet) cells
private List<Cell> m_freeCells = new List<Cell>();
private SudokuSolver(string grid)
{
InitializeCells();
InitializeCandidats();
FillCells(grid);
}
// Create each individual cell in our 9x9 grid and add every cell
// to the free cells list as initially all the cells are empty
private void InitializeCells()
{
for ( int i = 0; i < 9; i++ )
{
for ( int j = 0; j < 9; j++ )
{
m_freeCells.Add(m_grid[i, j] = new Cell(this, i, j));
}
}
}
// Initially every candidate is set (1), because there is no occupied cells
private void InitializeCandidats()
{
for ( int i = 0; i < 9; i++ )
{
m_rowCandidates[i] = 0x1FF;
m_columnCandidates[i] = 0x1FF;
m_boxCandidates[i] = 0x1FF;
}
}
// Insert initial clues in the grid. The parameter is standard sudoku puzzle format
// Ex. "...6.9....25...97.4.......87..321..5...9.78..9..485..72.......9.73...61....1.8..."
private void FillCells(string grid)
{
int current = 0;
for ( int i = 0; i < grid.Length; i++ )
{
if ( grid[i] == '.' || grid[i] == '0' )
{
current++;
continue;
}
if ( grid[i] >= '1' && grid[i] <= '9' )
{
m_grid[current / 9, current % 9].Value = int.Parse(grid[i].ToString());
current++;
}
}
}
// This converts the current grid into the string representation
// Ex. "...6.9....25...97.4.......87..321..5...9.78..9..485..72.......9.73...61....1.8..."
public override string ToString()
{
StringBuilder sb = new StringBuilder(81);
for ( int i = 0; i < 9; i++ )
{
for ( int j = 0; j < 9; j++ )
{
sb.Append(m_grid[i, j].Value == 0 ? "." : m_grid[i, j].Value.ToString());
}
}
return sb.ToString();
}
// This is the method that is to be called by the user of this class
// A grid to solve (as a standard sudoku puzzle string) should be specified
// And the maximimum number of results to look for
// Pass 1 to find a solution / check if there is a solution
// Pass 2 to check if a puzzle has more then one solution
// Pass int.MaxValue to find many results (if they exist)
public static IList<string> SolveSudoku(string grid, int maxResult)
{
SudokuSolver solver = new SudokuSolver(grid);
return solver.SolveSudoku(maxResult);
}
// This is the main solver function. It is called recursively.
private IList<string> SolveSudoku(int maxResults)
{
List<string> results = new List<string>();
// Search of a solution is most efficient when we start with the cells
// that have the minimum candidates to try
Cell cell = FindCellWithMinimumCandidates();
// This indicates that there is no more empty (unsolved) cells,
// and thus, we have a solution
if ( cell == null )
{
results.Add(ToString());
return results;
}
// If the grid contains a cell with no possible candidates,
// then there is no soultion for this puzzle. Return empty result set
if ( cell.Candidates.Count == 0 )
{
return results;
}
foreach ( int candidate in cell.Candidates )
{
// For each candidate, let's assume that this candidate is right and
// put it into the cell. Now let's try to solve the resulting puzzle
// now, when it has one less empty cell.
cell.Value = candidate;
IList<string> tmpResults = SolveSudoku(maxResults);
// If we found enough solutions, just return them
if ( tmpResults.Count == maxResults )
{
return tmpResults;
}
// Add the found solutions to the result set
results.AddRange(tmpResults);
}
// As we may be called reqursively we need to restore the state of the grid
// to what it was when we entered the function. So we clear the cell again
// to its initial state
cell.Value = 0;
return results;
}
private Cell FindCellWithMinimumCandidates()
{
// If there are no unoccupied cells we let the calling function know
// by returning null
if ( m_freeCells.Count == 0 )
{
return null;
}
// The running minimum number of candidates
int candidates = m_freeCells[0].Candidates.Count;
// The cell with the mininmum number of candidates
Cell result = m_freeCells[0];
foreach ( Cell cell in m_freeCells )
{
int i = cell.Candidates.Count;
if ( i < candidates )
{
candidates = i;
result = cell;
}
// There can't be less then 0 candidates, so the search is finised if so
if ( candidates == 0 )
{
return result;
}
}
return result;
}
// This class represents a single cell in the grid and tightly coupled with the grid
private class Cell
{
// The grid the cell belongs to
private SudokuSolver m_parent;
// The row, column and box of the cell
private int m_column;
private int m_row;
private int m_box;
// The value in the cell, 0 - if the cell is empty
private int m_value;
// This is a lookup table, created for speed. Given a candidates bitmask
// it returns the individual candidates. Ex. 5 will result in a list of two
// values: 1 and 3.
private static readonly IList<int>[] m_bitLookup = new IList<int>[1 << 9];
static Cell()
{
InitializeBitLoookupTable();
}
private static void InitializeBitLoookupTable()
{
for ( int i = 0; i < m_bitLookup.Length; i++ )
{
List<int> list = new List<int>();
m_bitLookup[i] = list;
for ( int j = 0; j < 9; j++ )
{
if ( ((1 << j) & i) != 0 )
{
list.Add(j + 1);
}
}
}
}
public Cell(SudokuSolver parent, int row, int column)
{
m_column = column;
m_row = row;
m_box = GetBoxNumber(row, column);
m_parent = parent;
}
private static int GetBoxNumber(int row, int column)
{
return (row / 3) * 3 + column / 3;
}
// This gives the list of candidates for the cell by combining information
// of candidated for the row, column and box of the cell
public IList<int> Candidates
{
get
{
return m_bitLookup[m_parent.m_rowCandidates[m_row] & m_parent.m_columnCandidates[m_column] & m_parent.m_boxCandidates[m_box]];
}
}
public int Value
{
get
{
return m_value;
}
// When we set a value we have to do several things
set
{
if ( value == m_value )
{
return;
}
// If the cell was not empty we need to set the candidates back
// as we remove the old value from the cell
if ( m_value != 0 )
{
FlipCandidates(m_value);
}
// If the value to set is not empty then we need to remove this value
// from the candidates for row, column and cell
if ( value != 0 )
{
FlipCandidates(value);
}
// If we fill a empty cell we need to remove it from the empty cell list
if ( (value == 0) && (m_value != 0) )
{
m_parent.m_freeCells.Add(this);
}
// If we empty a cell we need to put it back to the empty cell list
if ( (value != 0) && (m_value == 0) )
{
m_parent.m_freeCells.Remove(this);
}
m_value = value;
}
}
// This will flip the given candidate in the list of candidates
// for row, column and box
private void FlipCandidates(int candidate)
{
candidate = 1 << (candidate - 1);
m_parent.m_rowCandidates[m_row] ^= candidate;
m_parent.m_columnCandidates[m_column] ^= candidate;
m_parent.m_boxCandidates[m_box] ^= candidate;
}
}
}
} |
|
|
| Back to top |
|
|
| hall9000
| | Joined: 31 Mar 2008 | | Posts: 1 | | : | | Location: belgium |
Items |
|
| Posted: Mon Mar 31, 2008 5:35 pm Post subject: |
|
|
I just learned about sudoku's a couple of weeks ago. I made a brute force in Delphi. It goes around 180ms (Q6600) for a very hard one. If I have time I put some assembler in it 
No option for the moment to find all solutions for a given one, but should be easy to implement
hmm .. code lost some formating after copy paste
| Code: | unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, StdCtrls, ExtCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Grid: TStringGrid;
procedure Button1Click(Sender: TObject);
end;
var
Form1: TForm1;
Cube : array[0..8,0..8] of byte;
implementation
{$R *.dfm}
procedure GoSolve;
var
hoekx,hoeky,i,j : word;
ms : longint;
value : byte;
afreespaces : word;
freespace : array[0..90] of record
x,y, minicubeX, minicubeY : word;
end;
Function WorksFine(testlevel, valueToTest :byte): boolean;
var
m,n,localx,localy : word;
label
gobackfalse,goback;
begin
localx:= freespace[testlevel].x;
localy:= freespace[testlevel].y;
hoekx := freespace[testlevel].minicubeX;
hoeky := freespace[testlevel].minicubeY;
// Is the ValueToTest OK for his local 3x3grid ? otherwise go back a level
for m:=hoekx to hoekx+2 do for n:=hoeky to hoeky+2 do if cube[m,n]=ValueToTest then goto gobackfalse;
// Is the ValueToTest already horizontaly present then go back a level
for m:=0 to 8 do if cube[localx,m]=ValueToTest then goto gobackfalse; // ai, hij staat er al
// Is the ValueToTest already verticaly present then go back al level
for m:=0 to 8 do if cube[m,localy]=ValueToTest then goto gobackfalse; // ai, hij staat er al
// great, our ValueToTest is a candidate for deeper investigation
cube[localx,localy] := ValueToTest; // put him in the 9x9 grid
worksfine:=true; // we presumes this value will stay
//if there are no more free spaces to fill then the puzzle is completed and we go back
if testlevel=afreespaces then goto goback;
//lets fill in the next gap
for m:=1 to 9 do if WorksFine(testlevel+1, m) then goto goback; // until nextlevel is also good
// there seems no solution going deeper, so we made a mistake in a previous level , erase this level and go back
cube[localx,localy] := 0;
gobackfalse:
worksfine := false;
goback:
end;
begin
ms:=gettickcount; // timing starts
// where are the gaps ??
afreespaces := 0;
for i:=0 to 8 do for j:=0 to 8 do if cube[i,j]=0 then begin
inc(afreespaces);
FreeSpace[aFreespaces].x := i;
FreeSpace[aFreespaces].y := j;
Freespace[aFreespaces].minicubeX := (i div 3)*3; //precalc 3x3 cube starts
Freespace[aFreespaces].minicubeY := (j div 3)*3;
end;
value:=0;
repeat inc(value) until worksfine(1,value); // we try a number in first gap
// until we find a solution
ms:= gettickcount-ms;
for i:=0 to 8 do for j:=0 to 8 do form1.Grid.Cells[j,i] := intTostr(cube[i,j]);
form1.caption:=inttostr(ms)+' ms needed'
end;
procedure TForm1.Button1Click(Sender: TObject);
var
f : textfile;
l : string;
x,y : byte;
begin
// load sudoku from text file 9 lines
assignfile(f, 'input.txt'); reset(f);
for x:=0 to 8 do begin
readln(f,l);
for y:=0 to 8 do cube[x,y] := strToint(l[y+1]);
end;
closefile(f);
GoSolve;
end;
end. |
|
|
| Back to top |
|
|
|
|
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
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
