Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Mapping 3x3 boxes to rows

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku
View previous topic :: View next topic  
Author Message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Tue Jan 03, 2006 8:27 pm    Post subject: Mapping 3x3 boxes to rows Reply with quote

Does anyone know of a mapping algorithm that allows a solver program to treat the cells of a 3x3 box as if they were cells of a row?

I'd like the program to loop thru code 3 times ...
  1. First, with no translation,
  2. Second, transposing the rows and columns, and
  3. Third, mapping the 3x3 boxes to rows ... and doing whatever else it takes to maintain a valid 9x9 grid yielding valid eliminations.
Thanks in advance for any suggestions, Ron
Back to top
View user's profile Send private message
ulcman

Joined: 10 Jan 2006
Posts: 1
:

Items
PostPosted: Tue Jan 10, 2006 10:37 pm    Post subject: Reply with quote

Consider R is the row number (1-9), C is the column no., B is the box no:

Then:

B = int((R-1)/3)*3+int((C-1)/3)+1

You can use this within the loops of the rows and columns...
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Wed Jan 11, 2006 1:11 am    Post subject: Re: Mapping 3x3 boxes to rows Reply with quote

rkral wrote:
Does anyone know of a mapping algorithm that allows a solver program to treat the cells of a 3x3 box as if they were cells of a row?

If the language you're using supports pointers, then I'd suggest using a pointer array (ie that points to your main cell array) to avoid calculating cell offsets every time you need a cell in a box.
Back to top
View user's profile Send private message Visit poster's website
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Fri Jan 13, 2006 6:08 pm    Post subject: Re: Mapping 3x3 boxes to rows Reply with quote

angusj wrote:
If the language you're using supports pointers, then I'd suggest using a pointer array (ie that points to your main cell array) to avoid calculating cell offsets every time you need a cell in a box.

Great idea, and I'm using C++ which has pointers.

So to ...
  1. Treat rows as rows,
  2. treat cols as rows, and
  3. treat boxes as rows
... I can use the following three mappings of cell pointers.
Code:

 1   2   3   4   5   6   7   8   9
10  11  12  13  14  15  16  17  18
19  20  21  22  23  24  25  26  27
28  29  30  31  32  33  34  35  36
37  38  39  40  41  42  43  44  45
46  47  48  49  50  51  52  53  54
55  56  57  58  59  60  61  62  63
64  65  66  67  68  69  70  71  72
73  74  75  76  77  78  79  80  81
      Normal (no re-mapping)       


 1  10  19  28  37  46  55  64  73
 2  11  20  29  38  47  56  65  74
 3  12  21  30  39  48  57  66  75
 4  13  22  31  40  49  58  67  76
 5  14  23  32  41  50  59  68  77
 6  15  24  33  42  51  60  69  78
 7  16  25  34  43  52  61  70  79
 8  17  26  35  44  53  62  71  80
 9  18  27  36  45  54  63  72  81
            Transposed       


 1   2*  3  10  11* 12  19  20* 21
 4   5   6  13  14  15  22  23  24
 7   8   9  16  17  18  25  26  27
28  29* 30  37  38* 39  46  47* 48
31  32  33  40  41  42  49  50  51
34  35  36  43  44  45  52  53  54
55  56* 57  64  65* 66  73  74* 75
58  59  60  67  68  69  76  77  78
61  62  63  70  71  72  79  80  81
           Row-Box Swap

In the first two cases, domain (row, col, box) interactions (buddy checks, etc.) work just fine, but that's not true in the 3rd case. This is because the column cells end up being scattered about. (The asterisks above indicate where the original col 2 cells ended up.)

What I was originally asking for was a mapping algorithm that would not scatter any domains ... but instead rearrange them so that normal domain interactions would hold true. (If that's only as clear as mud, let me know and I'll try another description. Smile )

Maybe such a mapping is an impossiblity.

Ron
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Fri Jan 13, 2006 9:58 pm    Post subject: Reply with quote

I've never written anything in C/C++ so the following may not compile, but it should still show you what I had in mind ...
Code:
int i,j;
int grid[81];
int* row[9][9];
int* col[9][9];
int* box[9][9];
//initialize row, col & box arrays ...
for (i=0; i<9, i++)
  for (j=0; j<9, j++){
    row[i][j] = &grid[i*9 + j];
    col[i][j] = &grid[j*9 + i];
    box[i][j] = &grid[(i / 3)*27+(i % 3)*3+(j / 3)*9+(j % 3)];
}
Back to top
View user's profile Send private message Visit poster's website
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Sat Jan 14, 2006 1:02 am    Post subject: Reply with quote

angusj wrote:
I've never written anything in C/C++ so the following may not compile, but it should still show you what I had in mind ...

We're thinking along the same line. The following compiles ...
Code:

#include <stdio.h>

void main() {
  int i,j;
  int grid[81];
  int* row[9][9];
  int* col[9][9];
  int* box[9][9];
  //initialize row, col & box arrays ...
  for (i=0; i<9; i++) {
    for (j=0; j<9; j++) {
      row[i][j] = &grid[i*9 + j];
      col[i][j] = &grid[j*9 + i];
      box[i][j] = &grid[(i / 3)*27+(i % 3)*3+(j / 3)*9+(j % 3)];
      // printf("%4d", i*9+j);
      // printf("%4d", j*9+i);
      printf("%4d", (i / 3)*27+(i % 3)*3+(j / 3)*9+(j % 3));
    }
    fprintf(stderr, "\n");
  }
}

... and uncommenting one printf at a time (3 different compiles), your formulas produced the same indices(minus 1) of my prior post.

Are you suggesting the same code that does, e.g., a color check of 'buddies' when in the 'row mode' will also work when in the 'box mode' ... just by using the appropriate mapping array? If so, I don't see it yet.

Thanks, Ron
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Sat Jan 14, 2006 4:12 am    Post subject: Reply with quote

rkral wrote:
Are you suggesting the same code that does, e.g., a color check of 'buddies' when in the 'row mode' will also work when in the 'box mode' ... just by using the appropriate mapping array? If so, I don't see it yet.

Well my grid array is really an array of cell objects, not integers, so each cell's respective row, col and box index is stored in the cell object too. Looking up buddies is therefore very simple. The same thing in C could be achieved by using a simple struct array for your grid:

Code:
struct cell {
    int idx; //main grid index
    int row; //ie row index
    int col;
    int box;
    int value;};
Back to top
View user's profile Send private message Visit poster's website
peterb

Joined: 10 Mar 2006
Posts: 2
:
Location: Germany

Items
PostPosted: Fri Mar 10, 2006 11:58 am    Post subject: Re: Mapping 3x3 boxes to rows Reply with quote

rkral wrote:
Does anyone know of a mapping algorithm that allows a solver program to treat the cells of a 3x3 box as if they were cells of a row?

I'd like the program to loop thru code 3 times ...
  1. First, with no translation,
  2. Second, transposing the rows and columns, and
  3. Third, mapping the 3x3 boxes to rows ... and doing whatever else it takes to maintain a valid 9x9 grid yielding valid eliminations.
Thanks in advance for any suggestions, Ron


Let i be the row index, j the column index. i, j in {1,...,9}
Define i1, i2, j1, j2 (in {1,2,3}) such that
i=3*(i1-1)+i2
j=3*(j1-1)+j2
Then the box index =3*(i1-1)+j1
an the cell-in-a-box index =3*(i2-1)+j2
Replace all loops over rows, cols or boxes by two nested loops over the corresponding two of the indexes i1, i2, j1, j2 . They will all have the same structure.
Peter
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Fri Mar 10, 2006 12:30 pm    Post subject: Re: Mapping 3x3 boxes to rows Reply with quote

peterb wrote:
Let i be the row index, j the column index. i, j in {1,...,9}
Define i1, i2, j1, j2 (in {1,2,3}) such that
i=3*(i1-1)+i2
j=3*(j1-1)+j2
......................

Thanks for the reply. I don't understand that "define" part, however. Is it possible to illustrate with an example?

TIA, Ron
Back to top
View user's profile Send private message
peterb

Joined: 10 Mar 2006
Posts: 2
:
Location: Germany

Items
PostPosted: Fri Mar 10, 2006 1:20 pm    Post subject: Re: Mapping 3x3 boxes to rows Reply with quote

rkral wrote:
peterb wrote:
Let i be the row index, j the column index. i, j in {1,...,9}
Define i1, i2, j1, j2 (in {1,2,3}) such that
i=3*(i1-1)+i2
j=3*(j1-1)+j2
......................

Thanks for the reply. I don't understand that "define" part, however. Is it possible to illustrate with an example?

TIA, Ron


E. g. for the row labelling:

i i1 i2
-------
1 1 1
2 1 2
3 1 3
4 2 1
5 2 2
6 2 3
7 3 1
8 3 2
9 3 3

Same for the cols with j.
So i1=2, i2=1 denotes the 4th row.
j1=3, j2=2 is the 8th col.
i1=3, j1=1 is the lower left box.
i2=2, j2=2 is the central cell of any box.

The symmetry between rows, cols and boxes only shows up in 4 dimensions (i1, i2, j1, j2), not in 2D (i, j)!

Peter
Back to top
View user's profile Send private message
kaipiranha

Joined: 14 Apr 2006
Posts: 1
:

Items
PostPosted: Fri Apr 14, 2006 1:12 pm    Post subject: Re: Mapping 3x3 boxes to rows Reply with quote

[quote="peterb"]The symmetry between rows, cols and boxes only shows up in 4 dimensions (i1, i2, j1, j2), not in 2D (i, j)!
[/quote]

Hi,
I have no thorough mathematical background but came to think, that the equivalence exists between rows and columns only. The relationship is not defined mathematically by the sudoku rule(s) but is implied by the given 2D grid layout.

The one rule pertains to any region, without making a difference between rows, columns and blocks and stipulates each to be filled without doubles.
The layout on the other hand, manifests that each row has exactly 1 cell in common with each column and vice versa. In contrast, the congruence of blocks with rows or columns is 3 or 0.

And that's why I think that most strategies have to use a different approach for rows with regards to columns over rows or columns with regards to blocks.


How my thoughts developed:
Like probably any number of people before me, I had tried to work out the number of 'equivalent' transformations for a valid sudoku matrix.
The incentive was to find an algo that would produce a canonical key for every 'valid' sudoku - beeing either completed or having only one solution, that is. This key would then help to re-identify a sudoku, regardless of its given incarnation (transformation).

Beside mapping of symbols I think, there can be any rearrangement of either columns or rows. At least as long as the 3 single rows or columns sharing one 'block-row or -column' stay together in this trinity.
(3!^4)^2 = 1679616

I believe, but can't prove, that transposition and other valid transformations are already acounted for by the above number.
Thus the total number of valid derivations (including symbol mapping) would be 1679616 * 9! (=609499054080).

Any guide to further insight, proof of right or wrong would be appreciated.

Thanks, Steffen
Back to top
View user's profile Send private message
strmckr

Joined: 24 Apr 2009
Posts: 52
:

Items
PostPosted: Wed Apr 29, 2009 3:34 pm    Post subject: Does anyone know of a mapping algorithm that allows a solver Reply with quote

this also does it for turbo pascal..

Code:
program boxtest;
uses crt;
var
xb,yb, A,box:integer;
xn,yn:integer;
i,it:integer;

begin
A:=0;
clrscr;
for xb:= 0 to 2 do {prim X box call }
begin
A:=a+1;
for yb:=0 to 2 do {prim y box call}
begin

Box:=(A+(yb*3)); {which box is call is a function of (X + 3(y))}


for it:=0 to 2 do { calls sub box y's}

for i:=1+(xb*3) to 3+(xb*3) do { calls sub box x's}

begin
Yn:=(a-xb)+(it)+(yb*3); {calculates real y's given sub box x}

writeln(box,' ( ',I, ',',yn,' )'); {prints box:(x,y) coridnals on screen}

end;

end;

end;

readln;
end.


this gives you box # with xy coridnals then you call xy from your string array (i use 3d arrays to represent the grid string.)

notes:
iteration 1 calls box 1:4:7
2 calls box 2:5:8
3 calls box 3:6:9

inversion y over x
1 calls box 1 2 3
2 calls 4 5 6
3 calls 7 8 9
Back to top
View user's profile Send private message
leeo

Joined: 24 Jun 2009
Posts: 6
:
Location: USA NW

Items
PostPosted: Mon Jun 29, 2009 1:13 pm    Post subject: Reply with quote

I first programmed sudoku as a 4-d array, but have since abandonded that approach in favor of a 1-d array with locator tables.

row-major or "typewriter" order appears to work as well as any form

00 01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16 17
...
72 73 74 75 76 77 78 79 80

Then, traversing the whole grid can be programmed
for( int i= 0; i < 81; i+ ){ ...

a table from the grid position (gp) form into row-column position would appear as two tables:

byte[] gprow= new byte[81]{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2 ....

byte[] gpcol= new byte[81]{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3 ....

and from rc into gp as a single 2-dimensional table:

byte[,] rc= new byte[10,10]{
new byte[10]{ 255, 255, 255, 255, 255, 255, 255, 255, 255, 255 },
new byte[10]{ 255, 0, 1, 2, 3, 4, 5, 6, 7, 8 },
new byte[10]{ 255, 9, 10, 11 ....

- - - - -

One of the most useful tables set I've found is the ability to enumerate each of the 20 cells that share a house with each cell on the grid.

This requires a fixed array of 1620 entries, but the result permits me to spend more mental energy on a particular search algorithm instead of navagation issues:

byte pos= 20; // r3c3
byte loc;
for( byte i= 0; i < 20; i++ ){
loc = housetouch[ houseloc[ pos ] + i ]; // loc shares a house (or two) with pos
...
}

I also found it useful to layout the 20 cells that touch a given cell in this fashion:
6 entries: shares a row but not a box in gp order
2 entires: shares a row and box in gp order
4 entries: shares a box but not a row or column in gp order
2 entries: shares a box and column in gp order
6 entires: shares a column but not a box in gp order

the result is that the layout appears
r r r r r r rb rb b b b b bc bc c c c c c c

so to find the cells that share only a box, for example would appear

for( byte i= 6; i < 14; i++ ){
loc = housetouch[ houseloc[ pos ] + i ];

though I define the constants
boxstart= 6;
boxlt= 14;

I'd be willing to share these navigator tables with anyone who would ask.

protected internal static byte[,] rc; // row column to grid position
protected internal static byte[,] bp; // box position to grid position
protected internal const byte housetouches= 9;
protected internal static byte[] tbgp; // tab to grid position
protected internal static byte[] gprow; // grid position to row
protected internal static byte[] gpcol; // ~ to column
protected internal static byte[] gpbox; // ~ to box
protected internal static byte[] gppos; // ~ to pos // telephone numberpad position in box

protected internal static byte[] housecb; // for col or box to grid position start points
protected internal static byte[] rowgp; // row to grid position -- identity for row-major arrangement
protected internal static byte[] colgp; // col to ~ // much use is deprecated due to improved touch[]
protected internal static byte[] boxgp; // box to ~ also deprecated similarly
protected internal const byte celltouches= 20;
internal enum touchrange{ row= 0, box= 6, rowlt= 8, col= 12, boxlt= 14, collt= celltouches };
protected internal static short[] housetouch; // for touch position start points
protected internal static byte[] touch; // col, box and grid position starts
internal enum subhousetype{ row=-1, box=8, col=17 }; // sectional start points in rbc for scanning, compensated by 1
protected internal static byte[] houserbc; // start points for each group of 9 in the section
protected internal static string[] namerbc; // name of each group of 9 start point
protected internal static byte[] rbc; // all houses enumerated as rows, boxes, then columns

protected internal static short[] houseb2rc; // for box-col touch position start points -- touches == 3
protected internal static string[] nameb2rcrowbox; // name of each group of 3 rowbox
protected internal static byte[] rowbox; // box and row
protected internal static byte[] gprowbox; // for gridpos (<81), the houseb2rc (<27) which contains its rowbox
protected internal static string[] nameb2rcboxcol; // name of each group of 3 boxcol
protected internal static byte[] boxcol; // box and column
protected internal static byte[] gpboxcol; // for gridpos (<81), the houseb2rc (<27) which contains its boxcol

protected internal static short[] houseoutb2rc; // for box-outcol touch position start points -- touches == 6
protected internal static byte[] boxoutcol;
protected internal static byte[] boxoutrow;
protected internal static byte[] coloutbox;
protected internal static byte[] rowoutbox;
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT
Page 1 of 1

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron