Abstract Confusions

Complexity is not a cause of confusion. It is a result of it.

Tag Archives: Games

Math Games for Children

Games are the sure shot fun way to teach some thing. And math is one of the top-notch skills one needs to own for being successful in any career. Imagine if playing games hone your mathematical skills. As a kid I grew up learning few board games which helped me to understand the most basic math operations – counting, addition and division (subtraction and multiplication thereof).

Very recently, I tried teaching math principles to my nephew but found difficult without the help of games. The most important thing I did was to run to a store to get him a board game. So, if you don’t want to spend those long boring hours and make teaching fun, try few of these games.

Snakes and Ladders

This is a simple game. Most of adults would have played it. Two or more players can play this game. This board game has hundred squares numbered from 1 through 100. And a player wins if he starts from 1 and reach 100. Each player has to toss a die and move their playing piece according to the output of the die.

ladders-snakes-board-game-screenshot

Snakes and Ladders - A Chance game in 100 squares

Read more of this post
Advertisements

Instant Insanity – A Graph Theoretic Wonder

Instant insanity is one the many games involving sound mathematical principles. In particular it involves graph theory to solve. One of the mathematics most powerful tool – representation theory is used. As you are aware of, what looks like a strange problem is transformed into totally a unrelated problem in another field because of the hidden relations / transformations. Often these relations transform into a treasure trove of knowledge and excitement.

Read more of this post

And hence the sudoku is solved

Sudoku is one of the interesting puzzles one might have played. Sudoku gained popularity in late 1990s. Sudoku is a not a complex game to understand. Sudoku doesn’t have confusing rules. It doesn’t need accessories to play. All you need is a pencil and perhaps an eraser. I have seen old age people getting more interested in solving it because of its simplicity. There are bunch of guys, who tried writing computer programs, so that, it solves the puzzle. What’s interesting is, even though there are strategies on how to play sudoku. No one had a proved method for solving sudoku.

Enter mathematics

People started looking for tools, steps or methods to solve sudoku. The reason being, sudoku is ridiculously easy but still posed rigidity from being conquered. Some times people get so much frustrated because there might be two or three numbers away from solving but still not able to finish it. Computer programs are no good. All they could do is trail and error.

Sudoku - Game of numbers

Sudoku - Game of numbers

Enter mathematics, and things started to settle down. Sudoku is now solved mathematically. I was expecting this to happen. Because, sudoku to a certain extend can be played purely based on logic. For hard puzzles, others used another technique known as back tracking to solve it. But a mathematical method was lacking. Recently, this was supplied in an mathematical paper.

Pencil and paper algorithm

A professor of computer science, J. F. Crook from Winthrop university, US, has provided an algorithm, what he calls as, a pencil and paper algorithm for solving sudoku in an notice to AMS. The paper can be read from here. In that paper, J. F. Crook discussed how sudoku is played, rules and known strategies for solving it. Couple of definitions, examples and finally the algorithm to solve sudoku using pencil and paper. Here is that algorithm for you.

Algorithm: J. F. Crook’s pencil and paper algorithm.

  1. Find all forced numbers in the puzzle.
    This is a straight forward step. Just take a look at the puzzle and fix the obvious choices in the cell.
  2. Markup the puzzle.
    This is where you do the guessing. Start writing the possible numbers into a small set for every cell. This is known as ‘markup’.
  3. Search iteratively for ‘preemptive set’.
    This is looking for set of numbers or a singleton set in order to finalise the number for the cell. You need to repeat this for cells, rows and columns. Arriving at this preemptive set and hidden preemptive set is the key in finding solution for a sudoku puzzle. I am not going to explain in detail as needs lengthy explanation, and explained in detail in the paper.
  4. If  solution is reached, stop. Else, make a random choice and continue from step 3.
    There are chances, that you may not gracefully finish the puzzle without making a random choice. So make the necessary random choice to continue the game and solve it. Crook explained the need for making random choice by demonstrating that there are chances for a puzzle to have several possible solution.

Most of the mathematics is done in proving how preemptive sets are used to solve sudoku.

Critics

Mathematical proof for sudoku was expected for long time. Crook used combinatorial techniques in proving solution. The pencil and paper algorithm also needed a random input. Even though this is because of the non-uniqueness of sudoku solution, the algorithm looks in-complete. Even the best computer algorithms use random methods to solve sudoku. A definitive method for solving sudoku is still needed.

What Crook has shown is very important. When the news that sudoku is solved mathematically spread, people feared instead of rejoice. Papers reported that they don’t need a mathematical solution. At times, it is like some one telling the climax of a thriller. But, looking at the Crook’s pencil and paper algorithm, it is easy to do sudoku as one used to do previously rather then setting it up with mathematical methods. An comparison in the same paper states, it took 4 minutes for solving a sudoku puzzle normal way compared to 50 minutes using the pen and paper method. Perhaps with time and practice one might reduce the time taken from 50 minutes to 5 minutes. But you won’t be doing sudoku anymore.

At least in the foreseeable future, there won’t be a definitive algorithm, strategy or method to solve sudoku. You can still enjoy the happiness of finishing the puzzle on your own.