Sudoku Solver

All submissions for this problem are available.

Quoting Wikipedia : "Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes (also called blocks or regions) contains the digits from 1 to 9 only one time each. The puzzle setter provides a partially completed grid." The rules for an N² X N² sudoku are as follows :

• The board is consists of N² rows and N² columns.
• Numbers between 1 and N²(inclusive) are to be filled in each row such that :
• All numbers in each row are distinct.
• All numbers in each column are distinct.
• All numbers in the sub-matrix having rows from (i*N + 1) to(i + 1)*N, and columns from (j*N + 1) to (j + 1)*N both inclusive, should be distinct. 0 <= i,j <= N-1. Rows and columns are 1 indexed. Each such sub-matrix is called a "box" or "region".

For this problem, you are required to solve a general N²X N² sudoku puzzle. Given a partially filled sudoku board, you have to fill it in as "perfect" a manner as possible.

Input :

The first line contains N,K. The following K lines contain 3 numbers: x, y and d. 1 <= x,y,d <= N^2. This means that a number d is present on the board at position (x,y) 2 <= N <= 30 0 <= K <= N⁴ At most 50% of the board will be covered at the start. All positions (x,y) in the input will be unique.

Output :

The output consists of N² rows having N² numbers each. Each number should be between 1 and N² (inclusive) and separated by a space. If the initial grid has a number d at position (x,y), then even the output should have the number d at position (x,y).

Scoring :

• For each row and every number K in the range 1 to N² that is missing from the row, incurs a penalty of 1.
• For each column and every number K in the range 1 to N² that is missing from the column, incurs a penalty of 1.
• Similary, for each box and every number K in the range 1 to N² that is missing from the box, incurs a penalty of 1.

A box (as explained above) is a N X N square and the grid can be divided into N² such non-overlapping boxes.

Example :

Input:

2 4
1 2 1
2 4 4
3 3 1
4 1 3

Output:

2 1 3 4
1 2 4 4
3 4 1 2
3 2 4 1

Penalty:

(0 + 1 + 0 + 0) + (1 + 1 + 1 + 1) + (2 + 2 + 1 + 1) = 11

---

Date:	2009-08-11
Time limit:	3s
Source limit:	50000B
Languages:	All except: TCL PERL6 CLOJ GO PYTH 3.1.2 F# C++ 4.3.2 ERL
Resource:	syco