Sudoku, backtrack algorithm

Question

Sudoku backtrack method

int xx = (pos.getX() / 3) * 3;          
int yy = (pos.getY() / 3) * 3;           
for (int y = 0; y < 3; y++) {              
    for (int x = 0; x < 3; x++) {               
        if ((xx + x != pos.getX()) && (yy + y != pos.getY())) {            
            possible[work[xx + x][yy + y]] = false;

where x and y =

private byte x;
private byte y;

Could someone explain why do we divide by three and multiply by three?

(pos.getY() / 3) * 3;                      
(pos.getX() / 3) * 3;

brain · Accepted Answer · 2012-05-22 10:09:54Z

1

The division is integer division so it will remove the remainder. Doing the integer division following by a multiplication will give the you the first cell index of the correct 3x3 block.

E.g.

pos    0    1    2    3    4    5    6    7    8
/3     0    0    0    1    1    1    2    2    2
*3     0    0    0    3    3    3    6    6    6

answered May 22, 2012 at 10:09

brain

5,5561 gold badge29 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Thomash · Accepted Answer · 2012-05-22 09:52:28Z

1

Because we want a multiple of 3. We want the greatest multiple of 3 that is less than pos.getX(). It corresponds to the upper-left cell in the current 3x3 square.

Remember X/3 must be an integer so (X/3)*3 may not be equal to X.

answered May 22, 2012 at 9:52

Thomash

6,3791 gold badge32 silver badges50 bronze badges

Collectives™ on Stack Overflow

Sudoku, backtrack algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related