
View previous topic :: View next topic 
Author 
Message 
 rkral
 Joined: 21 Oct 2005  Posts: 233  :   Items 

Posted: Tue Jan 03, 2006 8:27 pm Post subject: Mapping 3x3 boxes to rows 


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 ...
 First, with no translation,
 Second, transposing the rows and columns, and
 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 


 ulcman
 Joined: 10 Jan 2006  Posts: 1  :   Items 

Posted: Tue Jan 10, 2006 10:37 pm Post subject: 


Consider R is the row number (19), C is the column no., B is the box no:
Then:
B = int((R1)/3)*3+int((C1)/3)+1
You can use this within the loops of the rows and columns... 

Back to top 


 angusj Site Admin
 Joined: 18 Jun 2005  Posts: 406  :   Items 

Posted: Wed Jan 11, 2006 1:11 am Post subject: Re: Mapping 3x3 boxes to rows 


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 


 rkral
 Joined: 21 Oct 2005  Posts: 233  :   Items 

Posted: Fri Jan 13, 2006 6:08 pm Post subject: Re: Mapping 3x3 boxes to rows 


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 ...  Treat rows as rows,
 treat cols as rows, and
 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 remapping)
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
RowBox 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. )
Maybe such a mapping is an impossiblity.
Ron 

Back to top 


 angusj Site Admin
 Joined: 18 Jun 2005  Posts: 406  :   Items 

Posted: Fri Jan 13, 2006 9:58 pm Post subject: 


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 


 rkral
 Joined: 21 Oct 2005  Posts: 233  :   Items 

Posted: Sat Jan 14, 2006 1:02 am Post subject: 


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 


 angusj Site Admin
 Joined: 18 Jun 2005  Posts: 406  :   Items 

Posted: Sat Jan 14, 2006 4:12 am Post subject: 


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 


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

Posted: Fri Mar 10, 2006 11:58 am Post subject: Re: Mapping 3x3 boxes to rows 


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 ...
 First, with no translation,
 Second, transposing the rows and columns, and
 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*(i11)+i2
j=3*(j11)+j2
Then the box index =3*(i11)+j1
an the cellinabox index =3*(i21)+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 


 rkral
 Joined: 21 Oct 2005  Posts: 233  :   Items 

Posted: Fri Mar 10, 2006 12:30 pm Post subject: Re: Mapping 3x3 boxes to rows 


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*(i11)+i2
j=3*(j11)+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 


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

Posted: Fri Mar 10, 2006 1:20 pm Post subject: Re: Mapping 3x3 boxes to rows 


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*(i11)+i2
j=3*(j11)+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 


 kaipiranha
 Joined: 14 Apr 2006  Posts: 1  :   Items 

Posted: Fri Apr 14, 2006 1:12 pm Post subject: Re: Mapping 3x3 boxes to rows 


[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 reidentify 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 'blockrow 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 


 strmckr
 Joined: 24 Apr 2009  Posts: 52  :   Items 

Posted: Wed Apr 29, 2009 3:34 pm Post subject: Does anyone know of a mapping algorithm that allows a solver 


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:=(axb)+(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 


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

Posted: Mon Jun 29, 2009 1:13 pm Post subject: 


I first programmed sudoku as a 4d array, but have since abandonded that approach in favor of a 1d array with locator tables.
rowmajor 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 rowcolumn 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 2dimensional 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 rowmajor 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 boxcol 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 boxoutcol 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 




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

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
