Mapping 3x3 boxes to rows

rkral · 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

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

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...

angusj · Site Admin

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

angusj · Site Admin

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 ...

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

angusj · Site Admin

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

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

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

kaipiranha · 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 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

strmckr

this also does it for turbo pascal..

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

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;