[Skip Navigation] [CSUSB] / [CNS] / [Comp Sci Dept] / [R J Botting] / [Samples] / sudoku.maths
[Index] [Contents] [Source Text] [About] [Notation] [Copyright] [Comment/Contact] [Search ]
Tue Sep 18 15:27:11 PDT 2007

Contents

    Sudoku -- an Example of Applied Logic and Mathematics

      Author

       Richard J Botting, CSci Dept, CSUSB.

      Introduction

      The Sudoku puzzle has become a distraction, entertainment, and addiction for many people. In many ways it resembles previous fads like Rubrik's Cube and "Instant Insanity". However, in respect it is different: it is a paper and pencil puzzle rather than being based on a piece of equipment. It provides a nice example that teachers can use in class. This document develops a precise mathematical definition of Sudoku. The [ Wikipedia sudoku entry ] which provides a very good but informal description of the puzzle.

      Here I try to define it as accurately as possible. I do this partially because I believe that the first step to solving many problem with many interconnected parts is to understand them. One way to test one's understanding is to create a mathematical model.

      Writing these models also lets me test and demonstrate a language I developed (MATHS) for writing such descriptions. I found a small bug (a missing "/") in the tool I use to generate these "Sample" pages while writing this plus some motivation to improve my description of bijections for the MATHS language.

      In practice, I tend to do these descriptions very quickly and roughly with lots of crossing out and scribbling.

      Sudoku Defined

      Here is a picture of a simple 4 by 4 Sudoku:

      A 4><4 grid of boxes with 5 numbers filed in.

      Here is a link to a larger 9><9 puzzle [ http://www.websudoku.com/ ] on a popular "Web Sudoku" site. Here is one from the flyer for this seminar: A 9><9 Sudoku puzzle

      In all rectangular Sudoku the large rectangle is divided into small regions each of which is a smaller rectangle of square boxes. In the 4><4 case there are 4 regions each containing 4 squares. In the 9 case there are 9 regions (in a kind of 3><3 tic-tac-toe grid) each containing a smaller 3><3 grid of square. A 6><6 puzzle has a 3><2 grid of regions and each region is a 2><3 grid of squares. There is horribly big 16><16 form of the puzzle with 16 regions and each region containing 16 (4><4) squares.

      Typically most of the squares are blank and some of them contain a single digit. The puzzle is to fill in the blank squares with digits:
      SizeRegion|Regions|Digits
      4><42><241,2,3,4
      6><63><26 (2><3 layout)1,2,3,4,5,6
      9><93><391,2,3,4,5,6,7,8,9
      16><164><4160,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
      The digits when filled in must fit three simple rules:

    1. Rules_0::=following,
      Net
      1. (Row0): Each row contains each digit once and once only.
      2. (Col0): Each column contains each digit once and once only.
      3. (Box0): Each region contains each digit once and once only.

      (End of Net)

      The elegance and power of the puzzle comes from the fact that the number of rows in the big grid is precisely equal to the number of columns and equal to the number of squares in each region. With out this restriction the Rules_0 can not be applied.

      Mathematical Model

      In general we start with the number of rows and columns in each region:

    2. r::1..* =the number of rows per region, a natural number from 1,2,3,...
    3. c::1..* =the number of columns per region, a natural number from 1,2,3,...

      Each region has r rows and c columns, so the size of a region is

    4. N::=r*c.

      These regions are also organized in a grid with c rows and r cols. So the total number of squares is N*N.

      This is also the number of digits:

    5. Digits::Finite_set, a set of symbols.

      And we have precisely N of them:

    6. |-|Digits| = N. (note1)

      Now each r><c region is one element in a c >< r grid of regions(note2). So the whole grid has N^2 square in it and we want to find a digit to put in each one.

      A grid is defined mathematically as a Cartesian (as in Rene Descartes) grid like many American cities. Symbolically,

    7. Row::=1..N,
    8. Col::=1..N,
    9. Grid::=Row >< Col.

      So

    10. (Grid)|-(1,1) is in Grid.
    11. (Grid)|-If N>4 then (2,4) is in Grid.
    12. (Grid)|-(N,N) is in Grid.

      (i,j)j=1j=2j=3j=4
      i=1(1,1)(1,2)(1,3)(1,4)
      i=2(2,1)(2,2)(2,3)(2,4)
      i=3(3,1)(3,2)(3,3)(3,4)
      i=4(4,1)(4,2)(4,3)(4,4)

      Indeed

    13. (Grid)|-For all i:Row, j:Col, (i,j) is in Grid.

      The placing of digits is modeled as a mapping (or function) from the Grid into the Digits:

    14. Board::=Grid -> Digits.
      Let
        If r=c=4 then here is a board
      1. a_board::= (1,1)+>1 | (1,2)+>2 | (1,3)+>3 | (1,4)+>4 | (1,1)+>1 | (1,2)+>2 | (1,3)+>3 | (1,4)+>4 | (1,1)+>1 | (1,2)+>2 | (1,3)+>3 | (1,4)+>4 | (1,1)+>1 | (1,2)+>2 | (1,3)+>3 | (1,4)+>4.

        Or using a table:
        1 2 3 4
        1 2 3 4
        1 2 3 4
        1 2 3 4

        However this is not valid sudoku board. To define what makes a board valid (Rules_0), we first need to defines the rows, cols, and regions of a given board.

        So, for example:

      2. a_board.row(1) = (1,2,3,4).

      3. a_board.col(2) = (2,2,2,2).

      4. a_board.box(1,1) = ( (1,1)+>1 | (1,2)+>1 | (2,1)+>1 | (2,2) +> 2)=
        12
        21


      (Close Let )

      Rows and columns are not difficult to define:

    15. For b:Board, i:Row, b.row(i)::=map[j:Col](b(i,j)).
    16. For b:Board, i:Col, b.col(i)::=map[j:Row](b(j,i)).

      (note for formalists: b.row(i) is one of many ways of writing (row(b))(i). row: Board->(Row->Digits) )

      Defining the regions is a little trickier,

    17. For b:Board, I:1..c, J:1..r, b.box(I,J)::=map[i:1..r,j:1..c](b(i+(I-1)*r, j+(J-1)*c).

      (I hope I got the above formula right... otherwise [click here [socket symbol] if you can fill this hole] )

      Here, box : Board->((1..c)><(1..r)->((1..r)><(1..c)->Digits)).

      We can now express the idea that a list has each digit once and once only. Since this must define a one-to-one map from Row to Digit (symbolized "Row---Digit" in MATHS, see [ A---B in logic_5_Maps ] ).

    18. For b:Board, perm_row(b)::= for all i:Row ( b.row(i) is in Row---Digits ).

    19. For b:Board, perm_col(b)::= for all i:Col ( b.col(i) is in Col---Digits ).

    20. For b:Board, perm_box(b)::= for all I:1..c, J:1..r, ( b.box(I,J) is in (1..r><1..c)---Digits).

      A note on terminology above: When one to one maps from a set into itself is called a permutation. With most sudoku the Digit = Row = Col (this is not true when N=16). And this is where the names perm_row and perm_col come from.

    21. Rules_1::=following,
      Net
      1. board::Board.
      2. |- (Row): perm_row(board). Each row contains each digit once and once only.
      3. |- (Col): perm_col(board). Each column contains each digit once and once only.
      4. |- (Box): perm_box(board). Each region contains each digit once and once only.

      (End of Net)

      (The above box is a "Net" of variables and assumptions. These are a useful tool in describing computerized systems! )

      Sudoku Simply but Slowly Solved

      Prolog is a useful prototyping tool. You can express the problem in the language and it often gives a way to solve the problem. As I expected this work well with small (4><4) examples [ ../cs320/prolog/sudoku4.plg ] but for normal size problems the program [ ../cs320/prolog/sudoku9.plg ] takes hours to run.

      The reason is simple. They both work by generating every possible permutation of the rows in turn. There are N! ( 1*2*3*4* ... *N) permutations of one row and N rows. So the number of cases tried is
      (N!)^N
      NN!(N!)^NApproximatelyTimes
      1111
      2244*10^0
      362162*10^2
      424331,7763*10^5<0.1 second
      512024,883,200,0002*10^11
      6720...10^17
      75,040...10^26
      840,320...10^37
      9362,880...10^503..4 hours
      ......

      Standard computer science predicts that the time will be dominated by the above numbers. The actual times on a 9><9 even with many speed ups is too slow to be useful.

      Solving by Hand

      I use some strategies that are quite well known. One is to list the possible digits for each square that does not have a known digit (Marking up in the [ Wikipedia sudoku entry ] ). The second is looking at each digit and its pattern of occurrence (Cross-hatching in the [ Wikipedia sudoku entry ] ).

      Tracking the possible digits in MATHS would be described as a grid of sets of digits:

    22. possible: Grid -> @ Digits. In a blank board, each digit is a possible in any place:
    23. Grid +> Digits.

      As each digit is determined then it is removed from all sets in the same row, the same column, and the same region.

      Demo TBD.

      I've found a spreadsheet is quite helpful to keep track of these. I've also found a spread sheet a handy way to handle the cases where I have to guess what is in a square and have 2 or 3 options: you can copy and paste the partly solved grid and do each possibility in a separate grid.

      I have another strategy that works better than I'd expect. I pick one digit to focus on -- say 7. I can look at the grid and see all the 7's. Often a row of three regions has two regions that have a 7 and one without. For example
      __1__7__2
      ______7__
      2_3______
      So I know that there is a 7 in the left hand region, and I also know it is not in the first two rows of that region. But in the third row of that region there is only one space left! So I have the 7 placed. This is discussed under "Analyzing" on the [ Wikipedia sudoku entry ] which suggests that certain patterns of digits have been given names.

      A similar pattern can be found with a column of regions.

      By hand I solve tough 9><9 is 2 or 3 days of spare time. A gentle 9><9, on a Palmtop takes an hour or so. But I'm still learning.

      Links


      (Wikipedia sudoku entry): An entry in the Wikipedia describing Sudoku [ Sudoku ]


      (Wikipedia): A social encyclopedia [ http://www.wikipedia.org/ ]


      (MATHS): My language for writing mathematical and logical descriptions [ ../maths/ ]

      Notations and Notes


    24. (note1): the '|-' is an assertion symbol that introduces a postulate, axiom, or other assumption into a document written in MATHS. The |X| notation stands fro the cardinality or size of set. Most MATHS documents are concerned with finite sets.


      (note2): I use "><" for Cartesian grids and products(MATHS).


      (map): "map" is a MATHS key word used to describe functions and mappings. As an example, map[x](x*x) is the function that squares a number. The set of maps(functions) from set A to set B is indicated A->B. One-one maps: A---B. [ ../maths/intro_function.html ]


      (Seminar): Oct 28th 10-12 Jack Brown Hall CSUSB

      1. 10:00 Meet and greet with snacks and coffee (10 minutes)
      2. 10:10 Open session (Dr. Botting facilitates, 30 minutes)
      3. 10:40 Sudoku by Computer, Part 1 (Dr. Botting, 30 minutes)
      4. 11:10 Sudoku by Computer, Part 2 (Dr. Voigt, 30 minutes) [ seminar.html ]
      5. 11:40 Wrap up (10 minutes)
      6. 11:50 End of meeting, 10 minutes to get to next meeting.

    25. TBD::="To be Done".

      Acknowledgment

    . . . . . . . . . ( end of section Sudoku -- an Example of Applied Logic and Mathematics) <<Contents | End>>

End