This popular Japanese number puzzle has just one easy rule:
In every Row, every Column and every 3x3 sub-grid, all the numbers from 1 to 9 should appear, but only once in each row, column and sub-grid.
+------+-------+------+
| 0 0 0 | 7 0 0 | 4 0 0 |
| 0 3 0 | 0 9 0 | 0 2 0 |
| 4 0 0 | 0 0 5 | 0 0 0 |
+------+-------+------+
| 0 0 8 | 0 0 0 | 0 0 5 |
| 0 9 0 | 0 3 0 | 0 7 0 |
| 6 0 0 | 0 0 0 | 3 0 0 |
+------+-------+------+
| 0 0 0 | 4 0 0 | 0 0 6 |
| 0 7 0 | 0 2 0 | 0 9 0 |
| 0 0 5 | 0 0 8 | 0 0 0 |
+------+-------+------+
Replace the 0's with the digits required to satisfy the rule.
(In reply to
A popular game in my neighborhood.... by Penny)
Penny, here's a recursive solution (also written in VB.NET).
It runs in under a second, and gets the same result that you got. You might want to give recursive logic another chance... :-)
------------------------------------------------
Module Module1
Dim board As Integer(,) = { _
{0, 0, 0, 7, 0, 0, 4, 0, 0}, _
{0, 3, 0, 0, 9, 0, 0, 2, 0}, _
{4, 0, 0, 0, 0, 5, 0, 0, 0}, _
{0, 0, 8, 0, 0, 0, 0, 0, 5}, _
{0, 9, 0, 0, 3, 0, 0, 7, 0}, _
{6, 0, 0, 0, 0, 0, 3, 0, 0}, _
{0, 0, 0, 4, 0, 0, 0, 0, 6}, _
{0, 7, 0, 0, 2, 0, 0, 9, 0}, _
{0, 0, 5, 0, 0, 8, 0, 0, 0} _
}
Sub Main()
Dim i As Integer, j As Integer
If Not test(0, 0) Then
Console.WriteLine("no solution")
Else
For i = 0 To 8
For j = 0 To 8
Console.Write(board(i, j))
Next
Console.WriteLine()
Next
End If
Console.ReadLine()
End Sub
Function test(ByVal x As Integer, ByVal y As Integer) As Boolean
If board(x, y) = 0 Then
For n As Integer = 1 To 9
board(x, y) = n
'Is this unique in this column?
For m As Integer = 0 To 8
If m <> y And board(x, m) = n Then
board(x, y) = 0
Exit For
End If
Next
If board(x, y) <> 0 Then
'Is this unique in this row?
For m As Integer = 0 To 8
If m <> x And board(m, y) = n Then
board(x, y) = 0
Exit For
End If
Next
If board(x, y) <> 0 Then
'Is this unique in this subgrid?
Dim xmin As Integer = Int(x / 3) * 3 'returns 0,3, or 6
Dim ymin As Integer = Int(y / 3) * 3
For xx As Integer = xmin To xmin + 2
For yy As Integer = ymin To ymin + 2
If board(xx, yy) = n And (xx <> x Or yy <> y) Then
board(x, y) = 0
Exit For
End If
Next
If board(x, y) = 0 Then Exit For
Next
If board(x, y) <> 0 Then
If x = 8 And y = 8 Then
Return True
Else
If testNext(x, y) Then
Return True
Else
board(x, y) = 0
End If
End If
End If
End If
End If
Next
If board(x, y) = 0 Then Return False
Else
Return testNext(x, y)
End If
End Function
Function testNext(ByVal x, ByVal y) As Boolean
y += 1
If y > 8 Then
y = 0
x += 1
End If
If x > 8 Then
Return False
Else
Return test(x, y)
End If
End Function
End Module
re: A popular game in my neighborhood....
