Upward Diagonals Sudoku (UDS) - an NP Problem

There are two types of Sudoku games: the standard one, and the Diagonal Sudoku. For the latter, it includes the standard rules plus the additional rule that the two main diagonals must also only contain unique numbers.

I'd like to propose a third type: Upward Diagonals Sudoku, or UDS. In an UDS, the standard Sudoku rules apply, but we add one more rule: all the upward diagonals, all of them, must also only have unique numbers.

The solution to this problem is again using Backtracking, but I liked to create a specific easy, scalable function to add new rules, which I highlight here. This way, if we want to add a different rule in the future, all we need is to craftly modify this function.

This seems to be (arguably) an NP problem. When I asked for solutions using both Claude.ai and ChatGPT o1, they really struggle and can't really find a solution for me. It is interesting that eventually they give up and produce a code (without me asking for a code) that would arguably generate the solutions (I didn't try their code, but it is also based on backtracking).

On the other hand, if you ask them to verify whether a certain configuration is a valid UDS, they do it relatively fast. This is the typical NP problem, where you can verify a solution in polynomial time, but cannot create a solution in polynomial time.

Code is down below, with an example of the solution for the given initial configuration. Cheers, ACC.

using System;
using System.Collections;

int[][] sudokuBoard = new int[9][]
{
    new int[9] { 1, 0, 0, 0, 0, 0, 0, 0, 0 },
    new int[9] { 0, 2, 0, 0, 0, 0, 0, 0, 0 },
    new int[9] { 0, 0, 3, 0, 0, 0, 0, 0, 0 },
    new int[9] { 0, 0, 0, 4, 0, 0, 0, 0, 0 },
    new int[9] { 0, 0, 0, 0, 5, 0, 0, 0, 0 },
    new int[9] { 0, 0, 0, 0, 0, 6, 0, 0, 0 },
    new int[9] { 0, 0, 0, 0, 0, 0, 7, 0, 0 },
    new int[9] { 0, 0, 0, 0, 0, 0, 0, 8, 0 },
    new int[9] { 0, 0, 0, 0, 0, 0, 0, 0, 9 }
};


Hashtable collectionConditions = new Hashtable();

SetInitialBoardPosition();
SolveDiagonalSudoku(0);

void SolveDiagonalSudoku(int index)
{
    int row = index / 9;
    int col = index % 9;

    if (row >= sudokuBoard.Length)
    {
        PrintSudokuBoard();
        return;
    }

    if (sudokuBoard[row][col] != 0)
    {
        SolveDiagonalSudoku(index + 1);
    }
    else
    {
        int[] conditionKeys = CreateConditionKeys(row, col);

        for (int play = 1; play <= 9; play++)
        {
            bool allowedToPlay = true;
            foreach (int conditionKey in conditionKeys)
            {
                allowedToPlay &= CheckSudokuPlay(conditionKey, play);
                if (!allowedToPlay) break;
            }

            if (allowedToPlay)
            {
                foreach (int conditionKey in conditionKeys)
                    SudokuPlay(conditionKey, play);
                int temp = sudokuBoard[row][col];
                sudokuBoard[row][col] = play;
                SolveDiagonalSudoku(index + 1);
                sudokuBoard[row][col] = temp;
                foreach (int conditionKey in conditionKeys)
                    SudokuUnPlay(conditionKey, play);
            }
        }
    }
}

void SetInitialBoardPosition()
{
    for (int row = 0; row < sudokuBoard.Length; row++)
    {
        for (int col = 0; col < sudokuBoard[row].Length; col++)
        {
            if (sudokuBoard[row][col] != 0)
            {
                int[] conditionKeys = CreateConditionKeys(row, col);

                int play = sudokuBoard[row][col];
                bool allowedToPlay = true;
                foreach (int conditionKey in conditionKeys)
                {
                    allowedToPlay &= CheckSudokuPlay(conditionKey, play);
                    if (!allowedToPlay) break;
                }

                if (allowedToPlay)
                {
                    foreach (int conditionKey in conditionKeys)
                        SudokuPlay(conditionKey, play);
                }
            }
        }
    }
}

int[] CreateConditionKeys(int row, int col)
{
    return new int[] {
                        row,
                        10 + col,
                        100 + ((row / 3) * 3 + col / 3),
                        1000 + row + col
                     };
}

void PrintSudokuBoard()
{
    Console.WriteLine("Solution:");
    Console.WriteLine();
    for (int row = 0; row < sudokuBoard.Length; row++)
    {
        for (int col = 0; col < sudokuBoard[row].Length; col++)
        {
            Console.Write("{0} ", sudokuBoard[row][col]);
        }
        Console.WriteLine();
    }
    Console.ReadLine();
}

bool CheckSudokuPlay(int conditionKey, int play)
{
    if (!collectionConditions.ContainsKey(conditionKey))
        collectionConditions.Add(conditionKey, new HashSet());

    HashSet condition = (HashSet)collectionConditions[conditionKey];
    return !condition.Contains(play);
}

void SudokuPlay(int conditionKey, int play)
{
    HashSet condition = (HashSet)collectionConditions[conditionKey];
    condition.Add(play);
}

void SudokuUnPlay(int conditionKey, int play)
{
    HashSet condition = (HashSet)collectionConditions[conditionKey];
    condition.Remove(play);
}