In file "sudoku.dat" is 9x9 size matrix. In one 3x3 bloc, can be from 2 up to 6 unknew digits, however main unknow digits amount in all matrix, must be not over 36 digits.
Unknow places marked with symbol ?
Example (3x3)
?9?
4??
?32
I need program which could write, does mentioned matrix has solution according by by traditional sudoku rules, if yes solve that sudoku.

Thanks

Dani AI

Generated

To clarify the request from and the thread commentary from , and : a compact, reliable approach is backtracking with simple constraint propagation and bitmasks. Validate the initial grid first (no repeated digits in any row, column or 3x3 box). Maintain three 9-entry bitmasks (rows, cols, boxes) where bit 0 represents digit 1, bit 8 represents digit 9. Collect empty cells, then recurse using MRV (choose the empty cell with the fewest legal digits). Stop early on any empty cell with zero candidates. For uniqueness testing, count solutions up to 2 and stop when two are found.

The following C skeleton shows the core solver idea (parsing, file IO and initial validation omitted for brevity):

/* use bits 0..8 for digits 1..9 */
int rowMask[9]={0}, colMask[9]={0}, boxMask[9]={0};
int grid[9][9];
struct Pos { int r,c; } empties[81];
int emptiesCount = 0;

int boxIndex(int r,int c){ return (r/3)*3 + (c/3); }
int bitcount(int x){ int c=0; while(x){ x &= x-1; ++c; } return c; }

int solve(int k){
  if (k == emptiesCount) return 1; /* solved */
  int best=-1, bestCnt=10, bestMask=0;
  for (int i=k;i<emptiesCount;i++){
    int r=empties[i].r, c=empties[i].c;
    int mask = ~(rowMask[r] | colMask[c] | boxMask[boxIndex(r,c)]) & 0x1FF;
    int cnt = bitcount(mask);
    if (cnt==0) return 0;
    if (cnt < bestCnt){ bestCnt=cnt; best=i; bestMask=mask; }
  }
  struct Pos tmp = empties[k]; empties[k]=empties[best]; empties[best]=tmp;
  int r=empties[k].r, c=empties[k].c, b=boxIndex(r,c);
  for (int d=0; d<9; ++d){
    int bit = 1<<d;
    if (bestMask & bit){
      rowMask[r]|=bit; colMask[c]|=bit; boxMask[b]|=bit;
      grid[r][c]=d+1;
      if (solve(k+1)) return 1;
      rowMask[r]&=~bit; colMask[c]&=~bit; boxMask[b]&=~bit;
      grid[r][c]=0;
    }
  }
  tmp = empties[k]; empties[k]=empties[best]; empties[best]=tmp;
  return 0;
}

Notes: when reading sudoku.dat, treat non-digits as blanks and set masks while checking for initial conflicts. For speed with up to ~36 blanks, MRV plus bitmasks is usually instant. If a faster or more general solver is required (or uniqueness must be enumerated fully), consider an exact-cover implementation (Algorithm X / DLX) later. This skeleton keeps the logic clear and leaves IO/validation as implementable next steps without handing over a full finished program.

Recommended Answers

All 4 Replies

Huh? I'm sorry but what exactly is your question? you have given a set of statements with no question.

Huh? I'm sorry but what exactly is your question? you have given a set of statements with no question.

I need program code in C

> I need program code in C
No, that's what you would like, not what you need.

What you need is to make an effort to solve your own homework, then ask a specific question when you get stuck.

Wanting someone to spoon-feed you an answer while you go off partying or something just isn't going to happen.

If you don't make an effort on this one, the next homework is going to look even more impossible to you. If you can't deal with this, just drop the course now.

Can someone show this moron why we don't give away code?
Now, that's a question.

I need program code in C

Is not a question.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.