Markus Schoder wrote:[color=blue]
>
kalinga1234@gmail.com wrote:[color=green]
> > hy guys
> >
> > i am having a problem with my sudoku program which i coded using c++.;
> > currently in my program if a duplicate number exist in either
> > row/column/block i would make the particualr square 0. but thats not i
> > want to do. I want to recurse back until until it find a correct
> > number. i will post the function which i need the help;[/color]
>
> I assume you want to backtrack if you reach an illegal situation. This
> can indeed be done easiest with recursion like so (not tested):[/color]
[...code snipped...]
[color=blue]
> That said I am pretty sure this will never fly because it is too slow.
> Given enough time it should however in principal create a valid sudoku
> (a poor rand() implementation could send it in an infinite loop though).[/color]
Turns out you can generate a random sudoku grid surprisingly fast with
some additional validity checks to cause early backtracking. Below is a
complete program that does it. There is a tiny bit of non-standard C++
in there. You need uint8_t and int16_t types from the C99 stdint.h
header and the ffs() function (find first bit set) from POSIX.
#include <cstdlib>
#include <stdint.h>
#include <iostream>
#include <vector>
#include <strings.h>
using namespace std;
class sudoku
{
public:
struct avail_t
{
int16_t a[9][9];
};
bool solve();
uint8_t get(const int r, const int c) const {return grid_[r][c];}
void set(const uint8_t v, const int r, const int c)
{grid_[r][c] = v; avail_.a[r][c] = -1;}
vector<uint8_t> get_valid(int r, int c) const;
bool update_avail(uint8_t v, int r, int c);
avail_t get_avail() const {return avail_;}
void set_avail(const avail_t &avail) {avail_ = avail;}
private:
bool generation(int r, int c);
uint8_t grid_[9][9];
avail_t avail_;
};
vector<uint8_t>
sudoku::get_valid(int r, int c) const
{
vector<uint8_t> valids;
int mask = avail_.a[r][c];
while(mask)
{
valids.push_back(ffs(mask) - 1);
mask &= mask - 1;
}
return valids;
}
bool
sudoku::update_avail(const uint8_t v, const int r, const int c)
{
const int16_t mask = ~int16_t(1 << v);
for(int c1 = 0; c1 < 9; ++c1)
{
if(c1 != c && avail_.a[r][c1] >= 0)
{
if(!(avail_.a[r][c1] &= mask))
return false;
}
}
for(int r1 = 0; r1 < 9; ++r1)
{
if(r1 != r && avail_.a[r1][c] >= 0)
{
if(!(avail_.a[r1][c] &= mask))
return false;
}
}
const int ra = r / 3 * 3;
const int ca = c / 3 * 3;
for(int r1 = ra; r1 < ra + 3; ++r1)
for(int c1 = ca; c1 < ca + 3; ++c1)
if((r1 != r || c1 != c) && avail_.a[r1][c1] >= 0)
{
if(!(avail_.a[r1][c1] &= mask))
return false;
}
return true;
}
bool
sudoku::generation(int r, int c)
{
if(c == 9)
{
if(++r == 9)
return true;
c = 0;
}
const vector<uint8_t> valids = get_valid(r, c);
if(valids.empty())
return false;
const int i0 = rand() % valids.size();
int i = i0;
do
{
const uint8_t v = valids[i];
const avail_t old_avail = get_avail();
if(update_avail(v, r, c))
{
set(v, r, c);
if(generation(r, c + 1))
return true;
}
set_avail(old_avail);
if(++i == (int)valids.size())
i = 0;
}
while(i != i0);
return false;
}
bool
sudoku::solve()
{
for(int r = 0; r < 9; ++r)
for(int c = 0; c < 9; ++c)
avail_.a[r][c] = (1 << 9) - 1;
return generation(0, 0);
}
int
main(const int argc, const char *const argv[])
{
ios::sync_with_stdio(false);
if(argc >= 2)
srand(strtol(argv[1], 0, 10));
sudoku s;
if(!s.solve())
{
cerr << "No sudoku grid found (bug)!\n";
return 1;
}
for(int r = 0; r < 9; ++r)
{
for(int c = 0; c < 9; ++c)
cout << char('1' + s.get(r, c));
cout << '\n';
}
}
