All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
There is something missing (Posted on 2005-05-13) Difficulty: 3 of 5
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.

See The Solution Submitted by Hugo    
Rating: 4.4000 (10 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution A popular game in my neighborhood.... | Comment 5 of 29 |
...is writing very large programs (copy/pasting duplicate code - I've given up on recursive logic) to solve problems like this one as quickly and efficiently as possible.
 
[The modified program summarized below executes in less than a minute]
 
Answer:
 
1 5 2 7 8 3 4 6 9
7 3 6 1 9 4 5 2 8
4 8 9 2 6 5 7 3 1
3 2 8 6 4 7 9 1 5
5 9 1 8 3 2 6 7 4
6 4 7 9 5 1 3 8 2
2 1 3 4 7 9 8 5 6
8 7 4 5 2 6 1 9 3
9 6 5 3 1 8 2 4 7
 
The following program ran is less than 1 minute (1:40:43 PM to 1:41:25 PM) to find that as the unique matrix:
 
Imports System
Imports System.IO
Imports System.Text
Imports System.Runtime.InteropServices
Imports System.Math
Module Module1
    Sub Main()
        Randomize()
        Dim strexit As String
        Dim intmatrix(9, 9) As Integer
        Dim intloop8 As Integer = 8
        Dim strflag As String
        Dim strstart As String
        Dim intrefresh(60, 2) As Integer
        Dim intloop59 As Integer = 59
        strstart = TimeOfDay
        Console.WriteLine("START TIME: " & strstart)
        init_refresh_tbl(intrefresh)
        For nextindex As Integer = 1 To 9
            cell_0(nextindex, intmatrix, intloop8, strflag, _
            intrefresh, intloop59)
        Next
        Console.WriteLine(" ")
        Console.WriteLine("END TIME: " & TimeOfDay)
        Console.WriteLine(" ")
        strexit = "x"
        While strexit > " "
            Console.WriteLine( _
            "Just hit ENTER to quit.")
            strexit = LCase(Console.ReadLine())
        End While
    End Sub

    Sub cell_0(ByRef thisindex, ByRef intmatrix, _
        ByRef intloop8, ByRef strflag, ByRef intrefresh, _
ByRef intloop59)
        Dim introw As Integer
        Dim intcol As Integer
        introw = intrefresh(0, 0)
        intcol = intrefresh(0, 1)
        intialize_matrix(intmatrix, intloop8, _
        introw, intcol, intrefresh, intloop59)
        searchgrid(introw, intcol, intmatrix, thisindex, strflag)
        If strflag = "n" Then
            Exit Sub
        End If
        searchrow(introw, intmatrix, thisindex, strflag, _
        intloop8)
        If strflag = "n" Then
            Exit Sub
        End If
        searchcol(intcol, intmatrix, thisindex, strflag, _
        intloop8)
        If strflag = "n" Then
            Exit Sub
        End If
        intmatrix(introw, intcol) = thisindex
        For nextindex As Integer = 1 To 9
            cell_1(nextindex, intmatrix, intloop8, strflag, _
            intrefresh, intloop59)
        Next
    End Sub

    Sub cell_1(ByRef thisindex, ByRef intmatrix, _
       ByRef intloop8, ByRef strflag, ByRef intrefresh, ByRef intloop59)
        Dim introw As Integer
        Dim intcol As Integer
        introw = intrefresh(1, 0)
        intcol = intrefresh(1, 1)
        intialize_matrix(intmatrix, intloop8, _
        introw, intcol, intrefresh, intloop59)
        searchgrid(introw, intcol, intmatrix, thisindex, strflag)
        If strflag = "n" Then
            Exit Sub
        End If
        searchrow(introw, intmatrix, thisindex, strflag, _
        intloop8)
        If strflag = "n" Then
            Exit Sub
        End If
        searchcol(intcol, intmatrix, thisindex, strflag, _
        intloop8)
        If strflag = "n" Then
            Exit Sub
        End If
        intmatrix(introw, intcol) = thisindex
        For nextindex As Integer = 1 To 9
            cell_2(nextindex, intmatrix, intloop8, strflag, _
            intrefresh, intloop59)
        Next
    End Sub
 
etc...... etc...... etc........
 
    Sub cell_59(ByRef thisindex, ByRef intmatrix, _
    ByRef intloop8, ByRef strflag, ByRef intrefresh, ByRef intloop59)
        Dim introw As Integer
        Dim intcol As Integer
        introw = intrefresh(59, 0)
        intcol = intrefresh(59, 1)
        intialize_matrix(intmatrix, intloop8, _
        introw, intcol, intrefresh, _
        intloop59)
        searchgrid(introw, intcol, intmatrix, thisindex, strflag)
        If strflag = "n" Then
            Exit Sub
        End If
        searchrow(introw, intmatrix, thisindex, strflag, _
        intloop8)
        If strflag = "n" Then
            Exit Sub
        End If
        searchcol(intcol, intmatrix, thisindex, strflag, _
        intloop8)
        If strflag = "n" Then
            Exit Sub
        End If
        intmatrix(introw, intcol) = thisindex
        display_results(intmatrix, intloop8)
    End Sub

    Sub searchgrid(ByRef introw, ByRef intcol, _
        ByRef intmatrix, ByRef indexval, ByRef strflag)
        Dim intstart1 As Integer
        Dim intstart2 As Integer
        strflag = "y"
        If introw <= 2 Then
            intstart1 = 0
            If intcol <= 2 Then
                intstart2 = 0
            ElseIf intcol <= 5 Then
                intstart2 = 3
            Else
                intstart2 = 6
            End If
        ElseIf introw <= 5 Then
            intstart1 = 3
            If intcol <= 2 Then
                intstart2 = 0
            ElseIf intcol <= 5 Then
                intstart2 = 3
            Else
                intstart2 = 6
            End If
        Else
            intstart1 = 6
            If intcol <= 2 Then
                intstart2 = 0
            ElseIf intcol <= 5 Then
                intstart2 = 3
            Else
                intstart2 = 6
            End If
        End If
        For index1 As Integer = intstart1 To intstart1 + 2
            For index2 As Integer = intstart2 To intstart2 + 2
                If intmatrix(index1, index2) = indexval Then
                    strflag = "n"
                    Exit Sub
                End If
            Next
        Next
    End Sub

    Sub searchrow(ByRef introw, ByRef intmatrix, _
        ByRef indexval, ByRef strflag, ByRef intloop8)
        strflag = "y"
        For index2 As Integer = 0 To intloop8
            If intmatrix(introw, index2) = indexval Then
                strflag = "n"
                Exit Sub
            End If
        Next
    End Sub

    Sub searchcol(ByRef intcol, ByRef intmatrix, _
        ByRef indexval, ByRef strflag, ByRef intloop8)
        strflag = "y"
        For index1 As Integer = 0 To intloop8
            If intmatrix(index1, intcol) = indexval Then
                strflag = "n"
                Exit Sub
            End If
        Next
    End Sub

    Sub intialize_matrix(ByRef intmatrix, ByRef intloop8, _
        ByRef introw, ByRef intcol, ByRef intrefresh, _
        ByRef intloop59)
        Dim strflag As String
        Dim intsub1 As Integer
        Dim intsub2 As Integer
        strflag = "n"
        For index1 As Integer = 0 To intloop59
            If intrefresh(index1, 0) = introw And _
            intrefresh(index1, 1) = intcol Then
                strflag = "y"
            End If
            If strflag = "y" Then
                intsub1 = intrefresh(index1, 0)
                intsub2 = intrefresh(index1, 1)
                intmatrix(intsub1, intsub2) = 0
            End If
        Next
        intmatrix(0, 3) = 7
        intmatrix(0, 6) = 4
        intmatrix(1, 1) = 3
        intmatrix(1, 4) = 9
        intmatrix(1, 7) = 2
        intmatrix(2, 0) = 4
        intmatrix(2, 5) = 5
        intmatrix(3, 2) = 8
        intmatrix(3, 8) = 5
        intmatrix(4, 1) = 9
        intmatrix(4, 4) = 3
        intmatrix(4, 7) = 7
        intmatrix(5, 0) = 6
        intmatrix(5, 6) = 3
        intmatrix(6, 3) = 4
        intmatrix(6, 8) = 6
        intmatrix(7, 1) = 7
        intmatrix(7, 4) = 2
        intmatrix(7, 7) = 9
        intmatrix(8, 2) = 5
        intmatrix(8, 5) = 8
    End Sub

    Sub display_results(ByRef intmatrix, ByRef intloop8)
        Dim strstring As String
        Console.WriteLine(TimeOfDay & ": One answer:")
        For index1 As Integer = 0 To intloop8
            strstring = ""
            For index2 As Integer = 0 To intloop8
                strstring &= Str(intmatrix(index1, index2)) & " "
            Next
            Console.WriteLine(strstring)
        Next
    End Sub

    Sub init_refresh_tbl(ByRef intrefresh)
        Dim intsub1 As Integer = -1
        intsub1 += 1
        intrefresh(intsub1, 0) = 0
        intrefresh(intsub1, 1) = 4
        intsub1 += 1
        intrefresh(intsub1, 0) = 0
        intrefresh(intsub1, 1) = 5
        intsub1 += 1
        intrefresh(intsub1, 0) = 1
        intrefresh(intsub1, 1) = 3
 
etc...etc..... this table establishes the order of
cells so that the search is by a good subgrid order.

    End Sub
End Module
 

Edited on May 18, 2005, 7:45 pm
  Posted by Penny on 2005-05-13 22:58:16

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information