Sudoku Programmers :: View topic - Brute force solver code optimisation [C++]

FAQ

Memberlist

Usergroups

Profile

Brute force solver code optimisation [C++]

Sudoku Programmers Forum Index -> Programming sudoku

View previous topic :: View next topic

Author

Message

Zarzyk

Joined: 17 May 2009

Posts: 1

Items

Posted: Mon May 18, 2009 7:07 pm Post subject: Brute force solver code optimisation [C++]

Hi ! This is my first post on this forum Smile

I read some topics concerning brute force algorithms and wanted to try if I'm able to write such a program in C++ Builder. I'm a newbie in programming so I need Your help.

I wrote *something* but it don't work as it should Sad

. It's based on "4 line sudoku solver" but is's terrible slow. Can you look at the code and help me with optimisation? You can find topic about 4line sudoku on this forum, I can't write a url because I'm new here.
empty[80] - array storing empty cell numbers
sudoku[80] - array representing sudoku board, cells numbered 0-80

Code:

bool czyPasuje (int n) { //checking if digit is legal in current cell
int row, col,i,j,k=0;
row = n / 9;
col = (n % 9);
for (i=0; i<9; i++)
{
if (sudoku[row * 9 + i] == sudoku[n]) k=k+1;
if (sudoku[col + i * 9] == sudoku[n]) k=k+1;
}

col = 3 * (col / 3);
row = 3 * (row / 3);
for (i=0; i<=2; i++)
for (j=col; j<=(col+2);j++)
if (sudoku[(row + i)*9+j] == sudoku[n]) k = k + 1;
if (k==3) return true; else return false;
}

bool czySaPustePola() { //Checking is there any empty cell left
int i;
for (i=0; i<81; i++) if (sudoku[i]==0) return true;
}

void rozw () { //solver main loop
int wsk=0; //pointer
whhile (wsk > -1) {
sudoku[empty[wsk]] = ((sudoku[empty[wsk]] + 1) % 10);
if ((sudoku[empty[wsk]] == 0)) wsk = (wsk + 1);
else if (czyPasuje(empty[wsk])) wsk = (wsk - 1);
}
}

And function initiation

Code:

while (czySaPustePola())
rozw();

Hope you can help me. For example it takes a lot of time (dont know how much, because it took more than 2 hours) to solve X-Shape sudoku.

Sorry if you fell offended with my english, it's not my first language Wink

Lunatic

Joined: 11 Mar 2007

Posts: 166

Location: Ghent - Belgium

Items

Posted: Tue May 19, 2009 4:14 pm Post subject:

Maybe this will help....

Code:

#include<conio.h>
#include<stdlib.h>
#include<stdio.h>

void initiate();
int brutesolvesudoku();
void removecandidates(int);
void undo();

int unsolvedcells[81];
int cellptr;
int solution[81];
int sudoku[81];
int cellscandidates[81];
int countcandidates[512];
int cellsboxnumber[81];
int boxcellnumbers[9][9];
int lastcandidate[81];
int logsteps;
int logcell[81];
int logrow[81];
int logcolumn[81];
int logbox[81];

void main(void)
{
initiate(); //initiate arrays and base data
//PREPARE ARRAY sudoku[] HERE
if (brutesolvesudoku()==1)//if return value is 1, then there was one unique solution
{
//handle the unique solution
}
else//if return value is not 1, then there was no unique solution
{
//handle the failure
}
}
}

void initiate(void)
{
int i;
int j;
int k;
int l;
int cell;
int box;
//possible candidates for each cell are stored bitwise in array
//cellscandidates[].If candidate 1 is present then bit 0 is set,
//if candidate 2 is present then bit 1 is set, and so on...
//The array countcandidates[] will return the number of candidates
//if feeded with any cell's cellscandidates[]
//Here, the array countcandidates[] is initiated.
for(i=0;i<512;i++)
{
j=i;
countcandidates[i]=0;
while (j>0)
{
if (j%2>0) countcandidates[i]++;
j=(j-(j%2))/2;
}
}
//Boxes are adressed 0 to 8 from top left to bottom right
//The array cellsboxnumber[] will return the boxnumber for
//any cell, it acts as some kind of boxmap.
//The array boxcellnumbers[][] holds the 9 cellnumbers
//for each box. Here we initiate both arrays
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
for(k=0;k<3;k++)
{
for(l=0;l<3;l++)
{
cell=(j*27)+(i*3)+(l*9)+k;
box=(j*3)+i;
cellsboxnumber[cell]=box;
boxcellnumbers[box][(l*3)+k]=cell;
}
}
}
}
}

int brutesolvesudoku(void)
{
int i;
int j;
int k;
int solvedcells;
int row;
int column;
int box;
int currentcell;
int countsolutions;
int boundary;
//This routine will brute force solve the puzzle contained in sudoku[] and put the solution in solution[]
//When found the first solution (and hopefully the only solution), the last solved cell
//will be rejected so the search will continue. If another solution is found
//the routine will be halted and countsolutions will be 2, indicating that there
//are at least 2 solutions, and the brute force loop will be stopped.
//If there is only one solution, this brute force will
//eventually backtrack beyond the first solved cell, can't have that!
//Therefore, a boundary is set to prevent this, and ends the brute force loop.
//At last, the value from countsolutions is returned (0=no solution, 1=1 solution, 2=at least 2 solutions)

//initiation
countsolutions=0;//reset solution counter (return value)
for(i=0;i<81;i++)
{
//transfer the sudoku puzzle to solution[]
solution[i]=sudoku[i];
//set all candidates available for all cells
cellscandidates[i]=511;
//clear last candidate indicator for all cells
lastcandidate[i]=0;
}

solvedcells=0;//setup solved cells counter
//update cellscandidates[]
for(i=0;i<81;i++)//scan sudoku[]
{
if (solution[i]>0)//for each solved cell...
{
solvedcells++;//update solved cells counter
//update cells candidates
//remove candidates for each solved cell
cellscandidates[i]=0;
row=i/9;//calculate row from solved cell
column=i%9;//calculate column from solved cell
box=cellsboxnumber[i];//get boxnumber from solved cell
j=1;//prepare candidate bitmask
if (solution[i]>1)
{
for (k=1;k<solution[i];k++) j=j*2;//update candidate bitmask
}
for (k=0;k<9;k++)//for all positions in row, column or box...
{
//remove candidate from cells in row
cellscandidates[(row*9)+k]=cellscandidates[(row*9)+k]&(511^j);
//remove candidate from cells in column
cellscandidates[(k*9)+column]=cellscandidates[(k*9)+column]&(511^j);
//remove candidate from cells in box
cellscandidates[boxcellnumbers[box][k]]=cellscandidates[boxcellnumbers[box][k]]&(511^j);
}
}
}

//collect unsolved cells
cellptr=-1;//reset unsolved cell pointer
for(i=0;i<81;i++)//scan sudoku[]
{
if (solution[i]==0)//for each unsolved cell...
{
//collect all unsolved cells
//increase cellptr for each unsolved cell
cellptr++;
//transfer cellnumber for each unsolved cell to array unsolvedcells[]
unsolvedcells[cellptr]=i;
}
}

boundary=cellptr+1;//set boundary
logsteps=-1;//reset log stepcounter
countsolutions=0;//clear solution counter

while (cellptr<boundary)//do brute force loop but don't let it backtrack beyond the first unsolved cell
{
if (cellptr==-1)//check cellptr, if -1 then a solution is found
{
//solution found, increase solution counter
countsolutions++;
//if this is the second solution then break the brute force loop
if (countsolutions==2) break;
//at this point only one solution is found, now reject
//the last solved cell by increasing cellptr, so the search
//can continue for other solutions, if any
cellptr++;
}
currentcell=unsolvedcells[cellptr];
if (solution[unsolvedcells[cellptr]]==0)
{
for(i=0;i<cellptr;i++)
{
if (countcandidates[cellscandidates[unsolvedcells[i]]]<countcandidates[cellscandidates[unsolvedcells[cellptr]]])
{
j=unsolvedcells[i];
unsolvedcells[i]=unsolvedcells[cellptr];
unsolvedcells[cellptr]=j;
}
}
currentcell=unsolvedcells[cellptr];
j=1;
for(i=0;i<9;i++)
{
if ((cellscandidates[currentcell]&j)>0)
{
solution[currentcell]=i+1;
break;
}
j=j*2;
}
if (countcandidates[cellscandidates[currentcell]]==1) lastcandidate[currentcell]=1;
removecandidates(currentcell);
j=cellptr;
cellptr--;
if (cellptr>-1)
{
for(i=0;i<j;i++)
{
if (cellscandidates[unsolvedcells[i]]==0)
{
cellptr++;
break;
}
}
}
}
else
{
if (lastcandidate[currentcell]==1)
{
undo();
lastcandidate[currentcell]=0;
cellptr++;
}
else
{
j=1;
k=solution[currentcell];
undo();
for(i=0;i<k;i++) j=j*2;
for(i=k;i<9;i++)
{
if ((cellscandidates[currentcell]&j)>0)
{
solution[currentcell]=i+1;
break;
}
j=j*2;
}
lastcandidate[currentcell]=1;
if (solution[currentcell]<9)
{
for(i=solution[currentcell];i<9;i++)
{
j=j*2;
if ((cellscandidates[currentcell]&j)>0)
{
lastcandidate[currentcell]=0;
break;
}
}
}
removecandidates(currentcell);
j=cellptr;
cellptr--;
if (cellptr>-1)
{
for(i=0;i<j;i++)
{
if (cellscandidates[unsolvedcells[i]]==0)
{
cellptr++;
break;
}
}
}
}
}
}
//brute force loop ended, return countsolutions
return (countsolutions);
}

void removecandidates(int currentcell)
{
int i;
int j;
int k;
int l;
int row;
int column;
int box;
//Each unsolved cell that shares the same row, column or box with the current cell
//will loose the value last placed in the current cell as candidate
//The current cell is saved, along with the positions of the cells losing the candidate,
//related to their row, column or box.
//If the brute force handler needs to backtrack, the undo() routine uses this information
//to restore those candidates
logsteps++;//increase stepcounter

logcell[logsteps]=currentcell;//save current cell, this is the last altered cell
logrow[logsteps]=0;//clear row log
logcolumn[logsteps]=0;//clear column log
logbox[logsteps]=0;//clear box log

row=currentcell/9;//calculate the row where the current cell belongs to
column=currentcell%9;//calculate the column where the current cell belongs to
box=cellsboxnumber[currentcell];//get the boxnumber for the current cell

j=1;//prepare candidate bitmask
if (solution[currentcell]>1)
{
for(i=1;i<solution[currentcell];i++) j=j*2;//update candidate bitmask
}
for(i=0;i<cellptr;i++)//scan all unsolved cells
{
if ((cellscandidates[unsolvedcells[i]]&j)>0)//test if candidate is present
{
if (unsolvedcells[i]/9==row)//check if it shares row with current cell
{
l=1;//prepare position bitmask
for(k=0;k<9;k++)//search position in row
{
if ((row*9)+k==unsolvedcells[i])//if position found...
{
logrow[logsteps]=logrow[logsteps]|l;//set position bit in row log
cellscandidates[unsolvedcells[i]]=cellscandidates[unsolvedcells[i]]&(511^j);//remove candidate from list
break;//stop position search
}
l=l*2;//update position bitmask
}
}
else if (unsolvedcells[i]%9==column)//check if it shares column with current cell
{
l=1;//prepare position bitmask
for(k=0;k<9;k++)//search position in column
{
if ((k*9)+column==unsolvedcells[i])//if position found...
{
logcolumn[logsteps]=logcolumn[logsteps]|l;//set position bit in column log
cellscandidates[unsolvedcells[i]]=cellscandidates[unsolvedcells[i]]&(511^j);//remove candidate from list
break;//stop position search
}
l=l*2;//update position bitmask
}
}
else if (cellsboxnumber[unsolvedcells[i]]==box)//check if it shares box with current cell
{
l=1;//prepare position bitmask
for(k=0;k<9;k++)//search position in box
{
if (boxcellnumbers[box][k]==unsolvedcells[i])//if position found...
{
logbox[logsteps]=logbox[logsteps]|l;//set position bit in box log
cellscandidates[unsolvedcells[i]]=cellscandidates[unsolvedcells[i]]&(511^j);//remove candidate from list
break;//stop position search
}
l=l*2;//update position bitmask
}
}
}
}
}

void undo(void)
{
int i;
int j;
int k;
int l;
int row;
int column;
int box;
//This routine uses the information stored by removecandidates[] to replace
//the last removed candidates from the unsolved cells whenever the brute force
//handler needs to backtrack
k=solution[logcell[logsteps]];//get the candidate value
solution[logcell[logsteps]]=0;//clear the solution

row=logcell[logsteps]/9;//calculate row
column=logcell[logsteps]%9;//calculate column
box=cellsboxnumber[logcell[logsteps]];//get boxnumber

j=1;//prepare candidate bitmask
if (k>1)
{
for(i=1;i<k;i++) j=j*2;//update candidate bitmask
}
l=1;//prepare position bitmask
for(i=0;i<9;i++)//scan all positions
{
//if position is in row log then replace candidate
if ((logrow[logsteps]&l)>0) cellscandidates[(row*9)+i]=cellscandidates[(row*9)+i]|j;
//if position is in column log then replace candidate
if ((logcolumn[logsteps]&l)>0) cellscandidates[(i*9)+column]=cellscandidates[(i*9)+column]|j;
//if position is in box log then replace candidate
if ((logbox[logsteps]&l)>0) cellscandidates[boxcellnumbers[box][i]]=cellscandidates[boxcellnumbers[box][i]]|j;
l=l*2;//update position bitmask
}
logsteps--;//decrease logcounter (for next backtrack, if needed)
}

This code is also based upon the four-line-solver, but is improved a bit.
Offcourse, you must somehow fill the array sudoku[] before running the brutesolvesudoku() routine !!!
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~

Display posts from previous:

	Sudoku Programmers Forum Index -> Programming sudoku	All times are GMT
Page 1 of 1

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