QUICK LINKS

Select A Quick Link FPT Home CSE@UNSW

Background Information: The Sudoku Puzzle

Sudoku is a logic puzzle that has gained massive popularity in recent years. Today, you can find daily Sudoku puzzles posted in major newspapers around the globe.

Sudoku is a simple, yet addictive, logic puzzle. There is a wealth of information on the Internet about Sudoku, including daily puzzles, solvers, and even mathematical analyses of the puzzle. A few great sites that offers Sudoku information include Wikipedia and Web Sudoku, which also include an online tutorial.

A typical Sudoku puzzle is shown below:

Each Sudoku puzzle consists of a 3-by-3 grid of boxes. Each box itself is a 3-by-3 grid of cells. Therefore, there is a total of 81 cells. Some of them, called givens, are filled in when the puzzle is given to you.

The rule to solve a Sudoku puzzle is simple: Fill in all the cells with a number from 1 to 9 such that no number appears more than once in a row, a column, or a box. For example, the solution to the above sample is shown below:

Variations

In general, the traditional Sudoku puzzle with 3*3*3*3=81 cells can be extended to one with N⁴ cells. We say that this general Sudoku puzzle has an order N, while the traditional Sudoku puzzle has an order 3. A general Sudoku puzzle of order N contains N*N boxes, where each box contains N*N cells. The goal then is to fill these cells with unique numbers from 1 to N² such that no number appears more than once in a row, a column, or a box. For example, a puzzle with N=4 is shown below:

For this competition, you will be designing an FPGA-based Sudoku solver that can solve puzzles for 3 ≤ N ≤ 15.